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

Cтраница 1

Случай, при котором алгоритм неэффективен. [1]

Изоморфные графы отличаются только метками вершин, в связи с чем задача определения изоморфизма возникает в ряде практических ситуаций, таких, как информационный поиск и определение химических соединений. [2]

Изоморфные графы могут быть получены один из другого путем перенумерации их вершин. Очевидно, что изоморфизм есть отношение эквивалентности на графах. Если изоморфные преобразования проводятся с графом, заданным матрицей смежности, то они сводятся к перестановке местами соответствующих строк и столбцов. Известно, что в общем случае для определения изоморфизма графов необходимо сделать п сравнений или перестановок строк и столбцов матрицы, что для графов с п30 не под силу даже современной ЭВМ. Поэтому необходимо применить тот или иной эвристический алгоритм поиска по дереву решений. [3]

Обычно изоморфные графы не различаются между собой. [4]

Изоморфные графы. [5]

Под изоморфными графами, мы, естественно, понимаем два графа G и G при условии, что множество К вершин k графа G идентично множеству К. [6]

Теорема 1.3. Изоморфные графы имеют изоморфные группы автоморфизмов. [7]

Гиперграф с группой автоморфизмов порядка 12. [8]

По существу изоморфные графы отличаются лишь нумерацией вершин. [9]

Из определения изоморфизма следует, что изоморфные графы отличаются друг от Друга только упорядоченностью в обозначениях вершин. Однако перенумерация вершин не изменяет полустепени исхода s и полустепени захода р каждой вершины. [10]

Очевидно, что гомоморфные мографы имеют изоморфные графы пересечений. Отсюда следует, что два гомоморфных мографа одновременно либо хордовые, либо не хордовые. [11]

Из приведенного здесь определения следует, что изоморфные графы отличаются лишь нумерацией их вершин. [12]

Теперь легко разбить составной граф G на изоморфные графы G, именно отнесем граф G. [13]

С точки зрения этого понятия абстрактный граф и его геометрическая реализация являются изоморфными графами. [14]

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

Страницы: 1 2