Номер 3, страница 81, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

3 Как можно проверить, одинаковы два графа или нет?

Проверка того, являются ли два графа одинаковыми, в математике называется задачей об изоморфизме графов. Два графа $G_1 = (V_1, E_1)$ и $G_2 = (V_2, E_2)$ считаются одинаковыми (изоморфными), если между их вершинами можно установить взаимно-однозначное соответствие (биекцию) $f: V_1 \to V_2$, которое сохраняет смежность. Это значит, что ребро между вершинами $u$ и $v$ существует в графе $G_1$ тогда и только тогда, когда существует ребро между соответствующими вершинами $f(u)$ и $f(v)$ в графе $G_2$.

Процесс проверки можно разбить на два основных этапа.

1. Проверка необходимых условий (с помощью инвариантов)

Инвариант графа — это свойство, которое не меняется при любом изоморфном преобразовании. Если два графа изоморфны, их инварианты должны совпадать. Это самый быстрый способ доказать, что графы разные. Если хотя бы один инвариант не совпадает, графы точно не изоморфны. Основные инварианты для проверки:

• Число вершин: Количество вершин в обоих графах должно быть одинаковым: $|V_1| = |V_2|$.
• Число ребер: Количество ребер также должно совпадать: $|E_1| = |E_2|$.
• Последовательность степеней вершин: Набор степеней всех вершин одного графа (мультимножество) должен быть таким же, как и у другого. Например, если в одном графе есть три вершины со степенями (2, 2, 3), то и в другом должен быть такой же набор степеней.
• Число компонент связности: Если один граф связный, а другой нет, они не изоморфны.
• Наличие и количество циклов определенной длины: Например, количество треугольников (циклов длины 3) или квадратов (циклов длины 4) в графах должно быть одинаковым.

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

Ответ: На первом этапе сравниваются простые характеристики графов (инварианты), такие как число вершин, ребер и распределение степеней вершин. Если они не совпадают, графы не одинаковы.

2. Поиск изоморфизма (достаточное условие)

Если все простые инварианты совпали, необходимо попытаться построить само отображение $f$, которое докажет изоморфизм. Для небольших графов это можно сделать методом перебора. Алгоритм действий следующий:

1. Выберите вершину $u_1$ в графе $G_1$.
2. Найдите в графе $G_2$ все вершины, которые могут соответствовать $u_1$. Это вершины, имеющие ту же степень, что и $u_1$ (и, возможно, другие совпадающие инварианты, например, количество треугольников, в которые они входят). Выберите одну из них, пусть это будет вершина $v_1$. Устанавливаем пробное соответствие $f(u_1) = v_1$.
3. Рассмотрим соседей вершины $u_1$ в $G_1$ и соседей вершины $v_1$ в $G_2$. Попытайтесь установить соответствие между этими группами соседей, снова учитывая их степени и связи между ними.
4. Продолжайте этот процесс рекурсивно для всех вершин. Если на каком-то шаге вы приходите к противоречию (например, вершине нужно сопоставить две разные вершины или нарушается условие смежности), вернитесь на шаг назад и попробуйте другое соответствие (этот метод называется поиском с возвратом или бэктрекингом).
5. Если удалось построить полное взаимно-однозначное соответствие для всех вершин, сохраняющее смежность, то графы изоморфны.
6. Если были перебраны все возможные начальные соответствия и ни одно не привело к успеху, то графы не изоморфны.

Стоит отметить, что задача проверки изоморфизма графов в общем виде является вычислительно сложной. Для нее до сих пор не найден алгоритм, работающий за полиномиальное время (класс P), но она и не доказана как NP-полная.

Ответ: На втором, основном этапе, осуществляется попытка прямого построения отображения вершин одного графа на вершины другого с сохранением структуры связей. Если такое отображение найдено — графы одинаковы (изоморфны); если после полного перебора вариантов отображение не найдено — графы различны.