Представьте себе добросовестного почтальона, которому
нужно обойти все улицы, где проживают адресаты писем. Оптимальным для
него будет такой маршрут, при котором ему придется пройти по каждой
улице ровно один раз. Если мы изобразим улицы на графе, то эта задача
будет равносильна поиску эйлерова цикла в этом графе. Но если этот граф
не содержит эйлеров цикл, почтальону придется пройти по некоторым улицам
несколько раз, но так, чтобы число повторов было минимальным. Этой
задачей занимался китайский математик Мэй-Ку Куан в 1962 году, поэтому
она получила название задачи о китайском почтальоне.
Если мы внимательно посмотрим на рисунки выше, то
увидим, что две вершины имеют степень, равную 3. Следовательно, данный
граф не содержит эйлеров цикл. Однако на втором рисунке видно, что если
мы добавим всего одно ребро (выделено пунктиром), то граф будет
содержать эйлеров цикл (последовательность обхода ребер обозначена
цифрами). При этом нужно будет пройти два раза всего по одной улице (5 и
6). Именно так выглядит алгоритм решения задачи китайского почтальона:
если граф не содержит эйлеров цикл, нужно добавить к нему минимально
возможное число ребер, которые будут дублировать уже имеющиеся, чтобы
получить эйлеров цикл.
На следующих рисунках приведен один из возможных вариантов решения и оптимальный путь почтальона.
Эта задача широко применяется при доставке
разнообразных грузов. Поиск оптимальных маршрутов в крупных городах
представляет особый интерес, так как позволяет снизить финансовые и
трудовые затраты при уборке улиц, доставке различных товаров и в других
процессах. К счастью, в настоящее время при поиске таких маршрутов нам
помогают компьютеры.
| 
