Cтраница 4
Группой графа называется совокупность всех его автоморфизмов; это группа подстановок, действующая на множестве вершин графа. Известно [13], что каждая конечная группа изоморфна группе некоторого графа, но не известно, вообще говоря, является ли данная группа подстановок группой графа. [46]
Теорема 9.5. Пусть G - данный граф, af - функция, определенная на множестве V вершин графа G и принимающая неотрицательные целые значения. [47]
Заметим, что так как S предполагается связной, то ее подграф связен, поэтому множество вершин графа Г0 включает в себя все четверные подгруппы из S. [48]
Следует заметить, что, используя рассмотренный выше алгоритм выделения семейства максимальных внутренне устойчивых подмножеств множества вершин графа ( максимальных пустых подграфов), можно выделять семейство Ф максимально полных подграфов. Для этого необходимо в матрице смежности R графа все единичные элементы заменить на нулевые и наоборот. В результате получим R и применяем алгоритм 1 без изменений. [49]
Набор независимых ребер графа G иногда называют паросоче-танием графа G, поскольку такой набор определяет разбиение множества вершин графа на пары вершин, инцидентных ребрам набора. G, называется наибольшим паросочетанием графа G. [50]
Продолжая исследования Хайнала и Шураньи [129], Дирак [97] и Гал-лаи [121] устанавливают достаточные условия возможности разбиения множества вершин графа на заданное число попарно непересекающихся подмножеств, порождающих полные подграфы; в эти условия входит ограничение сверху числа внутренней устойчивости данного графа, а также требование такого типа, чтобы каждый его элементарный цикл длины 3 имел хотя бы одну хорду или чтобы этому условию удовлетворяли по крайней мере все циклы нечетной длины. [51]
После применения процедуры ФФД к ( е, у) - ветвям приходим к промежуточному разбиению на множестве вершин графа, при котором классы эквивалентности объединяют вершины соответствующих частей ( е, у) - графа. [52]
Наиболее естественным является способ интерпретации схемы графом, при котором множеству - М модулей схемы взаимно однозначно ставится в соответствие множество X вершин графа G ( X, U), а множеству 5 соединений схемы - множество U ребер графа. Однако этот метод, при своей простоте, не свободен от ряда недостатков: не учитываются геометрические размеры модулей, за счет развязки узлов схемы в графе G появляются полные подграфы, т.е. вводится большое число избыточных ребер в графе, затрудняющих решение задач проектирования. Кроме того, граф часто получается неплаыар-ным, хотя соответствующая ему схема планарна. [53]
Через dv ( u, v) обозначим минимальную из длин ( и, v) - цепей, а через Т - множество вершин графа G, инцидентных нечетному числу ребер с отрицательными весами. [54]