Изоморфная графа

Cтраница 2

Ясно, что эти функции принадлежат одной и той же орбите группы ВА тогда и только тогда, когда они представляют изоморфные графы. Следовательно, как заметил Редфилд, графы могут быть перечислены с помощью П - произведений. [16]

Для завершения приведенного выше доказательства этого положения следует еще заметить, что подобные матрицы обладают изоморфными графами, так что А и А обладают изоморфными графами состояний. [17]

Другая особенность заключается в том, что при древесной классификации изоморфные ( в обычном смысле) графы не обязательно принадлежат к одному и тому же классу: существуют попарно изоморфные графы, которые относятся к разным классам. Любые же два изоморфных дерева, отличающиеся лишь разметкой вершин, маркируют в этой классификации два различных класса. При этом и мощности классов, маркируемых этими деревьями, тоже могут оказаться различными. [18]

Очевидно, что изоморфные графы С и Я могут быть представлены одной и той же диаграммой. При этом отрезок, представляющий ребро А графа О, или точку, представляющую вершину х графа О, можно интерпретировать как представления ребра ВА или вершины 0А - графа Я. [19]

Если ребра ориентированы, то их направления также должны соответствовать друг другу. Для нас в дальнейшем всюду будет несущественно, какое именно изображение графа используется, так как все изоморфные графы имеют одни п те же свойства. На рис. 1.2.1 приведены примеры изоморфных графов, образованных ребрами и вершинами правильных многогранников. [20]

Каждая взаимно однозначная функция /: Х ( 2 - Y представляет граф с множеством вершин X, и в этом графе вершины i и; смежны только в том случае, когда / г / есть элемент множества Yt. Ясно, что эти функции принадлежат одной и той же орбите группы ВА тогда и только тогда, когда они представляют изоморфные графы. Следовательно, как заметил Редфилд, графы могут быть перечислены с помощью П - произведений. [21]

Очевидно, что свойства плоскости графа не изменяются, если некоторое ребро разделить на два введением новой вершины степени 2 или если два ребра, инцидентные вершине степени 2, заменить на одно, удалив при этом данную вершину. Такие рассуждения приводят к следующему определению: графы G и G называются изоморфными с точностью до вершин степени 2, если они изоморфнц или если они могут быть превращены в изоморфные графы с помощью указанных выше преобразований. [22]

Таким образом, элементы 0 и 1 из множества Y используются для указания соответственно на существование или отсутствие ребра в графе. Рассмотрим степенную группу ВА, у которой А 5 ( Р2) и В Szt Ясно, что графы, представимые двумя функциями, эквивалентны относительно дополнительности тогда и только тогда, когда эти две функции принадлежат одной и той же орбите рассматриваемой степенной группы ВА. Поэтому если подстановка ( а; ( 0) ( 1)) из этой группы преобразует функцию / в функцию g, то / и g представляют изоморфные графы. А если / преобразуется в g подстановкой ( а; ( О, 1)), то две функции представляют взаимно дополнительные графы. Следовательно, число ар / - вершинных графов, подсчитываемых с точностью до их взаимной дополнительности, равно числу орбит указанной выше степенной группы. [23]

Таким образом, элементы 0 и 1 из множества Y используются для указания соответственно на существование или отсутствие ребра в графе. Рассмотрим степенную группу ВА, у которой А 5 ( P2) и В - Sz-Ясно, что графы, представимые двумя функциями, эквивалентны относительно дополнительности тогда и только тогда, когда эти две функции принадлежат одной и той же орбите рассматриваемой степенной группы ВА. Поэтому если подстановка ( а; ( 0) ( 1)) из этой группы преобразует функцию / в функцию g, то / и g представляют изоморфные графы. А если / преобразуется в g подстановкой ( а; ( О, 1)), то две функции представляют взаимно дополнительные графы. Следовательно, число ар р-вершинных графов, подсчитываемых с точностью до их взаимной дополнительности, равно числу орбит указанной выше степенной группы. [24]

Изоморфным отображением одного неориентированного графа на другой наз. Графы Gt и G2, представленные на рис., не изоморфны, a Gx и G3 изоморфны. Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом ребер конечно. [25]

Сохранение отношения связности означает, что две точки тогда и только тогда соединены ребром, когда то же самое верно для их образов. Если указанное отображение р существует, то графы Г и Г называются изоморфными, в противном случае они называются гетероморфными. Очевидно, изоморфизм является отношением эквивалентно-сти на множестве графов. Легко проверить, что графы на рис. 92 изоморфны. Изоморфные графы в теории графов не различаются. [26]

Мы уже отмечали, что при фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их дуг. Поэтому может оказаться, что один и тот же граф представляется совсем различными чертежами. Будем говорить, что два графа G и G изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V, что вершины соединены ребрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу. Для нас в дальнейшем всюду будет несущественно, какое именно изображение графа используется, так как все изоморфные графы имеют одни и те же свойства. На рис. 1.2.1 приведены примеры изоморфных графов, образованных ребрами и вершинами правильных многогранников. [27]

Графики зависимости условной ЦФ от числа итераций.| График зависимости времени решения от числа итераций. [28]

Задача распознавания изоморфизма графов является одной из важнейших комбинаторно-логических задач. Проблема определения изоморфизма двух графов, расположенных на плоскости, заключается в получении одного графа из другого путем перенумерации их вершин. Другими словами, необходимо найти подстановку множество вершин, переводящую один граф в другой. Как отмечалось выше, наибольшую трудность при определении изоморфизма представляют однородные графы. Было случайно сгенерировано сто однородных графов, а затем в этих же графах выполнена случайная перестановка их вершин. Следовательно, заранее было известно, что анализируются изоморфные графы, в которых нужно определить подстановку, переводящую один граф в другой. В таблице 7.6 в столбце 2 приведено количество вершин исследуемых графов. В столбце 3 указаны локальные степени вершин графов. [29]

Существует всего один способ присоединения отростка к графу-вершине. Следовательно, в перечне Ь только один элемент - это граф-звено. Так как граф-звено имеет автоморфизм, переставляющий его концы, то при построении Ь2 достаточно применить операцию присоединения отростка лишь для одного конца. Значит, в перечне Ь2 только один граф - это 2-цепь. Следовательно, в перечне Ь3 содержатся два графа; они показаны на рис. 1.7.1. Первый из них - 3-цепь, второй называется - звездой. Очевидно, что для каждого фиксированного п все гс-звезды являются изоморфными графами. Граф-вершина есть 0-звезда, граф-звено - 1-звезда и 2-цепь - 2-звезда. [30]

Страницы: 1 2