Основні поняття та властивості задачі листоноші

Будь-який листоноша перед тим, як відправитись у дорогу повинен відібрати на пошті листи, що належать до його дільниці, потім він повинен рознести їх адресатам, які розмістились вздовж маршруту його проходження, і повернутись на пошту. Кожен листоноша, бажаючи втратити якомога менше сил, хотів би подолати свій маршрут найкоротшим шляхом. Загалом, задача листоноші полягає в тому, щоб пройти всі вулиці маршруту і повернутися на пошту, мінімізуючи при цьому довжину пройденого шляху.

Задачу листоноші можна сформулювати в термінах теорії графів. Для цього побудуємо граф G = (X, Е), в якому кожна дуга відповідає вулиці в маршруті руху листоноші, а кожна вершина - стикові двох вулиць. Ця задача є задачею пошуку найкоротшого маршруту, який включає кожне ребро хоча б один раз і закінчується у початковій вершині руху.

Нехай S – початкова вершина маршруту і a(i, j) > 0 – довжина ребра (i, j). У графі на рис. 1 існує декілька шляхів, за якими листоноша може обійти всі ребра і повернутися у вершину S.

Рис. 1.

Наприклад:

Шлях 1: (S, a), (a, b), (b, c), (c, d), (d, b), (b, S)

Шлях 2: (S, a), (a, b), (d, b), (d, c), (c, b), (b, S)

Шлях 3: (S, b), (b, c), (c, d), (d, b), (d, a), (a, S)

Шлях 4: (S, b), (b, d), (d, c), (c, b), (b, a), (a, S).

У будь-який з чотирьох шляхів кожне ребро входить тільки один раз. Отже, загальна довжина кожного маршруту дорівнює

3 + 2 + 1 +3 + 7 + 6 = 22

Кращих маршрутів у листоноші не існує. Маршрут (ланцюг або шлях), в якому кожне ребро (дуга) повторюється тільки один раз, називається ейлеровим маршрутом.

Розглянемо граф, який показаний на рис. 2.

Рис. 2.

Очевидно, що на ньому відсутні маршрути листоноші, в яких дуга (b, с) входила б тільки один раз, тобто відсутній ейлеровий маршрут.

Можливим оптимальним маршрутом (маршрутом найменшої довжини) на цьому графі є:

(S, a), (a, b), (b, c), (c, d), (d, e), (e, c), (c, b), (b, S)

Загальна довжина цього маршруту дорівнює

3 + 2 + 5 + 1 + 3 + 7 + 5 + 6 = 32

Виходячи з формулювання задачі листоноші:

1. Очевидно, що в незв'язному графі (в графі, який має декілька компонент) не існує маршруту листоноші (не кажучи про існування ейлерового маршруту). Тому надалі вважатимемо, що граф є зв'язний.

2. Очевидно, що кількість приходів листоноші в деяку вершину повинна дорівнювати кількості виходів з цієї вершини. При цьому, якщо листоноша не проходить через деяке ребро більше одного разу, то вершина повинна бути інцидентна парній кількості ребер. Загальну кількість ребер, інцидентних вершині х, назвемо степенем вершини і будемо позначати через d(x). Якщо в графі G всі вершини мають парний (непарний) степінь, то граф називається парним (непарним). В орієнтованому графі кількість дуг, які входять у вершину х називають внутрішнім степенем вершини х або півстепенем входу (позначається через d^-(x)), a які виходять - зовнішнім степенем вершини х або півстепенем виходу (позначається d⁺(x). Якщо d^-(x)=d⁺(x) то граф називається симетричним.

Припустимо, що ми знаємо оптимальний маршрут листоноші на графі G, який починається і закінчується в вершині "S". Яким буде оптимальний маршрут, якщо поміняти початкову точку на вершину "t"? Будь-який оптимальний маршрут R, що починається в вершині "S", зрештою колись вперше проходить через вершину "t". Назвемо цю частину маршруту R₁ а залишок R₂. Зауважимо, що R₁ починається в вершині "S" і закінчується в "t". Своєю чергою R₂ починається в вершині "t" і закінчується в "S". Сформуємо новий маршрут R', який складається з R₂, а після нього R₁. Маршрут R' починається в вершині "t" і закінчується в вершині "t" та має сумарну довжину таку ж, як і маршрут R.

Висновок: R' = R - оптимальний маршрут. Отже:

Теорема 1. Сумарна довжина оптимального маршруту листоноші не залежить від того, яка з вершин цього маршруту буде вибрана за початкову.