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

117 Одинаковы ли графы, изображённые на рисунке 20?

а) б) Рисунок 20

Два графа называются одинаковыми или изоморфными, если между их вершинами можно установить взаимно-однозначное соответствие (биекцию), которое сохраняет смежность. Проще говоря, если один граф можно получить из другого, двигая вершины и изгибая рёбра, не разрывая их и не создавая новых.

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

Рассмотрим первую пару графов.

Левый граф:

• Количество вершин: 5.
• Количество рёбер: 5.
• Степени вершин (количество рёбер, выходящих из каждой вершины): есть одна вершина со степенью 3, три вершины со степенью 2 и одна вершина со степенью 1.
• Последовательность степеней: {3, 2, 2, 2, 1}.

Правый граф:

• Количество вершин: 5.
• Количество рёбер: 5.
• Степени вершин: есть одна вершина со степенью 3 (верхняя правая), три вершины четырехугольника со степенью 2 и одна "внутренняя" вершина со степенью 1.
• Последовательность степеней: {3, 2, 2, 2, 1}.

Поскольку количество вершин, рёбер и последовательности степеней у обоих графов совпадают, есть основание полагать, что они одинаковы. Проанализируем их структуру. Оба графа состоят из простого цикла на четырёх вершинах (четырёхугольника) и ещё одной вершины, которая соединена ребром с одной из вершин цикла. В обоих случаях эта "висячая" вершина (степени 1) соединена с вершиной, имеющей наибольшую степень (степень 3). Это подтверждает, что структура графов идентична. Их можно нарисовать одинаково, изменив расположение вершин.

Ответ: да, графы одинаковы.

Рассмотрим вторую пару графов.

Левый граф:

• Количество вершин: 4.
• Количество рёбер: 4.
• Степени вершин: все четыре вершины имеют степень 2.
• Последовательность степеней: {2, 2, 2, 2}.
• Структура: этот граф является циклом $C_4$.

Правый граф:

• Количество вершин: 4.
• Количество рёбер: 3.
• Степени вершин: одна центральная вершина имеет степень 3, а три остальные вершины имеют степень 1.
• Последовательность степеней: {3, 1, 1, 1}.
• Структура: этот граф является звездой $K_{1,3}$.

Сравнивая инварианты, мы видим, что, хотя количество вершин у графов одинаково (4), у них разное количество рёбер (4 у левого и 3 у правого) и совершенно разные последовательности степеней. Наличие хотя бы одного такого различия уже достаточно, чтобы сделать вывод о том, что графы не являются одинаковыми.

Ответ: нет, графы не одинаковы.