Теория графов
2026-02-26 18:54 Diff
https://ru.hexlet.io/courses/graphs/lessons/isomorphism/theory_unit

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

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

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

В обоих графах каждая вершина смежна с каждой другой вершиной, поэтому это две изоморфные копии 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. На втором графе пути другие:
    • Прямой путь по горизонтали в пять вершин
    • Путь в три вершины слева направо с поворотом вверх
    • Путь в три вершины справа налево с поворотом вверх

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