Задача листоноші

Задача (китайського) листоноші (англ. Chinese postman problem або англ. Route inspection problem) — задача пошуку найкоротшого циклу в графі, що включає всі ребра. Існують варіанти задачі для орієнтованих та неорієнтованих графів та для графів, частина ребер яких орієнтована, а частина — ні.

Задача отримала назву завдяки Алану Голдману (англ. Alan Goldman) з NIST, оскільки першим дослідником цієї задачі був китайський математик Мей-Ку Кван (англ. Mei-Ku Kuan, 1962).

Методи розв'язання задачі

Для орієнтованого графу: Необхідно розглянути окремо два випадки:

Випадок А. Граф $G$ симетричний.

Випадок Б. Граф $G$ несиметричний.

Випадок А. Якщо граф симетричний, то листоноша може пройти свій маршрут без повторного обходу якої-небудь із дуг, тобто оптимальне рішення задачі листоноші є Ейлерів маршрут.

Випадок Б. Нехай $f(i,j)$,позначає число повторних обходів дуги $(i,j)$. Листоноші необхідно обрати такі невід’ємні значення змінних $f(i,j)$, які мінімізують загальну довжину повторно обхідних дуг

$~\sum _{}^{}{a(i,j)f(i,j)}$ (1)

При умові, що в кожну вершину він входить стільки разів, скільки виходить із неї, тобто

$d^{-}(i)+\sum _{}^{}{f(j,i)}={d^{+}(i)}+(i)+\sum _{}^{}{f(i,j)}$ (2)

Перетворивши рівняння (2), отримуємо

$\sum _{}^{}{f(i,j)-f(j,i)}={d^{-}(i)}+{d^{+}(i)}=D(i)$ (3)

Таким чином, листоноша бажає мінімізувати вираз (1) при умові, що для всіх вершин графу G задовольняється рівність (3). Ця задача представляє одну із модифікацій задачі про потік мінімальної вартості. Вершини, для яких $D(i)<0$, є стоками з граничним значенням сумарного вхідного потоку, рівним – $D(i)$. Вершини, де $D(i)>0$, являють собою джерело з граничним значенням сумарного вихідного потоку, рівне $D(i)$. Вершини, для яких $D(i)=0$, є проміжковими вершинами. Значення пропускних здібностей всіх дуг безлімітні. Сформульована задача про потік мінімальної вартості може бути вирішена шляхом введення в граф додаткового джерела і стоку. Додаткове джерело пов'язаний дугами зі усіма іншими джерелами, і всі стоки пов'язані дугами з додатковим стоком. Значення пропускної здатності кожної дуги, що виходить з додаткового джерела, рівно граничному значенню сумарного потоку джерела, яке інцидентне цій дузі. Так як праві частини всіх рівностей, (3) - цілі числа, то можна стверджувати, що за допомогою описаного алгоритму визначення потоку мінімальної вартості будуть отримані невід'ємні цілі значення $f(i,j)$. Визначивши цілочисельні оптимальні значення змінних $f(i,j)$ побудуємо граф $G*$, В якому дуга $(i,j)$, що з'єднує вершини $i$ і $j$ для всіх $(i,j)$ $~{\mathcal {2}}$ $A$, повторюється $f(i,j)+1$ раз. З рівністю (3) такий граф $G*$ є симетричним. Тепер для графу $G*$ за допомогою методу, описаного для випадку А, може бути знайдений Ейлером маршрут. Останній на графі $G*$ відповідає маршруту листоноші па графі $G$, в якому дуга $(i,j)$ обходиться $[f(i,j)+1]$ разів. Так як оптимального значення $f(i,j)$ мінімізують вираз (1), одержуваний на графі $G*$ Ейлерів маршрут повинен відповідати оптимальному маршрутом листоноші на графі $G$.

Для змішаного графу: Необхідно розглянути окремо два випадки: Випадок А. Граф $G$ симетричний.

Випадок Б. Граф $G$ несиметричний.

Випадок А.Нехай $G=(X,A)$ – будь-який парний змішаний граф. Оптимальний маршрут листоноші (якщо він існує) може бути знайдено наступним чином. Позначимо через $U$ множину всіх неорієнтованих дуг, а через $V$ – множину всіх орієнтованих дуг в графі $G$. Для кожної дуги в U виберемо вихідний напрямок. Назвемо отриманий орієнтований граф графом $G_{\mathrm {d} }$. Для кожної вершини і графу $G_{\mathrm {(} }d)$ обрахуємо

$D(i)=d^{-}(i)-d^{+}(i)$ (4)

Якщо $D(i)<0$, то вершина і є стоком з граничною величиною сумарного вхідного потоку, рівному $D(i)$. Якщо $D(i)>0$, то вершина і є джерелом з граничною величиною сумарного виходить потоку $D(i)$ - Якщо $D(i)=0$, то вершина $i$ є проміжною. Якщо в графі всі вершини є проміжними, то граф-парний симетричний орієнтований граф. Для отримання оптимального маршруту листоноші на такому графі треба знайти Ейлерів маршрут, який відповідає оптимальному маршруту листоноші на графі $G$. В іншому випадку необхідно побудувати граф $G-(X,A')$, в якому: (а) Кожна дуга $(i,j)$ $~{\mathcal {2}}$ $V$ заміщується дугою $(i,j)$ $~{\mathcal {2}}$ $A'$ з необмеженою величиною пропускної здатності і вартістю, рівної довжині дуги (i, j). (б) Кожній дузі $(i,j)$ $~{\mathcal {2}}$ $U$ і відповідає пара дуг $(i,j)$ і $(j,i)$ в $A'$. Кожна з цих дуг має необмежену величину пропускної здатності і вартість, рівну довжині дуги $(i,j)$ $~{\mathcal {2}}$ $A$. (в) Кожній дузі $(i,j)$ $~{\mathcal {2}}$ $U$ відповідає також орієнтована дуга $(i,j)$ $~{\mathcal {2}}$ $A'$, напрямок якої протилежно напрямку дуги, прийнятому в $G_{\mathrm {(} }d)$. Ця дуга називається фіктивною дугою. Припишемо фіктивної дузі вартість, рівну нулю, і величину пропускної здатності, рівну 2. З урахуванням визначених вище для графу $G_{\mathrm {(} }d)$ граничних значень потоків, що виходять із джерел і входять до стоки, скористаємося алгоритмом побудови потоку мінімальної вартості для пошуку на графі ${G'}$ потоку мінімальної вартості, що задовольняє потреби всіх стоків. Якщо такого потоку не існує, то не існує і маршруту листоноші. В іншому випадку нехай через $f(i,j)$ позначається величина потоку, який протікає по дузі $(i,j)$ графу $G'$, отриманого в результаті рішення задачі про потік мінімальної вартості. Нагадаємо, що потік, отриманий за допомогою описаного вище алгоритму побудови потоку мінімальної вартості, є невід'ємним і цілочисловим. У ході докази того, що алгоритм забезпечує отримання рішення задачі листоноші, буде показано, що але кожної фіктивної дузі протікає потік, рівний 0 або 2. Побудуємо далі граф G*, В якому:

(a) Кожна не-фіктивного дуга $(i,j)$ $~{\mathcal {2}}$ $V$ графу $G'$ замінюється $[f(i,j)+1]$ дугами $(i,j)$ графу $G*$.

(б) Кожна не-фіктивна дуга $(i,j)$ $~{\mathcal {2}}$ $U$ графу $G'$ замінюється $f(i,j)$ дугами $(i,j)$ графу $G*$.

(в) Якщо потік у фіктивній дузі дорівнює двом одиницям, то в граф $G*$ включається одна така дуга.

(г) Якщо потік у фіктивній дузі дорівнює нулю, то в граф $G*$ включається одна така дуга з протилежного орієнтацією. Таким чином, якщо у фіктивній дузі потік дорівнює нулю, то вибраний вихідний напрямок дуги графу $G_{\mathrm {(} }d)$ зберігається і в графі $G*$, якщо ж потік у фіктивній дузі дорівнює двом одиницям, то напрямок орієнтації відповідної дуги графу $G_{\mathrm {(} }d)$ в графі $G*$ змінюється на протилежне.

Граф $G*$ є парним симетричним орієнтованим графом. Для отримання оптимального маршруту листоноші на такому графі треба знайти Ейлерів цикл.

Випадок Б. Алгоритму розв'язання даної задачі не існує

Див. також

• Задача комівояжера
• Ейлерів цикл

Література

• Майника Э. (1981). Алгоритмы оптимизации на сетях и графах. М.: Мир. с. 323.