5.2. Алгоритм для задачи китайского почтальона

В случае когда веса всех ребер равны единице, задачу китайского почтальона рассмотрели Беллман и Кук [3] с использованием динамического программирования. Более общую задачу.

когда веса ребер произвольны, сформулировали и решили как задачу о паросочетании (с частной задачей о кратчайшей цепи) Эдмондс [9], Эдмондс и Джонсон [10], Басакер и Саати [7] и Кристофидес [8].

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

и так как сумма 2 четна, то сумма также четна. Но все в последней сумме нечетны, значит число вершин нечетной степени четно.

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

Теперь мы можем доказать следующую теорему.

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

Доказательство. Если цикл проходит по графу то по крайней мере одно ребро, инцидентное каждой вершине нечетной степени, должно проходиться дважды. (Ребро, проходимое дважды, можно рассматривать как два параллельных ребра — одно реальное и одно искусственное — и каждое из них проходится один раз.) Пусть это ребро В случае нечетности степени вершины графа добавление искусственного ребра прежде всего сделает четным, и значит только ребро нужно будет проходить дважды, если ограничиться рассмотрением лишь вершин В случае когда четно, добавление искусственного ребра сделает нечетным, а второе ребро выходящее из должно быть пройдено дважды (т. е. добавляется еще одно искусственное ребро). Такая ситуация сохраняется до тех пор, пока не встретится вершина нечетной степени, о чем говорилось выше. Следовательно, чтобы удовлетворить условию возвращения в вершину нужно дважды пройти всю цепь из в некоторую другую вершину нечетной степени принадлежащую множеству Это автоматически приводит к выполнению условия прохождения вершины Аналогично обстоит дело для всех других вершин из Это значит, что все множество цепей из определенное выше, должно проходиться дважды, и так как отсюда вытекает, что каждое ребро из должно проходиться один раз, то теорема доказана.

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

5.2.1. Описание алгоритма.

Шаг 1. Пусть матрица весов ребер графа Используя алгоритм кратчайшей цепи (см. гл. 8), образуем -матрицу где вес цепи наименьшего веса, идущей из некоторой вершины в другую вершину

Шаг 2. Найдем то цепное паросочетание для множества которое дает наименьший вес (в соответствии с матрицей весов Это можно сделать эффективно с помощью алгоритма минимального паросочетания из гл. 12.

Шаг 3. Если вершина сочетается с другой вершиной то определим цепь наименьшего веса (из соответствующую весу делая шаг 1. Добавим искусственные ребра в

соответствующие ребрам из и проделаем это для всех других цепей из множества в результате чего получится

Шаг 4. Сумма весов всех ребер графа найденная с использованием матрицы (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по При этом число прохождений цикла по ребру равно общему числу параллельных ребер между

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

Рис. 9.11. Цепи имеющие общее ребро

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

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

5.2.2. Пример.

Рассмотрим граф изображенный на рис. 9.12, имеющий 12 вершин и 22 ребра, веса которых указаны у каждого ребра.

Рис. 9.12. Граф из примера 5.2.2.

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

На шаге 2 алгоритм минимального паросочетания (см. гл. 12) связывает следующие вершины (два других паросочетания также являются минимальными):

Граф получающийся после выполнения шага 3, изображен на рис. 9.13; пунктиром показаны искусственные ребра.

Рис. 9.13. Граф из примера реальные ребра; искусственные ребра.

Из этого рисунка видно, что оптимальный цикл в графе проходит через ребра и дважды, а через все остальные ребра — один раз. Вес этого цикла равен 294.

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

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