Изоморфизм графов и инварианты

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

Если для двух графов (7, = (Pj,?,) и G₂ = {у₂, Е_г) существует взаимно однозначное соответствие между Уу и V^, а также между Еу и Есохраняющее отношение инцидентности, то графы Gy и Gj называются изоморфными, что обозначается как (7, s G₂ (рис. 5.9).

В общем случае узнать, изоморфны ли два графа, достаточно сложно. Если буквально следовать определению, то нужно перебрать все биективные отображения и проверить каждое из них, является ли оно изоморфным. Для п вершин имеется л! биекций и эта работа становится практически невыполнимой. Так, если п — 20, что является не очень большим, число биекций составляет уже практически не поддающееся проверке количество вариантов 20! > 210¹⁸.

Рис. 5.9. Изоморфность графов: а — исходный граф, б — граф, изоморфный данному

Однако в ряде случаев изоморфность установить достаточно просто.

Пример. Рассмотрим графы, изображенные на рис. 5.10.

При изоморфизме пара смежных вершин переходит в пару смежных и наоборот. Отсюда: число ребер у двух изоморфных графов должно быть одинаковым. Поэтому графы Gy и Gj неизоморфны. У графов Crj и G$ одинаковое число ребер, но они нсизоморфны, так как изоморфные графы должны иметь одинаковые наборы локальных степеней вершин. Графы Gy и G+ имеют одинаковое количество ребер и одинаковые наборы локальных степеней вершин, но эти графы также неизоморфны. В графе 64 есть цикл длины 3, а в G такого цикла нет. В изоморфных графах каждый цикл определенной длины должен переходить в цикл соответствующей длины.

Рис. 5.10. Неизоморфные графы

Характеристики графов, которые сохраняются при изоморфизме, называются инвариантами. На основе рассмотренного примера инвариантами являются: число ребер, набор локальных степеней вершин, число циклов заданной длины.