Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

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

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

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

eyJpZCI6ImVhZjk0NDc3ZWJlNzIxNjJlNzZjMjUyNGRiZGRiNmRiLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=136afe73ec2774d044e1b716f63c83f2ad061f965f01acb67765749c34b7f26f

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

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

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

eyJpZCI6IjhiY2FkYjhlNTFjZGJjNGY1NjY4YmNkNWNhNGJkOWM2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=576f46ed9b0ec7fda4c78972ef096dba10735355141e7480c52b4f996601d5cb

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

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

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

Графы и изоморфны, в функции соблюдаются два условия одновременно:

  • является смежным с в

  • является смежным с в

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

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

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

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

eyJpZCI6ImI5NTQ2OGIyNjg4MzBkMjhkMGMyZjJkYzk2M2NiNzlhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=ea3f6dce61d4c21f097912aa06acbf1cd6e6972e74f7ab4d94eaa7387f0e5454

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

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

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

  • Возьмем ребро в первом графе

  • Вспоминаем, что вершины и сопоставлены с и

  • Проверяем, есть ли ребро во втором графе

  • Такое ребро есть, так что можно идти дальше

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

  • Посмотрим на первый граф и выясним, что на нем нет ребра от до

  • Вспоминаем, что вершины и сопоставлены с и

  • Проверяем, есть ли ребро во втором графе

  • Такого ребра нет, так что можно идти дальше

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

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

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

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

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

  • Разное количество вершин или ребер

  • Разное количество компонент

  • Степени вершин в каждом графе

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

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

eyJpZCI6ImY3ZjM3ZmVhZjk4Nzg0MjAzZjNkNzU0ZWNmN2Q0NjQ2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=cdcd3ea235cb2a0cafb006eac84544158696ba441847ce858f1236f08402adb5

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

  • Одинаковое количество вершин и ребер

  • Одна компонента в обоих случаях

  • По две вершины степени , две вершины степени и четыре вершин степени

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

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

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

eyJpZCI6IjViN2E0NzU0ZmQzNWY0Mzg3ODM5YzkzM2M3YzdhZjE3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=7c0c2f315aef7a866b2e24ee8ab6d1c4911cbc0789e944eba167ce6670433a92

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

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

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

    • Прямой путь по горизонтали

    • Путь справа налево с поворотом вверх

  2. На втором графе пути другие:

    • Прямой путь по горизонтали в пять вершин

    • Путь в три вершины слева направо с поворотом вверх

    • Путь в три вершины справа налево с поворотом вверх

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


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

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

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

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

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

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

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

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

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

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

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

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»

Изображение Тото

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