Комбинаторные алгоритмы для программистов


Изоморфизм


Два графа

G_A = (V_A,E_A ),G_B = (V_B,E_B )
называются изоморфными, если существует взаимно однозначное соответствие
f:V_A \to V_B
, такое, что
(v,w) \in E_A
тогда и только тогда, если
(f(v),f(w)) \in E_B
, то есть существует соответствие между вершинами графа
G_A
и вершинами графа
G_B
, сохраняющее отношение смежности. Например, на рис. 12.2 показаны два изоморфных орграфа: вершины
a,b,c,d,e,f
в орграфе
G_2
соответствуют вершинам 2, 3, 6, 1, 4, 5 в указанном порядке в орграфе
G_1^{}
. Вообще говоря, между
V_A
и
V_B
может быть более чем одно соответствие, и на рис. 12.3 графы имеют на самом деле второй изоморфизм:
a,b,c,d,e,f
соответствуют в указанном порядке вершинам 2, 3, 6, 1, 5, 4. Изоморфные графы отличаются только метками вершин, в связи с чем задача определения изоморфизма возникает в ряде практических ситуаций, таких, как информационный поиск и определение химических соединений.

Заметим, что можно ограничится орграфами. Любой неориентированный граф превращается в орграф заменой каждого ребра двумя противоположно направленными ребрами. Два полученные таким образом орграфа, очевидно, изоморфны тогда и только тогда, если изоморфны исходные графы.

Изоморфные орграфы

Рис. 12.3.  Изоморфные орграфы




Начало  Назад  Вперед



Книжный магазин