Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

2 <h2>Что такое изоморфные графы</h2>

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

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

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

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

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

8 <h2>Как доказать изоморфность графов</h2>

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

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

11 <ul><li>v является смежным с w в G</li>

12 <li>f (v) является смежным с f (w) в H</li>

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

14 <ul><li>Если две вершины были смежными в первом графе, во втором они тоже должны быть смежными</li>

15 <li>Если две вершины не были смежными в первом графе, во втором они тоже не должны быть смежными</li>

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

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

18 <ul><li>a ↔ v</li>

19 <li>b ↔ w</li>

20 <li>c ↔ x</li>

21 <li>d ↔ z</li>

22 <li>e ↔ y</li>

23 </ul>Так это выглядит в виде функции:

24 <ul><li>f(a) = v</li>

25 <li>f(b) = w</li>

26 <li>f(c) = x</li>

27 <li>f(d) = z</li>

28 <li>f(e) = y</li>

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

30 <ul><li>Возьмем ребро ab в первом графе</li>

31 <li>Вспоминаем, что вершины a и b сопоставлены с v и w</li>

32 <li>Проверяем, есть ли ребро vw во втором графе</li>

33 <li>Такое ребро есть, так что можно идти дальше</li>

34 </ul>Таким же образом проверяем не-ребра:

35 <ul><li>Посмотрим на первый граф и выясним, что на нем нет ребра от a до e</li>

36 <li>Вспоминаем, что вершины a и e сопоставлены с v и y</li>

37 <li>Проверяем, есть ли ребро vy во втором графе</li>

38 <li>Такого ребра нет, так что можно идти дальше</li>

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

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

41 <h2>Как доказать неизоморфность графов</h2>

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

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

44 <ul><li>Разное количество вершин или ребер</li>

45 <li>Разное количество компонент</li>

46 <li>Степени вершин в каждом графе</li>

47 <li>Содержание абсолютно одинаковых подграфов</li>

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

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

50 <ul><li>Одинаковое количество вершин и ребер</li>

51 <li>Одна компонента в обоих случаях</li>

52 <li>По две вершины степени 1, три вершины степени 2, две вершины степени 3 и одной вершине степени 4</li>

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

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

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

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

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

58 <ol><li>На первом графе есть два пути длиной в пять вершин:<ul><li>Прямой путь по горизонтали</li>

59 <li>Путь справа налево с поворотом вверх</li>

60 </ul></li>

61 <li>На втором графе пути другие:<ul><li>Прямой путь по горизонтали в пять вершин</li>

62 <li>Путь в три вершины слева направо с поворотом вверх</li>

63 <li>Путь в три вершины справа налево с поворотом вверх</li>

64 </ul></li>

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