Изоморфизм графов. 
Геометрическая теория графов

Два графа G и G; называются изоморфными (или равными), если между их однотипными элементами можно установить взаимно-однозначные соответствия, сохраняющие отношение инциденции.

Пример. Рассмотрим два графа G и G/, изображенные на рис. 7а и 76. Граф G имеет множество вершин V = {A ₁1 / = 1,2,3,4,5} и множество ребер

Е =, | / = 1,2,3,4,5}, а граф G/ состоит из множества вершин V_x = { В J / = 1,2,3,4,5 j и множества ребер

/>_wc. 7а 76

Определим взаимно-однозначное соответствие I между элементами этих графов при помощи пары отображений /: V —> V_{ и /₂, заданных по формулам:

Легко видеть, что две вершины графа G соединены ребром тогда и только тогда, когда соответствующие вершины графа Gj соединены соответствующим ребром. Поэтому построенное взаимно однозначное соответствие / = (1_Х;1₂) между элементами графов G и G/ сохраняет отношение инциденции. Таким образом, можно утверждать, что графы Сиб/ изоморфны.

Описанное в примере взаимно однозначное соответствие / = (/,; /₂), состоящее из пары отображений // и I2 и обеспечивающее изоморфизм графов, называется отображением изоморфизма G на С/. Таким образом, граф G изоморфен графу G; тогда и только тогда, когда существует отображение изоморфизма G на G/. Для того чтобы доказать, что некоторые графы G и G/ изоморфны, нужно построить конкретное отображение изоморфизма (как в приведенном примере).

Если граф G изоморфен графу G/, то будем использовать обозначение GG/. Бинарное отношение «~» на множестве всех графов является отношением эквивалентности, т. е. удовлетворяет условиям рефлексивности, симметричности и транзитивности:

• 1. G-G- рефлексивность;
• 2. G ~ Gi=> Gi~ G-симметричность;
• 3. G ~ G/ G] ~ G₂ => G ~ G2 - транзитивность. Поэтому множество всех графов распадается на непересекающиеся классы изоморфных графов.

Из определения изоморфизма следует, что изоморфные графы имеют одинаковое количество элементов. Вершины, соответствующие при изоморфизме, имеют одинаковую степень. При отображении изоморфизма петли переходят в петли, а параллельные ребра — в параллельные ребра. Вообще изоморфные графы имеют одинаковые комбинаторные свойства и, с точки зрения теории графов, неразличимы. В частности, изоморфизм графов сохраняет смежность вершин и смежность ребер.

Важно заметить, что не всякое взаимно однозначное соответствие между элементами графов, сохраняющее смежность, является изоморфизмом графов. Действительно, рассмотрим два графа G и G/, изображенные на рис. 8а и 86. Определим взаимно однозначное соответствие / = (/,; /₂) между элементами этих графов по закону:

Рис. 8а

Рис. 86

Это соответствие сохраняет смежность вершин и ребер, но не сохраняет инцидентность (в графе G вершина АI и ребро аз инцидентны, а им соответствующие в графе Gi вершина В/ и ребро b.i — не инцидентны). Следовательно, отображение / = (/,;/₂) не является изоморфизмом графов.

Упражнения

Изоморфны ли пары графов, изображенные на рис.

9−12?

Рис. 10.

Рис. 12.

Ответы и пояснения

На рис. 9 представлены изоморфные графы.

На рис. 10 графы не изоморфны, так как они имеют разное количество ребер.

На рис. 11 графы не изоморфны, так как они имеют разное количество вершин. Кроме того, во втором графе есть петля, а в первом — нет.

На рис.' 12 графы не изоморфны, так как во втором графе есть вершина степени четыре, а в первом графе такой вершины нет.