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

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

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

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

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

eyJpZCI6IjFiMTRlZTEyMjZjNTBhZWYwMTY4NmI0NWNkNjJkYmFiLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=7d626fded8b5592ba6f1006b7e2f4c97dc8dca66327e92804cdcb08dd8cd3f61

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

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

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

eyJpZCI6IjhhOWY0ZDYwMDVkYjYxNjM3YTg1N2RlM2Y3MmZkN2E2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=880c1f6acd5642293942f54b9c19ff617f6119652a050b9bc8747422eeb1c308

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

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

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

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

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

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

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

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

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

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

eyJpZCI6IjYzOGVjNmQ1MGFhZDMxZTk3NDE2MzM0NmJjNGQ2ZDcxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=34e962360e6e76d63d8300c664b769a61487d29b0562be5a56a3260aa8195d75

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

eyJpZCI6ImZmMjExNzJlNmFmZjU0ZWZlMTI1MDkxYjYyZTFhOTRiLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4abff5823b5ae869fa0aa22c5907547e16fcb863f56b4ac28c1ce705ceaa614b

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

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

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

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

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

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

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

eyJpZCI6IjgyZTI2NmQ2YjM4NTMwYmE2YTFkODlkYmI5YTAyODc4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=c1eb8e98748242b918dceb4e4e23c334556064bdb90844bf0b9dd6ca11573abb

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

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

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

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

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

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

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

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

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

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


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

Задача №1

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

eyJpZCI6IjcyYmFlNzVlZTgwOWNlODc0ZTBiMmQ1NDJjNTM2ZmY4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=f0095bd585f76d3c0540e745b3e5ebcebd947ffc942279369b8bfa982ab06700
Нажмите, чтобы увидеть ответ

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

Задача №2

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

eyJpZCI6IjIzNmRlZDMyOTM2MTJmNGYyMDA5NTg3N2JmYTgxNTM4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=2a93f3b081c22026801bf733f43f3814fef2a38877f57b822d2ae68c6585e53f
Нажмите, чтобы увидеть ответ

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

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

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

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

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

  • Количество ребер в графе

  • Количество ребер в графе

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

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

Задача №3

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

eyJpZCI6IjBmMDcyYTVmZmJjY2Q5MjE4ODliM2U4YTcwZGMyYWE4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4b24f4e1000852c247ed4648123980d8b9c21fd7a5b4f1f9f567d8711d8163ed
Нажмите, чтобы увидеть ответ

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

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

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

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

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

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

  • Количество ребер в графе

  • Количество ребер в графе

  • Количество ребер в графе

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

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

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

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

  • Последовательность степеней графа

  • Последовательность степеней графа

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

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

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

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

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

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

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

eyJpZCI6ImFhYzFiMGQ4NGRjNDUwYjVlMjMxNGYxODM0MTE5N2UyLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=725b32371e316ea4e8e6c6ef3ec639eef9c4250ce317749a3330a1ec74b8ebe7

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

Задача №4

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

eyJpZCI6Ijc5ZjQ4NjY2YTk3MjFmMGEzZjA0NDc4ZTc2Njc1YjMzLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=e657c893db3e90f3c23c83c42bfc73bd405568ceeb9784dd5bfe598e6cdf12ba
Нажмите, чтобы увидеть ответ

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

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

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

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

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

  • Количество ребер в графе

  • Количество ребер в графе

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

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

  • Последовательность степеней графа

  • Последовательность степеней графа

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

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

  • В графе вершины степени образуют цикл длины

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

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

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



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

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

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

Об обучении на Хекслете

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

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

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

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

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

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

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

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

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

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

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

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