Тема 15.2. Обход графа

Определение:Маршрут, содержащий все рёбра или все вершины графа, и обладающий определёнными свойствами называетсяобходомграфа.

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

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

Существует критерий существования эйлерова цикла в графе.

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

Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кёнигсбергских мостах. Расположение семи мостов в городе Кёнигсберге в начале XVIIIвека приведено на рисунке. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.

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

Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.

Теорема.Для того, чтобы связный граф обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечётной степени.

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

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

Известен ряд достаточных условий существования гамильтонова цикла в графе. Но неизвестен критерий существования Гамильтонова цикла в графе.

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

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

Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.

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

Штрихи в обозначении используются, потому что не обязательно дуги под одинаковыми индексами будут совпадать.

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

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

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

1) , причёмтогда и только тогда, когда;

2) .

Также для расстояния выполняется неравенство треугольника: для любых трёх вершинвыполняется неравенство:.

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

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

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

Пусть – рассматриваемая вершина данного графа, а– произвольная вершина графа.Максимальным удалениемв графеот фиксированной вершиныназывается величина.

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

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

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

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

Определение:Протяжённостьюназывается максимальная из длин связывающих эти вершины простых цепей.