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

 

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

Задача о Ханойской башне

Рассмотрим пример представления графом изменения состояний дискретной системы [18].

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

Легенда гласит, что в одном буддийском монастыре во Вьетнаме на первом стержне нанизано 64 диска. Если переложить все их по указанным правилам на третий стержень, то наступит конец света. Конец света – вопрос философский, но, тем не менее, не будем испытывать судьбу и рассмотрим задачи с меньшим числом дисков.

Рассмотрим n=1 (рис. 24).

Рис. 24. Задача о Ханойской башне для n=1

 

Задача для n=1 решается за один шаг, но возможен и неоптимальный вариант – два шага, т.е. сначала диск устанавливают на второй стержень, а потом на третий.

Обозначим X, Y и Z множества дисков, надетых соответственно на первый, второй и третий стержни. Состояние такой системы будем описывать набором элементов этих множеств (X,Y,Z).

Тогда возможные состояния такой системы имеют вид:

X Y Z

(1,0,0) – исходное,

(0,0,1) – целевое,

(0,1,0) – промежуточное.

Представим состояния системы в виде графа с использованием координатной плоскости с осями X и Z (рис. 25). Такое представление избавляет нас от необходимости указывать состояние вершин.

 

Рис. 25. Представление графом задачи о Ханойской башне при n=1

 

Третья ось на рис. 25 не указана, множество Y всегда можно получить как дополнение множеств X, Z до полного множества дисков.

Тогда путь 11 соответствует оптимальному решению задачи, а путь 101 – неоптимальному.

Рассмотрим случай n=2. Будем описывать элементы множеств в виде столбца цифр, соответствующих убыванию диаметра дисков:

X Y Z

(,0,0) – исходное состояние,

(2,1,0) – 1-й шаг,

(0,1,2) – 2-й шаг,

(0,0, ) – 3-й шаг, целевое состояние.

Это оптимальное решение задачи – за 3 шага. Возможны также неоптимальные последовательности. Изобразим вначале все возможные последовательности в виде графа и обозначим все ребра следующим образом (рис. 26)

Рис. 26. Возможные последовательности решения

задачи о Ханойской башне для n=2

а) для трех множеств X,Y,Z, б) для двух множеств X,Z

 

Представим теперь случай n=2 на координатной плоскости, используя координаты – множества X,Z (первая и третья координаты). Получим рис. 27, на котором отмечены дуги, соответствующие рис. 26б. Видно, что этот граф как бы содержит в себе три графа для n=1, а оптимальное решение соответствует последовательности дуг а,b,с (,0;2,0;0,2;0, ).

Общий способ решения задачи о Ханойской башне может быть получен путем анализа трансформации графа для n дисков при переходе к n+1 диску.

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

Рис. 27. Представление графом задачи

о Ханойской башне для n=2

 

Оптимальный переход всегда из нижней левой точки крайнего правого треугольника! Степени всех вершин, кроме крайних равны 3. Есть три пути, как у витязя на распутье. Кратчайший путь для данных графов можно найти полным перебором возможных путей. Рассмотрим систематический метод определения этого пути. Общее правило нахождения кратчайшего пути в графе с ребрами единичной длины состоит в том, чтобы каждой вершине х_i приписать индекс l_i, равный длине кратчайшего пути из данной вершины в конечную:

1) конечной вершине приписывается индекс 0;

2) всем вершинам, из которых идет ребро в конечную вершину, приписывается индекс 1;

3) всем вершинам, ещё не имеющим индексов, из которых идет ребро в вершину с индексом l_i приписывается индекс l_i+1.

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

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

Такой способ определения кратчайшего пути является частным случаем нахождения оптимального решения по методу динамического программирования (Р. Беллмана).

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