17. Понятие о задачах на графа

Одной из первых задач в теории графов считается задача Эйлера (1736 г.) – задача о кенигсбергских мостах [19, 26]. Ее решение Л. Эйлер опубликовал, когда работал в Российской Академии наук. Расположение мостов в г. Кенигсберге на реке Преголь в то время приведено на рис. 23а, а соответствующий неориентированный граф – на рис. 23б. Требуется пройти каждый мост по одному разу и вернуться в исходную часть города.

Рис. 23. Задача о кенигсбергских мостах

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

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

Таков граф «звезда», изображенный на рис. 12.

Оказывается, конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны [19].

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

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

С другой задачей – задачей раскраски графов связана так называемая «задача четырех цветов» [19]. Это задача раскраски карты, т.е. разбиения плоскости на связные области. Достаточно ли четырех цветов для раскраски любой карты? По некоторым сведениям, еще в 1840 г. об этой задаче знал известный немецкий математик А.Ф. Мебиус. Только сравнительно недавно два американских математика доказали разрешимость этой задачи, использовав компьютер [19].

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

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

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

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

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