Зарегистрируйтесь, чтобы продолжить обучение

Изоморфизм Теория графов

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

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

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

isomorphism-1

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

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

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

isomorphism-2

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

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

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

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

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

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

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

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

isomorphism-3

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

  • 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 во втором графе
  • Такого ребра нет, так что можно идти дальше

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

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

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

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

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

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

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

isomorphism-4

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

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

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

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

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

isomorphism-5

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

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

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

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


Самостоятельная работа

Задача №1

Являются ли следующие два графа изоморфными?

400

Оба графа имеют 6 вершин, 9 ребер. Последовательность степеней одинакова. Однако во втором графе есть цепь длины 3, а минимальная длина любой цепи в первом графе равна 4. Следовательно, данные графы не изоморфны.

Задача №2

Являются ли следующие два графа изоморфными?

401

Проверим необходимые условия. Начнем с условия 1:

  • Количество вершин в графе — G1 = 4
  • Количество вершин в графе — G2 = 4

Здесь оба графа G1 и G2 имеют одинаковое количество вершин. Таким образом, условие 1 удовлетворяется.

Проверим условие 2:

  • Количество ребер в графе G1 = 5
  • Количество ребер в графе G2 = 6

Здесь оба графа G1 и G2 имеют разное количество ребер. Таким образом, условие 2 нарушается.

Поскольку условие 2 нарушается, данные графы не могут быть изоморфными. G1 и G2 не являются изоморфными графами.

Задача №3

Какие из следующих графов изоморфны?

402

Шаг 1. Проверим необходимые условия. Начнем с условия 1:

  • Количество вершин в графе G1 = 4
  • Количество вершин в графе G2 = 4
  • Количество вершин в графе G3 = 4

Здесь все графы G1, G2 и G3 имеют одинаковое количество вершин. Таким образом, условие 1 удовлетворяется.

Шаг 2. Проверим условие 2:

  • Количество ребер в графе G1 = 5
  • Количество ребер в графе G2 = 5
  • Количество ребер в графе G3 = 4

Здесь графы G1 и G2 имеют одинаковое количество ребер. Таким образом, условие 2 удовлетворяется для графов G1 и G2. Однако графы (G1, G2) и G3 имеют разное количество ребер. Значит, условие 2 нарушается для графов (G1, G2) и G3.

Поскольку условие 2 нарушается для графов (G1, G2) и G3, они не могут быть изоморфными. G3 не изоморфен ни G1, ни G2.

Так как условие 2 удовлетворяется для графов G1 и G2, то они могут быть изоморфны. G1 может быть изоморфен G2.

Шаг 3. Теперь продолжим проверку для графов G1 и G2. Проверим условие 3:

  • Последовательность степеней графа G1 = { 2 , 2 , 3 , 3 }
  • Последовательность степеней графа G2 = { 2 , 2 , 3 , 3 }

Здесь оба графа G1 и G2 имеют одинаковую последовательность степеней. Таким образом, условие 3 удовлетворяется.

Шаг 4. Проверим условие 4:

  • Оба графа содержат два цикла длиной 3 каждый, образованные вершинами со степенями { 2 , 3 , 3 }.

Это означает, что оба графа G1 и G2 имеют одинаковые циклы. Таким образом, условие 4 удовлетворяется.

Таким образом, все 4 необходимых условия выполнены. Значит, графы G1 и G2 могут быть изоморфны.

Шаг 5. Теперь давайте проверим достаточное условие. Мы знаем, что два графа обязательно изоморфны тогда и только тогда, когда изоморфны их комплементарные графы.

Итак давайте построим графы дополнения графов G1 и G2:

403

Очевидно, что дополняющие графы G1 и G2 изоморфны. Графы G1 и G2 являются изоморфными графами.

Задача №4

Являются ли следующие два графа изоморфными?

404

Шаг 1. Проверим необходимые условия. Начнем с условия 1:

  • Количество вершин в графе G1 = 8
  • Количество вершин в графе G2 = 8

Здесь оба графа G1 и G2 имеют одинаковое количество вершин. Таким образом, условие 1 удовлетворяется.

Шаг 2. Проверим условие 2:

  • Количество ребер в графе G1 = 10
  • Количество ребер в графе G2 = 10

Здесь оба графа G1 и G2 имеют одинаковое количество ребер. Таким образом, условие 2 удовлетворяется.

Шаг 3. Проверим условие 3:

  • Последовательность степеней графа G1 = { 2 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 }
  • Последовательность степеней графа G2 = { 2 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 }

Здесь оба графа G1 и G2 имеют одинаковую последовательность степеней. Таким образом, условие 3 удовлетворяется.

Шаг 4. Проверим условие 4:

  • В графе G1 вершины степени 3 образуют цикл длины 4
  • В графе G2 вершины степени 3 не образуют 4-цикл, так как вершины не являются смежными

Здесь оба графа G1 и G2 не содержат одинаковых циклов. Значит, условие 4 нарушается.

Поскольку условие 4 нарушается, данные графы не могут быть изоморфными. G1 и G2 не являются изоморфными графами.



Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff