Термин «изоморфизм» буквально означает «одинаковая форма». Он встречается во многих отраслях математики, в том числе в теории графов. В этом уроке мы узнаем, что означает этот термин. Вы научитесь определять изоморфные графы и доказывать свою точку зрения математически.
Что такое изоморфные графы
Два графа изоморфны, если это один и тот же граф, просто нарисованный или представленный по-другому. Например, на этом рисунке показаны два графа, которые изоморфны друг другу:
В обоих графах каждая вершина смежна с каждой другой вершиной, поэтому это две изоморфные копии .
Для такого простого примера несложно представить себе превращение одного графа в другой — надо просто переставить вершины местами. Но для графов с большим числом вершин такой подход не сработает.
На самом деле довольно сложно показать, что большие графы изоморфны. Например, здесь все три графа изоморфны, но это неочевидно с первого взгляда:
В таких неочевидных случаях мы можем математически доказать, изоморфны графы друг другу или нет.
Как доказать изоморфность графов
Чтобы доказать изоморфность, рассмотрим ее определение:
Графы и изоморфны, в функции соблюдаются два условия одновременно:
-
является смежным с в
-
является смежным с в
Другими словами, два графа считаются изоморфными, если мы можем идеально сопоставить вершины одного графа с вершинами другого. При этом смежность тоже должна совпадать:
-
Если две вершины были смежными в первом графе, во втором они тоже должны быть смежными
-
Если две вершины не были смежными в первом графе, во втором они тоже не должны быть смежными
Попробуем применить это определение на практике и доказать изоморфность этих графов:
Для этого мы сопоставляем вершины следующим образом:
Так это выглядит в виде функции:
С вершинами разобрались, осталось проверить, все ли ребра совпадают:
-
Возьмем ребро в первом графе
-
Вспоминаем, что вершины и сопоставлены с и
-
Проверяем, есть ли ребро во втором графе
-
Такое ребро есть, так что можно идти дальше
Таким же образом проверяем не-ребра:
-
Посмотрим на первый граф и выясним, что на нем нет ребра от до
-
Вспоминаем, что вершины и сопоставлены с и
-
Проверяем, есть ли ребро во втором графе
-
Такого ребра нет, так что можно идти дальше
Эта проверка может показать долгой и утомительной, но таким образом можно точно проверить все ребра и не-ребра.
Эту работу можно ускорить с помощью алгоритмов графов, но это отдельная сфера математики, о которой пока мы не будем говорить подробно.
Как доказать неизоморфность графов
Как мы увидели на примере выше, изоморфность доказать не всегда легко. С другой стороны, доказать неизоморфность двух графов обычно проще — нужно найти свойство, которое эти два графа не разделяют.
Например, два графа могут отличаться такими свойствами:
-
Разное количество вершин или ребер
-
Разное количество компонент
-
Степени вершин в каждом графе
-
Содержание абсолютно одинаковых подграфов
Чтобы лучше понять эти свойства, рассмотрим такой пример:
В этом примере графы имеют такие свойства:
-
Одинаковое количество вершин и ребер
-
Одна компонента в обоих случаях
-
По две вершины степени , три вершины степени , две вершины степени и одной вершине степени
Таким образом, первые три свойства не помогают. Однако нам на помощь приходит четвертое свойство: в первом графе нет треугольника-подграфа, а во втором — он есть.
Существует множество других возможностей доказать неизоморфность. Иногда для этого требуется немного творчества.
Например, вот эти графы неизоморфны:
Обратите внимание, что у них одинаковое количество вершин и ребер, степени почти всех вершин тоже одинаковы. Определим, в чем разница между ними. Второй граф содержит вершину степени , смежную с двумя вершинами степени — в первом графе это не так.
К этому же примеру можно подойти по-другому:
-
На первом графе есть два пути длиной в пять вершин:
-
Прямой путь по горизонтали
-
Путь справа налево с поворотом вверх
-
-
На втором графе пути другие:
-
Прямой путь по горизонтали в пять вершин
-
Путь в три вершины слева направо с поворотом вверх
-
Путь в три вершины справа налево с поворотом вверх
-
В этом уроке мы разобрали изоморфизм в теории графов. Теперь вы умеете доказывать изормфность и неизоморфность графов даже в тех случаях, когда это неочевидно с первого взгляда.
Самостоятельная работа
Задача №1
Являются ли следующие два графа изоморфными?
Нажмите, чтобы увидеть ответ
Оба графа имеют вершин, ребер. Последовательность степеней одинакова. Однако во втором графе есть цепь длины , а минимальная длина любой цепи в первом графе равна . Следовательно, данные графы не изоморфны.
Задача №2
Являются ли следующие два графа изоморфными?
Нажмите, чтобы увидеть ответ
Проверим необходимые условия. Начнем с условия 1:
-
Количество вершин в графе —
-
Количество вершин в графе —
Здесь оба графа и имеют одинаковое количество вершин. Таким образом, условие 1 удовлетворяется.
Проверим условие 2:
-
Количество ребер в графе
-
Количество ребер в графе
Здесь оба графа и имеют разное количество ребер. Таким образом, условие 2 нарушается.
Поскольку условие 2 нарушается, данные графы не могут быть изоморфными. и не являются изоморфными графами.
Задача №3
Какие из следующих графов изоморфны?
Нажмите, чтобы увидеть ответ
Шаг 1. Проверим необходимые условия. Начнем с условия 1:
-
Количество вершин в графе
-
Количество вершин в графе
-
Количество вершин в графе
Здесь все графы и имеют одинаковое количество вершин. Таким образом, условие 1 удовлетворяется.
Шаг 2. Проверим условие 2:
-
Количество ребер в графе
-
Количество ребер в графе
-
Количество ребер в графе
Здесь графы и имеют одинаковое количество ребер. Таким образом, условие 2 удовлетворяется для графов и . Однако графы и имеют разное количество ребер. Значит, условие 2 нарушается для графов и .
Поскольку условие 2 нарушается для графов и , они не могут быть изоморфными. не изоморфен ни , ни .
Так как условие 2 удовлетворяется для графов и , то они могут быть изоморфны. может быть изоморфен .
Шаг 3. Теперь продолжим проверку для графов и . Проверим условие 3:
-
Последовательность степеней графа
-
Последовательность степеней графа
Здесь оба графа и имеют одинаковую последовательность степеней. Таким образом, условие 3 удовлетворяется.
Шаг 4. Проверим условие 4:
-
Оба графа содержат два цикла длиной каждый, образованные вершинами со степенями .
Это означает, что оба графа и имеют одинаковые циклы. Таким образом, условие 4 удовлетворяется.
Таким образом, все 4 необходимых условия выполнены. Значит, графы и могут быть изоморфны.
Шаг 5. Теперь давайте проверим достаточное условие. Мы знаем, что два графа обязательно изоморфны тогда и только тогда, когда изоморфны их комплементарные графы.
Итак давайте построим графы дополнения графов и :
Очевидно, что дополняющие графы и изоморфны. Графы и являются изоморфными графами.
Задача №4
Являются ли следующие два графа изоморфными?
Нажмите, чтобы увидеть ответ
Шаг 1. Проверим необходимые условия. Начнем с условия 1:
-
Количество вершин в графе
-
Количество вершин в графе
Здесь оба графа и имеют одинаковое количество вершин. Таким образом, условие 1 удовлетворяется.
Шаг 2. Проверим условие 2:
-
Количество ребер в графе
-
Количество ребер в графе
Здесь оба графа и имеют одинаковое количество ребер. Таким образом, условие 2 удовлетворяется.
Шаг 3. Проверим условие 3:
-
Последовательность степеней графа
-
Последовательность степеней графа
Здесь оба графа и имеют одинаковую последовательность степеней. Таким образом, условие 3 удовлетворяется.
Шаг 4. Проверим условие 4:
-
В графе вершины степени образуют цикл длины
-
В графе вершины степени не образуют -цикл, так как вершины не являются смежными
Здесь оба графа и не содержат одинаковых циклов. Значит, условие 4 нарушается.
Поскольку условие 4 нарушается, данные графы не могут быть изоморфными. и не являются изоморфными графами.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
