Задача почтальона для орграфа

Во введении в качестве примера приводилась задача Эйлера о кенигсбергских мостах (задача 1) и её модификация (задача 2).

Сформулируем эти задачи в терминах теории графов. Для этого представим город (рис.В.1) в виде мультиграфа (рис. 7.7), в котором вершины соответствуют частям города, а рёбра - мостам.

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

Если каждому ребру (x, y) приписать число a (x, y), равное длине пути из вершины x в вершину y, то задача 2 в общем виде в терминах теории графов будет сформулирована следующим образом: в мультиграфе найти маршрут наименьшей длины из начальной вершины x, включающий каждое ребро хотя бы один раз и заканчивающийся в той же вершине x. Такая задача возникает при разносе почты, при патрулировании улиц, при обходе железнодорожных путей и при выполнении других видов курьерских заданий. В теории графов такую задачу принято называть задачей почтальона, а соответствующий маршрут – маршрутом почтальона.

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

Сказанное легко обобщается и для орграфов. Критерий существования эйлерова маршрута в орграфе формулируется следующим образом: эйлеров маршрут существует только в орграфе, в котором для каждой вершины x число входящих в эту вершину дуг d ^-(x) равно числу дуг, выходящих из этой вершины d ⁺(x). Графы, удовлетворяющие сформулированному условию, называются симметричными графами.

Если графы не являются четными (симметричными), то в маршруте почтальона некоторые рёбра (дуги) будут повторяться более одного раза. Алгоритмы нахождения оптимальных маршрутов почтальона для различных видов графов (неориентированных, ориентированных, смешанных) различны.

Рассмотрим алгоритм нахождения оптимального маршрута почтальона для орграфов.

Алгоритм 8.

Шаг 1. Если граф G =(V, E) несимметричный, то перейти к шагу 2, иначе к шагу 3.

Шаг 2. Путем дублирования дуг графа G уровнять степени вершин, то есть сделать граф симметричным. Причем суммарная длина дублируемых дуг должна быть минимальной. Детально шаг 2 будет рассмотрен ниже.

Шаг 3. Построить эйлеров маршрут по правилам:

1. Начиная с начальной вершины s, обходим дуги без повторных обходов до тех пор, пока не произойдет возврат в вершину s. Пройденные при этом дуги образуют некоторый контур C ₁.

2. Затем, начав с любой непройденной дуги и обходя только такие дуги, строим другой контур C ₂. Процедура построения контуров продолжается до тех пор, пока не будет завершен обход всех дуг графа.

3. Все найденные контуры объединяем в один.

Рассмотрим более детально этапы выполнения шага 2. Пусть f (x, y) – число дублирований дуги (x, y), a (x, y) – длина (вес) дуги (x, y). Тогда в графе с уравненными степенями вершин должно выполняться условие:

" x Î V, d ^-(x)+ å f (y, x) = d ⁺(x)+ å f (x, y), (7.6)

y Î V y Î V

причем суммарная длина дублируемых дуг

å a (x, y)× f (x, y) (7.7)

(x, y)Î E

должна быть минимальной.

Преобразовав выражение 7.6, получим:

" x Î V, å [ f (x, y)- f (y, x) ] = d ^-(x) - d ⁺(x) = D (x)

y Î V

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

Вершины, для которых D (x)<0, являются стоками с предельным значением суммарного входящего потока, равным - D (x). Вершины, для которых D (x)>0, представляют собой источники с предельным значением суммарного выходящего потока, равным D (x). Вершины, для которых D (x)=0, являются промежуточными вершинами. Значения пропускных способностей дуг не ограничены.

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

Применив к полученному таким образом графу алгоритм поиска потока минимальной стоимости, получим целые неотрицательные значения f (x, y). Продублировав в исходном графе G =(V, E) каждую дугу (x, y)Î E f (x, y) раз, получим граф G ¢=(V, E). Согласно выражению 7.6, граф G ¢ симметричный. Согласно выражению 7.7, сумма стоимостей дуг графа G ¢ минимальна.

На этом выполнение шага 2 в алгоритме нахождения оптимального маршрута почтальона в орграфе завершается.

Рассмотрим пример работы алгоритма на примере орграфа, изображенного на рис. 7.8.

На шаге 1 алгоритма 8 выясняется, что граф G =(V, E), изображенный на рис. 7.8, не является симметричным (есть вершины, для которых число входящих дуг больше, чем число выходящих, и наоборот), и осуществляется переход к шагу 2.

На втором шаге определяется, какие вершины графа G будут источниками, стоками и промежуточными. Результаты этих действий сведены в таблицу 7.3.

Таблица 7.3. Этапы выполнения шага 2 алгоритма 8

Вершина x	d -(x)	d +(x)	Описание вершины x
	v 1			Промежуточная
	v 2			Источник с предельным значением суммарного выходящего потока, равным d -(v 2)- d +(v 2)=3-1=2
	v 3			Сток с предельным значением суммарного входящего потока, равным d +(v 3)- d -(v 3)=2-1=1
	v 4			Сток с предельным значением суммарного входящего потока, равным d +(v 4)- d -(v 4)=2-1=1
	v 5			Промежуточная

Далее вводится дополнительный источник, сток и дуги, как было сказано выше. Результат таких действий проиллюстрирован на рис.7.9.

Применив к полученному графу алгоритм поиска потока минимальной стоимости, получим: f (s, v ₂)= f (v ₂, v ₄)=2, f (v ₄, t)= f (v ₄, v ₃)= f (v ₃, t)=1, для остальных дуг (x, y) f (x, y)=0.

Продублировав в исходном графе G =(V, E) (рис. 7.8) каждую дугу (x, y)Î E f (x, y) раз, получим симметричный граф, изображенный на рис.7.10.

Далее переходим к выполнению шага 3. Отметим, что в зависимости от порядка просмотра данных (дуг графа), могут получиться различные контуры, например, C ₁= v ₁, v ₂, v ₄, v ₅, v ₁ или C ₁= v ₁, v ₂, v ₄, v ₃, v ₅, v ₁. Результат выполнения шага 3 от порядка просмотра данных не зависит. Один из возможных вариантов построения контуров и их объединения в маршрут почтальона проиллюстрирован на рис.7.11.

СПИСОК ЛИТЕРАТУРЫ

1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 384 с.

2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ./ Предисл. В.Б.Алексеева. - М.: Мир, 1980. - 476 с.

3. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. - М. Мир, 1981. - 323 с.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - 2-е изд. - М.: Энергоатомиздат, 1988. - 480 с.

5. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. - М.: Мир, 1982. - 416 с.

6. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. - М.: Мир, 1978. - 846 с.

7. П.Холл. Вычислительные структуры. Введение в нечисленное программирование: Пер. с англ. - М.: Мир, 1978. - 214 с.

8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

9. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. - 432 с.

10. Берж К. Теория графов и её применения. – М.: ИЛ, 1962. – 319 с.

11. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 381 с.

12. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986. – 384 с.

13. Оре О. Теория графов. – М.: Наука, 1980. – 336 с.

14. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – 454 с.

15. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. – 207 с.

16. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.

Св.план 2000, поз. ____

МУРОМЦЕВ ВИКТОР ВЛАДИМИРОВИЧ

АЛГОРИТМЫ НА ГРАФАХ

УЧЕБНОЕ ПОСОБИЕ

Редактор ___________________

Корректор ___________________

Подписано к печати ___/_______/_____ Формат 60´84/16

Объем 3 уч.-изд.л. Тираж _________

Заказ Цена __________