Изоморфизм
Два графа
называются изоморфными, если существует взаимно однозначное соответствие
, такое, что
тогда и только тогда, если
, то есть существует соответствие между вершинами графа
и вершинами графа
, сохраняющее отношение смежности. Например, на рис. 12.2 показаны два изоморфных орграфа: вершины
в орграфе
соответствуют вершинам 2, 3, 6, 1, 4, 5 в указанном порядке в орграфе
. Вообще говоря, между
и
может быть более чем одно соответствие, и на рис. 12.3 графы имеют на самом деле второй изоморфизм:
соответствуют в указанном порядке вершинам 2, 3, 6, 1, 5, 4. Изоморфные графы отличаются только метками вершин, в связи с чем задача определения изоморфизма возникает в ряде практических ситуаций, таких, как информационный поиск и определение химических соединений.
Заметим, что можно ограничится орграфами. Любой неориентированный граф превращается в орграф заменой каждого ребра двумя противоположно направленными ребрами. Два полученные таким образом орграфа, очевидно, изоморфны тогда и только тогда, если изоморфны исходные графы.
Рис. 12.3. Изоморфные орграфы
Содержание раздела
