Множество - вершина - граф
Cтраница 3
Циклически-реберная связность определяет отношение эквивалентности на множестве вершин V графа G. Множество всех вершин, циклически-реберно связанных с данной вершиной а0, назовем листовым множеством L ( UO)), которому принадлежит Со. Листовое множество может состоять только из вершины UQ; тогда листовое множество а0 называется особым. Это может случиться только тогда, когда все ребра в а0 являются петлями или разделяющими ребрами. [31]
У ( п С), то множества вершин графов G и Н не пересекаются. [32]
Лемма 1.4. Если существует подстановка t T множества вершин X графа G на множество Y графа Н Я, которая переводит граф G в граф Н, то граф G изоморфно вложим в граф Я. [33]
В связи с этим определим понятие разбиения множества вершин графа и докажем, что каждая подстановка может быть задана парой разбиений множества вершин. Ниже мы покажем, каким образом находить пары разбиений определенного вида, чтобы значительно сократить перебор для отыскания подстановки при разложении графа. [34]
Довольно часто возникает задача поиска таких подмножеств множества вершин X графа О, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества 8 с X, для которого порожденный подграф ( 5) является полным. Или какова максимальная мощность подмножества 5, такого, что граф ( 5) - вполне несвязный. Она состоит в нахождении минимально возможной мощности таких подмножеств 5 множества X, что любая вершина из X - б1 достижима из с помощью путей единичной длины. Решение этой задачи дается так называемым числом доминирования графа С. [35]
Довольно часто возникает задача поиска таких подмножеств множества вершин X графа G, которые обладают определенным, наперед заданным свойством. X, для которого порожденный подграф ( S) является полным. Или какова максимальная мощность подмножества S, такого, что граф ( S) - вполне несвязный. Она состоит в нахождении минимально возможной мощности таких подмножеств S множества X, что любая вершина из X - S достижима из S с помощью путей единичной длины. [36]
Перенумеруем вершины графа G и рассмотрим на множестве V вершин графа G функцию /, принимающую неотрицательные целые значения. Обозначим через k0 ( S, Т) число таких компонент Я графа G - ( S [) Т), что сумма q ( H, Т) У. [37]
Наконец, если ветвь может перемещаться вдоль некоторого множества S вершин графа, то S будем называть стволом дерева-графа или просто стволом. [38]
 |
Наилучший полученный маршрут в Eilon s - 75 ( Длина 535, размер популяции 20, уровень мутаций 0 3, элитное число 10. [39] |
Задача построения независимых ( внутренне устойчивых) подмножеств множества вершин графа неформально может быть сформулирована следующим образом. В заданном графе определяется семейство подмножеств вершин. Внутри каждого подмножества вершины графа между собой не соединены ребрами. Добавление любой вершины графа к такому подмножеству делает его не внутренне устойчивым. Задачи такого рода актуальны, когда необходимо определить наибольшее число групп независимых объектов. [40]
Автоморфизмом ф простого графа G называется взаимно однозначное отображение множества вершин графа G на себя, обладающее тем свойством, что вершины ф ( v) ир ( о)) смежны тогда и только тогда, когда смежны вершины о и да. [41]
Поскольку отношение связности является отношением эквивалентности ( А. А. Зыков [68]), то множество вершин X графа G ( X, U) можно разбить на непересекающиеся классы Xi, причем ребра графа будут соединять лишь вершины внутри этих классов. Таким образом, получим разбиение графа G на связные подграфы G, называемые компонентами связности. [42]
Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Эти узкие места определяют пропускную способность системы в целом. [43]
Таким образом, множества вершин связных компонент, а также сильных компонент образуют разбиение множества вершин графа, а число c ( G) связных компонент графа G определяется однозначно. [44]
 |
Симметричные графы.| Тождественные графы. [45] |
Страницы: 1 2 3 4