Цепь, простая цепь, цикл

Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Под длиной маршрута понимают количество ребер маршрута.

О: Маршрут именуют цепью в случае, когда все его ребра различны. Простой цепью маршрут можно назвать, если все его вершины, за исключением первой и последней, различны.

Так, для графа, изображенного на рис. 38.4 обозначим:

— маршрут, а не цепь, представляет собой непростую цепь, является простой цепью.

О: Цепь, которая предполагает совпадение начальной и конечной вершин, имеет название цикла, в случае, когда цепь простая, — простого цикла.

Рис. 8

Рис. 9.

В частности, всякая петля представляет собой цикл.

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

Составление теории графов связывают с постановкой и решением задачи о Кенигсбергских мостах Эйлером.

Задача. На рис. 10. обозначено расположение мостов. Необходимо пройти каждый мост единожды и вернуться в начальную часть города (суши).

Рис. 10

Рис. 11.

Изобразим участок суши в виде точек а, b, c, d и представим граф задачи (рис. 11). Для обхода мостов характерно соответствие последовательности ребер графа, при этом два соседних ребра соединены общей вершиной, т. е. имеют общий маршрут. Поскольку по окончании обхода необходимо возвратиться в исходную часть города и на каждом мосту находиться единожды, то такой маршрут можно назвать циклом, который включает в себя все ребра графа. Решение задачи предполагает формулировку ответа на вопрос, имеется ли в данном случае такой цикл?

О: Связный неориентированный мультиграф именуют эйлеровым при условии, что имеется цикл, который включает в себя все ребра графа (так называемый эйлеров цикл).

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

Т: Неориентированный связанный мультиграф G является эйлеровым только в случае четности степени его вершин.

В соответствии с теоремой заключим, что для задачи о Кенигсбергских мостах не существует решения в силу того, что для всех вершин характерна нечетная степень. На рис. 12. обозначен Эйлеров граф.

Рис. 12

Рис. 13.

О: Связной неориентированный граф G именуют гамильтоновым в случае, когда имеется простой цикл, который проходит через все вершины графа (так называемый гамильтонов цикл).

На рис. 13 представлен гамильтонов цикл.

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