Теория: Изоморфизм

Термин «изоморфизм» буквально означает «одинаковая форма». Он встречается во многих отраслях математики, в том числе в теории графов. В этом уроке мы узнаем, что означает этот термин. Вы научитесь определять изоморфные графы и доказывать свою точку зрения математически.

Что такое изоморфные графы

Два графа изоморфны, если это один и тот же граф, просто нарисованный или представленный по-другому. Например, на этом рисунке показаны два графа, которые изоморфны друг другу:

В обоих графах каждая вершина смежна с каждой другой вершиной, поэтому это две изоморфные копии K4.

Для такого простого примера несложно представить себе превращение одного графа в другой — надо просто переставить вершины местами. Но для графов с большим числом вершин такой подход не сработает.

На самом деле довольно сложно показать, что большие графы изоморфны. Например, здесь все три графа изоморфны, но это неочевидно с первого взгляда:

В таких неочевидных случаях мы можем математически доказать, изоморфны графы друг другу или нет.

Как доказать изоморфность графов

Чтобы доказать изоморфность, рассмотрим ее определение:

Графы G и H изоморфны, в функции f: V(G) → V(H) соблюдаются два условия одновременно:

• v является смежным с w в G
• f (v) является смежным с f (w) в H

Другими словами, два графа считаются изоморфными, если мы можем идеально сопоставить вершины одного графа с вершинами другого. При этом смежность тоже должна совпадать:

• Если две вершины были смежными в первом графе, во втором они тоже должны быть смежными
• Если две вершины не были смежными в первом графе, во втором они тоже не должны быть смежными

Попробуем применить это определение на практике и доказать изоморфность этих графов:

Для этого мы сопоставляем вершины следующим образом:

• a ↔ v
• b ↔ w
• c ↔ x
• d ↔ z
• e ↔ y

Так это выглядит в виде функции:

• f(a) = v
• f(b) = w
• f(c) = x
• f(d) = z
• f(e) = y

С вершинами разобрались, осталось проверить, все ли ребра совпадают:

• Возьмем ребро ab в первом графе
• Вспоминаем, что вершины a и b сопоставлены с v и w
• Проверяем, есть ли ребро vw во втором графе
• Такое ребро есть, так что можно идти дальше

Таким же образом проверяем не-ребра:

• Посмотрим на первый граф и выясним, что на нем нет ребра от a до e
• Вспоминаем, что вершины a и e сопоставлены с v и y
• Проверяем, есть ли ребро vy во втором графе
• Такого ребра нет, так что можно идти дальше

Эта проверка может показать долгой и утомительной, но таким образом можно точно проверить все ребра и не-ребра.

Эту работу можно ускорить с помощью алгоритмов графов, но это отдельная сфера математики, о которой пока мы не будем говорить подробно.

Как доказать неизоморфность графов

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

Например, два графа могут отличаться такими свойствами:

• Разное количество вершин или ребер
• Разное количество компонент
• Степени вершин в каждом графе
• Содержание абсолютно одинаковых подграфов

Чтобы лучше понять эти свойства, рассмотрим такой пример:

В этом примере графы имеют такие свойства:

• Одинаковое количество вершин и ребер
• Одна компонента в обоих случаях
• По две вершины степени 1, три вершины степени 2, две вершины степени 3 и одной вершине степени 4

Таким образом, первые три свойства не помогают. Однако нам на помощь приходит четвертое свойство: в первом графе нет треугольника-подграфа, а во втором — он есть.

Существует множество других возможностей доказать неизоморфность. Иногда для этого требуется немного творчества.

Например, вот эти графы неизоморфны:

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

К этому же примеру можно подойти по-другому:

1. На первом графе есть два пути длиной в пять вершин:
   • Прямой путь по горизонтали
   • Путь справа налево с поворотом вверх
2. На втором графе пути другие:
   • Прямой путь по горизонтали в пять вершин
   • Путь в три вершины слева направо с поворотом вверх
   • Путь в три вершины справа налево с поворотом вверх

В этом уроке мы разобрали изоморфизм в теории графов. Теперь вы умеете доказывать изормфность и неизоморфность графов даже в тех случаях, когда это неочевидно с первого взгляда.