Урок-практикум "Пути и циклы в графе"

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

Цикл – это путь, у которого начальная и конечная вершины совпадают. Длина цикла – это число рёбер в этом цикле. Простой цикл – это цикл, который проходит через каждую вершину не более одного раза.

Указание. Необходимо привести наглядный пример пути, цикла и простого цикла. Рассмотрим рисунок 45. В этом графе пути – это, например, и циклы – это, например, и простые циклы – это, например, и

Рисунок 45 – Пример графа для поиска пути, цикла, простого цикла.

Утверждение. Если в графе есть цикл, то в нём есть и простой цикл.

Задача 1. (Задача на проверку базового понимания, что такое цикл в графе). Рассмотрим граф, изображённый на рисунке 46. Какие вершины этого графа содержатся хотя бы в одном простом цикле длины четыре?

Рисунок 46 – Граф для задачи 1.

Решение: Посмотрим на наш граф. Сразу обращаем внимание на то, что в нём есть простой цикл длины Значит вершины участвуют хотя бы в этом цикле. Осталось понять, участвуют ли оставшиеся вершины в простом цикле длины

Вершины имеют степени два. Они соединены между собой, а ещё каждая из них соединена с вершиной Поэтому если бы, например, вершина участвовала в простом цикле длины то вершины и точно в нём участвовали бы. Но при этом, из вершины выходит только одно ребро То есть рёбра и должны участвовать в этом цикле. Но они участвуют в простом цикле длины а не длины Значит, вершины и точно не участвуют в цикле длины

Задача 2. (Задача на проверку базового понимания, что такое цикл в графе, и на аккуратный подсчёт количества циклов). Сколько существует простых циклов длины четыре в полном графе с пятью вершинами?

Решение. Нарисуем полный граф с пятью вершинами (см. рисунок 47).

Рисунок 47 – Полный граф на пяти вершинах.

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

Рисунок 48 – Полный граф на четырёх вершинах.

В данном полном графе на четыре вершины нужно выбрать те ребра, которые будут образовывать простой цикл длины Существует несколько способов выбора таких рёбер.

Во-первых, можем в качестве простого цикла выбрать стороны четырёхугольника. Получим цикл, изображённый на рисунке 49.

Рисунок 49 – Простой цикл длины

Во-вторых, предположим, что какое-то одно ребро не участвует в образовании цикла. Тогда получатся другие варианты простого цикла длины (см. рисунок 50).

Рисунок 50 – Простые циклы длины

Таким образом, в полном графе на вершины есть способа выбора простого цикла длины

Теперь вернемся к полному графу с пятью вершинами. У нас есть пять способов выбора полного графа с четырьмя вершинами. Для каждого такого графа есть способа выбора простого цикла длины Получаем всего способов.