Маршруты на графах

Пусть дан неориентированный граф G (X, ?). Маршрутом длины т называется некоторая последовательность т ребер графа G (X, Е), такая что вершины двух соседних ребер последовательности совпадают. Примерами маршрутов на графе, изображенном на рис. 16.2, могут служить последовательности ребер (а_х, а₆, а₅, а_1; а₃) и (а₂, а_х, а₄, а₃). Первый из них проходит последовательно через вершины х_х, х₂, х₃, х₂, х_х, х₃, соединяя х_х с х₃. Второй, проходя через вершины х₂, х_х, х₂, х₃, х₂, образует замкнутый маршрут, так как приводит в ту же вершину, из которой и начался.

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

Маршрут, все ребра которого различны, называется цепью. Цепь, проходящая через различные вершины, называется простой (элементарной) цепью. Замкнутая цепь называется циклом, а цикл, проходящий через различные вершины — простым циклом. Так, в графе, изображенном на рис. 16.2, маршрут (а_х, а₅, а₈) является простой цепью, маршрут (а₂, а₅, а₆, а_х) — циклом.

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

Цикл, содержащий все ребра графа, называется эйлеровым, а граф, имеющий эйлеров цикл, называется эйлеровым графом. Если эйлеров граф — плоский, то его можно изобразить одним росчерком пера (не отрывая пера от бумаги), причем начальная и конечная вершины совпадут. На рис. 16.6 изображен граф, обход всех ребер которого ровно один раз возможен по маршруту «1, сс₂, а₃, а₄, а₅, oig, ос₇.

Вопрос о существовании эйлерова графа разрешается следующей теоремой.

Рис. 16.6. Эйлеров граф.

Теорема 16.1 [2]. Конечный неориентированный граф эйлеров тогда и только тогда, когда он связан и степени всех его вершин четны.

Так, граф изображенный на рис 16.6, эйлеров, так как степени его вершин х_ь х₂ и х₄ — 2, вершин х₃ и х₅ — 4.

Простой цикл, который проходит через все вершины графа, называется гамильтоновым (назван в честь ирландского математика У. Р. Гамильтона, 1805—1865). Условий, гарантирующих существование в графе гамильтонова цикла, не установлено. Это обстоятельство существенно усложняет нахождение ответа в очень многих задачах, решение которых сводится к нахождению гамильтонова цикла. Наиболее известна так называемая задача коммивояжера, или задача о странствующем торговце, состоящая в следующем. Пусть имеется несколько связанных между собой пунктов (городов). Выходя из фиксированного пункта, коммивояжер должен вернуться в него, посетив все пункты ровно один раз. Обычно задача усложняется введением дополнительного ограничения, например пройти маршрут за самое короткое время или с минимальными затратами на транспорт.

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

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

Рис. 16.7. Граф, имеющий гамильтонов цикл.

Рис. 16.8. Граф, не имеющий гамильтонова цикла.

При помощи ориентированного графа удобно задавать бинарные отношения, например отношения порядка. Говорят, что на ориентированном графе D (X, А) задано отношение порядка, если для любых двух вершин х, и худовлетворяющих условию х, — > Xj, существует путь из х, — в х_}. Для отношения порядка характерны три свойства: рефлексивность, антисимметричность и транзитивность. С позиций теории графов эти свойства можно интерпретировать следующим образом.

• 1. Рефлексивность означает истинность условия х, — < х₍. Следовательно, вершинах, не больше самой себя, т. е. имеется путь изх, в х" что обусловливает допустимость петли для вершины х,.
• 2. Антисимметричность (х, — < х_;) л (х_; < х,) —" (х, — = х_;) показывает, что если на графе имеется путь из х, в х_;, то имеется и путь из Xj в X/. Таким образом, в таком графе имеется контур.
• 3. Транзитивность отношения «быть не больше» означает истинность выражения (х_; < xj) л (х, — < x_k) —> (х, — < x_k). Транзитивность эквивалентна тому, что вершины х₍, х, х_к последовательно встречаются на одном и том же пути.

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