Задача листоноші для неорієнтованого графу

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

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

Випадок 1: Граф G парний.

Випадок 2: Граф G непарний.

Випадок 1. Якщо граф парний, то оптимальний розв'язок задачі є завжди і ним буде ейлеровий маршрут.

У цьому випадку листоноша не повинен обходити більше одного разу будь-яку вулицю, у даному випадку ребро графу.

Як віднайти на графі G ейлеровий маршрут, в якому "S" - початкова вершина? Для цього необхідно пройти будь-яке ребро (S, x) інцидентне вершині "S", а потім ще невикористане ребро, інцидентне вершині "х". Кожен раз, коли листоноша приходить у деяку вершину, є невикористане ребро по якому листоноша покидає цю вершину. Дуги, по яким здійснений обхід, створюють цикл С₁. Якщо в цикл С₁ ввійшли всі ребра графу G, то C₁ є ейлеровим маршрутом (оптимальним для задачі).

В іншому випадку треба створити цикл С₂, який складається з невикористаних ребер і який починається з невикористаного ребра. Створення циклів С₃, С₄,..., продовжується доти, доки не будуть використані всі ребра графу. Далі треба об'єднати цикли C₁, C₂, C₃,... в один цикл С, який містить всі ребра графу G. У цикл С кожне ребро графу входить лише один раз, і тому він є оптимальним розв'язком задачі листоноші. Два цикли C₁ і С₂ можуть бути з'єднані тільки тоді, коли вони мають спільну вершину "х ".

Для з'єднання двох таких циклів необхідно вибрати початковим довільним ребром циклу С₁ і рухатися вздовж його ребер до вершини "х". Далі потрібно пройти всі ребра циклу С₂ і повернутися у вершину "х". Врешті-решт, потрібно продовжити прохід ребер циклу С, до повернення назад до початкового ребра. Пройдений маршрут є циклом, отриманим внаслідок з'єднання циклів C₁ і С₂. Цю процедуру можна легко розширити на випадок з'єднання довільної кількості циклів і можна виконувати доти, доки не утвориться дві їх підмножини, які не мають загальних вершин.

Приклад. Необхідно знайти оптимальний маршрут листоноші на парному графі, який зображений на рис. 3. Почавши з вершини “S”, здійснюємо обхід ребер графу за периметром до повернення в вершину “S”. Внаслідок обходу цих ребер буде сформований цикл

С₁ = (s,b), (b,c), (c, f), (f, i), (i, h), (h, g), (g, d), (d, s) ® рис. 4.

 

Рис. 3.

Рис. 4.

Ребро циклу С₁ вважатимемо використаним. Далі, починаючи з невикористаного ребра (d,b), обійдемо невикористані ребра трикутного циклу C₂ = (d,b), (b,e), (e,d), після чого ребра циклу С₂ також будемо вважати використаними. Нарешті, починаючи з невикористаного ребра (e, f), обійдемо ребра нижнього трикутника циклу C₃ = (e,f), (f,h), (h,e). Тепер всі ребра графу використані.

З’єднаємо знайдені вище цикли так: цикл С₂ вставимо між ребрами (g,d) і (d,s) циклу С₁; а цикл С₃ – між ребрами (b,e), (e,d) циклу С₂. Внаслідок цього отримаємо цикл

C = (s,b), (b,c), (c,f), (f,i), (i,h), (h,g), (g,d), (d,b), (b,e), (e,f), (f,h), (h,e), (e,d), (d,s).

Очевидно, що С – оптимальний розв’язок задачі листоноші для розглянутого графу, оскільки С містить кожне ребро один раз, до того ж, починається і закінчується у вершині “S”. Відмітимо, що в цьому прикладі не враховані довжини ребер.

Випадок 2. Граф є непарним. У будь-якому маршруті листоноші кількість входів у вершину дорівнює кількості виходів з неї. Тому, якщо вершина "х" має непарний степінь, то хоч би одне ребро, інцидентне вершині "х", буде обходитись вдруге. Нехай f(i, j) - кількість додаткових проходжень листоношею ребра (i, j). Значить ребро (i, j) обходиться f(i, j)+1 разів (число f(i, j)+1 - невід'ємне, ціле число).

Побудуємо новий граф G*=(X, E*), в якому ребро (i, j) графу G повторюється f(i, j)+1 разів. Очевидно, що ейлеровий маршрут в графі G* відповідає маршрутові в графі G. Листоноша прагне вибрати значення змінних f(i, j) такими, щоб

а). граф G* був парним;

б). åa(і, j)∙f(і, j) - загальна довжина вдруге пройдених ребер була мінімальна, де a(і, j) – вага ребра, f(і, j) – кількість додаткових проходів по ребру (і, j).

Якщо вершина "х" в графі G має непарний степінь, то для того, щоб в графі G* вершина "х" мала парний степінь, листоноша повинен вдруге обійти парну кількість ребер, інцидентних даній вершині. Аналогічно, якщо вершина "х" в графі G має парний степінь, то для того, щоб в графі G* вершина "х" мала парний степінь, листоноша повинен ще раз обійти парну кількість ребер, інцидентних цій вершині (нуль є парне число). Якщо ми до кінця простежимо ланцюг ребер, що починається у вершині з непарним степенем, то він обов'язково повинен закінчитись в іншій вершині з непарним степенем. Отже, ребра, які обходять вдруге, створюють ланцюги, початком і кінцем яких є вершини з непарним степенем. Тому листоноша повинен:

1). вирішити, які вершини з непарним степенем будуть з'єднані ланцюгом ребер для обходу вдруге.

2). знати точний склад кожного такого ланцюга.

Листоноша може за допомогою будь-якого з алгоритмів побудови найкоротшого шляху визначити на графі G найкоротший шлях між кожною парою вершин з непарним степенем.

Для визначення пари вершин з непарним степенем, які повинні бути з'єднані ланцюгом ребер, які обходить вдруге, листоноша може вчинити так.

Алгоритм рішення задачі листоноші для неорієнтованого непарного графа.

Будується додатковий граф G¢, вершинами якого є всі вершини, які мають непарний степінь в початковому графі G. Всі ребра між цими вершинами переносимо в G¢ з відповідною вагою. Граф вийшов непарний і його необхідно доповнити, щоб не втратити глобальний екстремум у розв’язку задачі. Вага на кожному додатковому ребрі буде дорівнювати довжині найкоротшого простого ланцюга між відповідними вершинами графа G.

На графі G¢ необхідно знайти min покриття min ваги.

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

Далі на графі G треба побудувати паросполучення з мінімальною вагою. Ці паросполучення з'єднують на графі G пари вершин з непарними степенями. Листоноша вдруге повинен обійти ребра, що складають ланцюг найменшої довжини і які з’єднують пару інцидентних паросполученню вершин. Оскільки ці паросполучення мають найменшу загальну вагу, то отриманий внаслідок цього маршрут листоноші повинен мати мінімальну загальну довжину.

Приклад. Знайдемо оптимальний маршрут листоноші на неорієнтованому графі, який зображений на рис. 5.

Вершини графу a, c, d і f мають непарні степені. Довжини найкоротших ланцюжків між всіма парами вершин з непарними степенями задаються таблицею.

 

Таблиця 1