Міністерство народної освіти Республіки Дагестан
Дагестанский Державний Університет
Курсова робота
Програмування задач на графах
Гамільтона і ейлерови цикли
Виконав:
Студент 4 курсу 4 гр. МФ
Цургулов Аліл Гасанович
Науковий керівник:
Якубов А. 3.
Махачкала, 2003 рік
Зміст
Зміст 2
Введення 4
Глава 1. Ейлерови цикли 4
§ 1. Основні поняття і визначення 5
§ 2. Критерій існування ейлерова циклу 5
§ 3. Алгоритми побудови ейлерова циклу 6
§ 4. Деякі родинні завдання 8
§ 5. Завдання китайського листоноші 9
Глава 2. Гамільтона цикли 11
§ 1. Основні поняття та визначення 11
§ 2. Умови існування Гамільтона циклу 11
§ 3. Завдання пов'язані з пошуком гамільтонових циклів 12
§ 4. Методи побудови гамільтонових циклів в графі. 14
§ 5. Алгебраїчний метод побудови гамільтонових циклів 15
§ 6. Метод перебору Робертса та Флореса 16
§ 8. Поліпшення методу Робертса та Флореса 18
§ 9. Мультіцепной метод 19
§ 10. Порівняння методів пошуку гамільтонових циклів 21
Глава 3. Завдання комівояжера 23
§ 1. Загальний опис 23
§ 2. "Жодний" алгоритм розв'язання ЗК 25
§ 3. "Дерев'яний" алгоритм розв'язання ЗК 26
§ 4. Метод лексикографічного перебору 28
§ 5. Метод гілок і меж рішення ЗК 29
§ 6. Застосування алгоритму Дейкстри до вирішення ЗК 34
§ 7. Метод опуклого багатокутника для вирішення ЗК 34
§ 8. Генетичні алгоритми 36
§ 9. Застосування генетичних алгоритмів 39
Список літератури 41
Введення
Метою моєї курсової роботи є опис методів знаходження іпобудови ейлерових і всіх гамільтонових циклів в графах, а такожпорівняльний аналіз цих методів. Інша мета яке вирішується у даній роботі --це розгляд задачі комівояжера і методів її рішення (включаючиевристичні та генетичні алгоритми).
Перш за все, щоб внести ясність і уточнити термінологію, хотілосяб дати визначення деяким елементам графа таким, як маршрут, ланцюг,цикл.
Маршрутом у графі G (V, E) називається чергуються послідовністьвершин і ребер: v0, e1, ... en, vn, в якій будь-які два сусідніх елементаінцідентни. Якщо v0 = vn, то маршрут замкнутий, інакше відкритий.
Якщо всі ребра різні, то маршрут називається ланцюгом. Якщо всі вершини
(а значить, ребра) різні, то маршрут називається простий ланцюгом.
Замкнута ланцюг називається циклом; замкнута проста ланцюг називаєтьсяпростим циклом. Граф без циклів називається ациклічні. Для Орграф ланцюгназивається шляхом, а цикл - контуром.
Глава 1. Ейлерови цикли
Потрібно знайти цикл, що проходить по кожній дузі рівно один раз. Цюзавдання вперше поставив і вирішив Леонард Ейлер, чим і заклав основи теоріїграфів, а відповідні цикли тепер називаються ейлеровимі. Фігури,які потрібно змалювати, не перериваючи і не повторюючи лінії, такожвідносяться до ейлеровим циклами.
Завдання виникла із запропонованої Ейлера головоломки, що одержаланазву "проблема кенігсберзькими мостів". Річка Прегель, що протікає через
Калінінград (перш за місто називалося Кенігсбергом), омиває два острови.
Береги річки пов'язані з островами так, як це показано на малюнку.
У головоломці потрібно було знайти маршрут, що проходить по всіх ділянкахсуші таким чином, щоб кожен з мостів був пройдений рівно один раз, апочатковий і кінцевий пункти маршруту збігалися.
§ 1. Основні поняття і визначення
Дамо тепер суворе визначення ейлерову циклу і ейлерову графу. Якщограф має цикл (не обов'язково простий), що містить всі ребра графа поодному разу, то такий цикл називається ейлеровим циклом, а граф називаєтьсяейлеровим графом. Якщо граф має ланцюг (не обов'язково просту), що міститьвсі вершини по одному разу, то така ланцюг називається ейлеровой ланцюгом, аграф називається полуейлеровим графом.
Ясно, що Ейлером цикл містить не тільки всі ребра по одному разу, алеі всі вершини графа (можливо, по кілька разів). Очевидно також, щоейлеровим може бути тільки зв'язний граф.
Виберемо в якості вершин графа берега річки, а в якості ребер --мости, що з'єднують їх. Після цього завдання стає очевидною: вимоганездійсненно - щоб його виконати, число дуг, що приходять до кожноївершині, повинно бути парним. Справді, оскільки по одному мосту не можнапроходити двічі, кожному входу на берег повинен відповідати вихід.
§ 2. Критерій існування ейлерова циклу
Що необхідно, щоб у графі існував Ейлером цикл? По-перше,граф повинен бути пов'язаним: для будь-яких двох вершин повинен існувати шлях,їх з'єднує. По-друге, для неорієнтовані графів число ребер укожній вершині повинно бути парним. Насправді цього виявляєтьсядостатньо.
Теорема 1. Щоб у зв'язаному неорієнтовані графі G існувавЕйлером цикл, необхідно і достатньо, щоб число вершин непарного ступенябуло парних.
Доказ.
Необхідність. Будь-який Ейлером цикл повинен прийти в вершину по одномуребра і залишити її по іншому, тому що будь-яке ребро має використовуватисярівно один раз. Тому, якщо G містить Ейлером цикл, то ступеня вершинповинні бути парними.
Достатність. Нехай G - зв'язний неорієнтовані граф, усі вершиниякого мають парну ступінь. Почнемо шлях з деякої довільноївершини x0 і підемо по деякому раніше не використаним ребру донаступної вершини, і так до тих пір, поки не повернемося в вершину x0 і незамкнемо цикл. Якщо всі ребра виявляться використаними, то потрібний Ейлеромцикл побудований. Якщо ж деякі ребра не використані, то нехай Ф - тількищо побудований цикл. Так як граф G зв'язків, то цикл Ф повинен проходитичерез деяку вершину, скажімо xi, що є кінцевою вершиною якого -або до цих пір не використаного ребра. Якщо видалити всі ребра,належать Ф, то в графі, що залишився, всі вершини, як і раніше будуть матипарну ступінь, так як в циклі Ф повинно бути парне число ребер (0є парним числом), інцідентних кожної вершини.
Починаючи тепер з xi, отримуємо цикл Ф ', що починається і закінчується вxi. Якщо все, що залишилися, раніше ребра використані для циклу Ф ', то процесзакінчений. Потрібний Ейлером цикл буде утворений частиною циклу Ф від вершини x0до xi, потім циклом Ф 'і, нарешті, частиною циклу Ф від вершини xi до x0. Якщож усе ще залишилися невикористані ребра, то об'єднання побудованих вищециклів Ф і Ф 'дає новий цикл Ф. Ми знову можемо знайти вершину xj,що належить циклу і яка є кінцевою вершиною деякогоневикористаного ребра. Потім ми можемо приступити до побудови новогоциклу Ф ', що починається в xj, і так до тих пір, поки не будуть використанівсі ребра і не буде отриманий таким чином Ейлером цикл Ф. Це доводитьтеорему.
Хоча доказ проведено для неорієнтовані графів, воно відразупереноситься на орієнтовані, тільки вимога парності замінюєтьсятепер на таке: число входять в кожну вершину ребер має дорівнюватичисла виходять.
Слідство # 1.
Для зв'язкового ейлерова графа G безліч ребер можна розбити на простіцикли.
Слідство # 2.
Для того щоб зв'язний граф G покривався єдиною ейлеровой ланцюгом,необхідно і достатньо, щоб він містив рівно 2 вершини з непарноїступенем. Тоді ланцюг починається в одній з цих вершин і закінчується вінший.
§ 3. Алгоритми побудови ейлерова циклу
Вище був встановлений ефективний спосіб перевірки наявності ейлерова циклуу графі. А саме, для цього необхідно і достатньо переконатися, що ступенявсіх вершин парні, що неважко зробити при будь-якому поданні графа.
Залишилось зауважити, що запропонований в доказі алгоритм лине, тобтокількість дій прямо пропорційно числу ребер.
Алгоритм побудови ейлерова циклу в ейлеровом графі.
Вхід: Ейлером граф G (V, E), заданий матрицею суміжності. Для простотизазначимо, що Г [v] - безліч вершин, суміжних з вершиною v.
Вихід: послідовність вершин ейлерова циклу.
S: = Ш (стек для зберігання вершин)select vV (довільна вершина)v> S (v покласти в стек S)while S? Ш do vS (v - верхній елемент стека) if Г [v] = Ш then vS (u покласти в стек)
Г [v]: = Г [v] (u); Г [u]: = Г [u] (v) (видалити ребро (v, u)) end ifend while
Обгрунтування алгоритму.
Принцип дії цього алгоритму полягає в наступному. Починаючи здовільної вершини, будуємо шлях, видаляючи ребра і запам'ятовуючи вершини встеку, до тих пір поки безліч суміжності черговий вершини не виявитьсяпорожнім, що означає, що шлях подовжити не можна. Зауважимо, що при цьому ми знеобхідністю прийдемо в ту вершину, з якої почали. В іншому випадкуце означало б, що вершина v має непарну ступінь, що неможливо зумові. Таким чином, з графа були видалені ребра циклу, а вершини циклузбережених у стеку S. Зауважимо, що при цьому ступені всіх вершинзалишилися парними. Далі вершина v виводиться в якості першої вершиниейлерова циклу, а процес триває, починаючи з вершини, що стоїть навершині стека.
Мені б хотілося навести тут ще один алгоритм побудови ейлеровациклу в ейлеровом графі - це Алгоритм Флері, він дозволяє пронумеруватиребра вихідного графа так, щоб номер ребра вказував яким за рахунком церебро увійде Ейлером цикл.
Алгоритм Флері:
1. Починаючи з будь-якої вершини v присвоюємо ребру vu номер 1. Викреслюємоце ребро зі списку ребер і переходимо до вершини u.
2. Нехай w - вершина, до якої ми прийшли в результаті виконання 1кроку алгоритму і k - номер, присвоєний чергового ребру на цьому кроці.
Вибираємо довільне ребро інцідентное вершині w, причому міст вибираємотільки в крайньому випадку, якщо інших можливостей вибору ребра неіснує. Надаємо ребру номер k 1 і викреслюємо його. Процес триваєдо тих пір, поки всі ребра не викреслено.
Примітка: Мостом називається ребро, видалення якого позбавляє данийграф зв'язності, тобто збільшує число компонент зв'язності.
Приклад:
Наведемо тепер суворе обгрунтування коректності алгоритму Флеріпобудови ейлерового циклу в даному ейлеровом графі.
Теорема 2. Нехай G (V, E) - Ейлером граф. Тоді наступна процедуразавжди можлива і призводить до побудови ейлерова циклу графа G (V, E).
Виходячи з довільної вершини, йдемо по ребрах графа довільнимчином, дотримуючись при цьому наступні правила:
1) Стираємо ребра по мірі їх проходження (разом з ізольованими вершинами, які при цьому утворюються);
2) На кожному кроці йдемо по мосту тільки в тому випадку, коли немає інших можливостей.
Доказ.
Переконаємося спочатку, що вказана процедура може бути виконана накожному етапі. Нехай ми досягли певної вершини v, почавши з вершини u, v?u. Видаливши ребра шляху з v в u, бачимо, що залишився, граф G1 зв'язків тамістить рівно два непарних вершини v і u. Згідно слідству # 2 з теореми
1 граф G1 має Ейлером шлях P з v в u. Оскільки видалення перший ребраінцідентного u шляху P або не порушує зв'язності G1, або відбуваєтьсявидалення вершини u і залишився граф G2 зв'язків з двома непарними вершинами,то звідси отримуємо, що описане вище побудова завжди можливо на кожномукроці. (Якщо v = u, то доказ не змінюється, якщо є ребра,інцідентние u). Покажемо, що дана процедура призводить до ейлерову шляху.
Дійсно, в G не може бути ребер, що залишилися не пройденими післявикористання останнього ребра, інцідентного u, оскільки в іншомувипадку видалення ребра, суміжного одному з решти, призвело б донезв'язними графу, що суперечить умові 2).
§ 4. Деякі родинні завдання
Відразу ж зазначимо ряд питань, пов'язаних з тим, чи є внеорієнтовані графі Ейлером цикл. Наприклад,
Яке найменше число ланцюгів або циклів необхідне для того, щоб кожнеребро графа G містилося точно в одного ланцюга або в одному циклі? Очевидно,що якщо G має Ейлером цикл або ейлерову ланцюг, то відповіддю буде числоодин.
Ребрах графа G приписані позитивні ваги. Потрібно знайти цикл,що проходить через кожне ребро графа G по крайней мере один раз і такий, щодля нього загальна вага (а саме сума величин njc (aj), де число njпоказує, скільки разів проходив ребро aj, а c (aj) - вага ребра)мінімальний. Очевидно, що якщо G містить Ейлером цикл, то будь-який такий циклбуде оптимальним, тому що кожне ребро проходиться за один раз і вага цьогоциклу дорівнює тоді
Сформульована вище завдання 2) називається завданням китайського листоноші, іїї рішення має багато потенційних програм, як наприклад:
Збір сміття. Розглянемо проблему збору домашнього сміття. Припустимо, щопевний район міста обслуговується єдиною машиною. Ребра графа Gпредставляють дороги, а вершини - перетину доріг. Величина c (aj) - вагаребра - буде відповідати довжині дороги. Тоді проблема збору сміття вданому районі зводиться до знаходження циклу в графі G, що проходить по кожномуребру G принаймні один раз. Потрібно знайти цикл з найменшимкілометражем.
Доставка молока чи пошти. Ще два завдання, коли потрібно визначитимаршрут, що проходить хоча б один раз по кожній з вулиць, виникають придоставки молока чи пошти. Тут завдання полягає у знаходженні маршруту,мінімізує загальний кілометраж (або час, вартість і т.д.).
Перевірка електричних, телефонних або залізничних ліній. Проблемаінспектування розподілених систем (лише деякі з яких названівище) пов'язана з неодмінною вимогою перевірки всіх «компонент». Томувона також є проблемою типу 2) або близька до неї.
§ 5. Завдання китайського листоноші
Розглянемо неорієнтовані граф G (X, A). Серед вершин з X деяківершини (скажімо з безлічі X +) будуть мати парні ступеня, а інші
(з безлічі X-= XX +) - непарні ступеня. Сума ступенів di всіх вершинxiX дорівнює подвоєному числа ребер в A (тому що кожне ребро додає поодиниці до ступенях двох його кінцевих вершин) і тому дорівнює парним числом
2m. Отже, і так як перша сума парних, то друга суматакож парні. Але все di в останній сумі непарні, значить число | X-| вершиннепарній ступеня парне.
Нехай M - безліч таких ланцюгів (скажімо? ij) в G між кінцевимивершинами xi і xj X-, що ніякі два ланцюга не мають однаковихкінцевих вершин, тобто ланцюга з'єднують різні пари вершин з X-іпокривають усі вершини множини X-. Число ланцюгів? Ij в M дорівнює 1/2 | X-| ізавжди ціле, якщо звичайно воно визначено. Припустимо тепер, що всіребра, які утворюють ланцюг? ij, тепер подвоєні (додані штучні ребра).
Так вчиняємо з кожною ланцюгом? IjM і отриманий граф позначимо через G-
(M). Так як деякі ребра з G можуть входити більше ніж в один ланцюг? Ij,то деякі ребра з G-(M) можуть бути (після того як додано всі
«Нові» ланцюга? Ij) Ранок, учетверо і т.д.
Теорема 3. Для будь-якого циклу, що проходить по G, можна вибрати безліч
M, для якого граф G-(M) має Ейлером цикл, відповіднийспочатку взятому циклу в графі G. Це відповідність таке, що якщоцикл проходить по ребру (xi, xj) з G l раз, то в G-(M) існує l ребер
(одне реальне і l-1 штучних) між xi та xj, кожне з якихпроходиться рівно один раз ейлеровим циклом з G-(M). Справедливо і зворотнетвердження.
Доказ.
Якщо цикл проходить по графу G, то принаймні одне ребро,інцідентное кожній вершині xi непарній ступеня, повинні проходити двічі.
(Ребро, прохідне двічі, можна розглядати як два паралельні ребра --одне реальне і одне штучне - і кожне з них проходиться один раз).
Нехай це ребро (xi, xk). У разі непарності ступеня dk вершини xk графа Gдодавання штучного ребра перш за все зробить dk парних, і значитьтільки ребро (xi, xk) потрібно буде проходити двічі, якщо обмежитисярозглядом лише вершин xi і xk. У разі коли dk парних, додаванняштучного ребра зробить dk непарних, а друге ребро виходить з xkповинно бути пройдено двічі (тобто додається ще одне штучнеребро). Така ситуація зберігається до тих пір, поки не зустрінеться вершинанепарній ступеня, про що йшлося вище. Отже, щоб задовольнитиумовою повернення в вершину xi, потрібно двічі пройти весь ланцюг з xi вдеяку іншу вершину непарній ступеня xr X-. Це автоматичнопризводить до виконання умови проходження вершини xr. Аналогічно ідесправа для всіх інших вершин xi X-. Це означає що всі безліч Mланцюгів з G, визначене вище, повинно проходиться двічі, і так як звідсивипливає, що кожне ребро з G-(M) має проходитися один раз, то теоремадоведена.
Алгоритм рішення задачі китайського листоноші негайно випливає здоведеної теореми, тому що все, що для цього необхідно, полягає взнаходженні безлічі ланцюгів M * (ланцюгового паросочетанія для безлічі вершиннепарній ступеня), що дає найменший додатковий вагу. Ц?? кл найменшоговаги, що проходить по G, буде мати вагу, що дорівнює сумі ваг усіх ребер з Gплюс сума ваг ребер в ланцюгах з M *. Це те ж саме, що й сума вагвсіх ребер - реальних і штучних - графа G-(M *).
Опис алгоритму рішення задачі китайського листоноші:
Нехай [cij] - матриця ваг ребер G. Використовуючи алгоритм знаходженнянайкоротшою ланцюги, утворюючи | X-| * | X-| - матрицю D = [dij], де dij - вага ланцюганайменшого ваги, що йде з деякої вершини xiX-в іншу вершинуxjX-.
Знайдемо то ланцюгове паросочетаніе M * для безлічі X-, яке дає найменшийвага (у відповідності з матрицею ваг D). Це можна зробити ефективно здопомогою алгоритму мінімального паросочетанія.
Якщо вершина x? поєднується з іншого вершиною x?, то визначимо ланцюг???найменшого ваги (з x? в x?), що відповідає вазі d??, роблячи крок 1.
Додамо штучні ребра в G, відповідні ребрах з???, І виконаємоце для всіх інших ланцюгів з безлічі M *, в результаті чого вийде граф
G-(M *).
Сума ваг усіх ребер графа G-(M *), знайдена з використанням матриці
[cij] (вага штучного ребра береться рівним вазі паралельного йомуреального ребра), дорівнює мінімальній вазі циклу, що проходить по G. При цьомучисло проходжень циклу по ребру (xi, xj) дорівнює загальній кількості паралельнихребер між xi і xj в G-(M *).
Покажемо, що вказаний вище алгоритм будує мінімальний цикл. Дляцього слід зауважити, що оскільки на кроці 2 ми використовуємо мінімальнепаросочетаніе, ніякі дві найкоротші ланцюга? ij і? pq при такомупаросочетаніі (скажімо, що йдуть з xi в xj і з xp в xq) не можуть матизагального ребра. Якщо б вони мали спільне ребро (xa, xb), то поєднання вершинxi і xq (використовує Подцепи від xi до xb і від xb до xq) і поєднання паривершин xp і xj (використовує Подцепи від xp до xa і від xa до xj) давало бзагальне паросочетаніе ваги 2cab, меншого ніж вага первісногопаросочетанія, що суперечить припущення про мінімальності вихідногопаросочетанія. Отже, граф G-(M *) не повинен містити більше двохпаралельних ребер між будь-якими двома вершинами, тобто оптимальний цикл непроходить, ні за яку ребра графа G більш ніж два рази.
Глава 2. Гамільтона цикли
Назва «Гамільтоном цикл" походить від завдання «Навколосвітняподорож »запропонованої ірландським математиком Вільямом Гамільтоном в
1859 року. Потрібно було, вийшовши з початкової вершини графа, обійти всі йоговершини і повернутися в початкову точку. Граф представляв собою укладанняДодекаедр, кожній з 20 вершин графа було приписано назва великогоміста світу.
§ 1. Основні поняття і визначення
Якщо граф має простий цикл, що містить всі вершини графа по одномуразу, то такий цикл називається Гамільтона циклом, а граф називаєтьсяГамільтона графом. Граф, який містить простий шлях, що проходить черезкожну його вершину, називається полугамільтоновим. Це визначення можнапоширити на орієнтовані графи, якщо шлях вважати орієнтованим.
Гамільтоном цикл не обов'язково містить усі ребра графа. Ясно, щоГамільтона може бути тільки зв'язний граф і, що всякий Гамільтоном графє полугамільтоновим. Зауважимо, що Гамільтоном цикл існує далеконе в кожній графі.
Зауваження.
Будь-який граф G можна перетворити в Гамільтон граф, додавши достатнякількість вершин. Для цього, наприклад, досить до вершин v1, ..., vp графа
G додати вершини u1, ..., up і безліч ребер ((vi, ui)) ((ui, vi +1 )}.
Ступенем вершини v називається число ребер d (v), інцідентних їй, прице петля враховується двічі. У випадку орієнтованого графа розрізняютьступінь do (v) за виходять дуг і di (v) - по вхідних.
§ 2. Умови існування Гамільтона циклу
На відміну від ейлерових графів, де є критерій для графа бутиейлеровим, для гамільтонових графів такого критерію немає. Більше того, завданняперевірки існування Гамільтона циклу виявляється NP-повною.
Більшість відомих фактів має вигляд: «якщо граф G має достатнюкількість ребер, то граф є Гамільтона ». Наведемо кілька такихтеорем.
Теорема Дірака. Якщо в графі G (V, E) cn вершинами (n? 3) виконуєтьсяумова d (v)? n/2 для будь-якого vV, то граф G є Гамільтона.
Доказ.
Від протилежного. Нехай G - не Гамільтоном. Додамо до G мінімальнекількість нових вершин u1, ..., un, поєднуючи їх з усіма вершинами G так,щоб G ': = G + u1 + ... + un був Гамільтона.
Нехай v, u1, w, ..., v - Гамільтон цикл в графі G', причому vG,u1G ', u1G. Така пара вершин v і u1 в Гамільтона цикліобов'язково знайдеться, інакше граф G був би Гамільтона. Тоді wG, w
(u1, ..., un), інакше вершина u1 була б не потрібна. Більш того, вершина vнесуміжних з вершиною w, інакше вершина u1 була б не потрібна.
Далі, якщо в циклі v, u1, w, ..., u ', w', ..., v є вершина w ', суміжна звершиною w, то вершина v 'несуміжних з вершиною v, бо інакше можна булоб побудувати Гамільтоном цикл v, v ', ..., w, w', ..., v без вершини u1, взявшипослідовність вершин w, ..., v 'у зворотному порядку. Звідси випливає, щочисло вершин графа G ', не суміжних з v, не менше числа вершин, суміжних з w.
Але для будь-якої вершини w графа G d (w)? p/2 + n по побудові, в тому числі d (v)
? p/2 + n. Загальне число вершин (суміжних і не суміжні з v) складає n + p-1.
Таким чином, маємо: n + p-1 = d (v) + d (V)? d (w) + d (v)? p/2 + n + p/2 + n = 2n + p.
Отже, 0? n +1, що суперечить тому, що n> 0.
Теорема Оре. Якщо число вершин графа G (V, E) n? 3 і для будь-яких двохнесуміжних вершин u і v виконується нерівність: d (u) + d (v)? n і (u, v) E, то граф G - Гамільтон.
Граф G має Гамільтоном цикл якщо виконується одна з наступнихумов:
Умова пошана: d (vk)? k +1 для k Умова Бонді: з d (vi)? i і d (vk)? k => d (vi) + d (vk)? n (k? i)
Умова вистачало: з d (vk)? k? n/2 => d (vn-k)? nk.
Далі, відомо, що майже всі графи Гамільтона, тобто де H (p) - безліч гамільтонових графів з p вершинами, а G (p) --множина всіх графів з p вершинами. Таким чином, задача відшуканняГамільтона циклу або еквівалентна завдання комівояжера єпрактично затребуваними, але для неї невідомий (і, швидше за все неіснує) ефективний алгоритм рішення.
Приклад графа, коли не виконується умова теореми Дірака, але графє Гамільтона.
N = 8; d (vi) = 3; 3? 8/2 = 4 НЕ Гамільтоном граф, але існуєГамільтоном цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)
§ 3. Завдання пов'язані з пошуком гамільтонових циклів
У ряді галузей промисловості виникає наступне завданняпланування. Потрібно провести n продуктів, використовуючи єдиний типапаратури. Апарат повинен бути перенастроюватиме після того як був зробленийпродукт pi (але до того як розпочато виробництво продукту pj), в залежностівід комбінації (pi, pj). Вартість перенастроювання апаратури постійна і незалежить від продуктів, що виробляються. Припустимо, що ці продуктивиробляються в безперервному циклі, так що після виробництва останнього зn продуктів знову поновлюється в тому ж фіксованому циклі виробництвопершого продукту.
Виникає питання про те, чи може бути знайдена циклічнапослідовність виробництва продуктів pi (i = 1,2, ..., n), що не вимагаєперенастроювання апаратури. Якщо уявити це завдання у виглядіорієнтованого графа, то відповідь на поставлене питання залежить від того,чи має цей орієнтований граф Гамільтоном цикл чи ні.
Якщо не існує циклічної послідовності продуктів, нещо вимагає переналаштування апаратури, то яка має бутипослідовність виробництва з найменшими витратами на перенастроювання,тобто що вимагає найменшого числа необхідних перенастроек?
Таким чином ми розглянемо наступні два завдання.
Завдання 1. Дан орієнтований граф G, потрібно знайти в G Гамільтономцикл (або всі цикли), якщо існує хоча б один такий цикл.
Завдання 2. Дан повний орієнтований цикл G, дуг якого приписанідовільні ваги C = [cij], знайти такий Гамільтоном цикл, який маєнайменший загальна вага. Слід зазначити, що якщо орієнтований граф G неповний, то його можна розглядати як повний орієнтований граф,приписуючи відсутнім дуг нескінченний вагу.
Алгоритми рішення задачі комівояжера та її варіантів мають великекількість практичних застосувань в різних галузях людськоїдіяльності. Розглянемо, наприклад, завдання в якій вантажівка їде зцентральної бази для доставки товарів даного числа споживачів іповертається назад на базу. Вартість перевезення пропорційна пройденоговантажівкою відстані, і при заданій матриці відстаней міжспоживачами маршрут з найменшими транспортними витратами виходить якрішення відповідної задачі комівояжера. Аналогічні типи завданьвиникають під час збирання поштових відправлень з поштових скриньок, складанніграфіка руху шкільних автобусів за заданими зупинок і т.д. Завданнядуже легко узагальнюється і на той випадок, коли доставкою (збором) займаютьсякілька вантажівок, хоча це завдання можна також переформулювати якзавдання комівояжера більшої розмірності. Інші програми включаютьскладання розкладу виконання операцій на машинах, проектуванняелектричних мереж, керування автоматичними лініями і т.д.
Очевидно, що сформульована вище задача (1) є приватнимвипадком задачі (2). Справді, приписуючи випадковим чином дугзаданого орієнтованого графа G кінцеві ваги, отримуємо завданнякомівояжера. Якщо рішення для цього завдання, тобто найкоротший Гамільтономцикл, має кінцеве значення, то це рішення є Гамільтона цикломорієнтованого графа G (тобто відповіддю на завдання 1). Якщо ж рішення маєнескінченне значення, то G не має Гамільтона циклу.
З іншого боку можна дати ще одну інтерпретацію завдання 1).
Розглянемо знову повний орієнтовані граф G1 із загальною матрицею ваг дуг
[cij] і розглянемо задачу знаходження такого Гамільтона циклу, в якомунайдовша дуга мінімальна. Це завдання можна назвати мінімаксного завданнямкомівояжера. Тоді класичну задачу комівояжера в тій же термінологіїможна було б назвати мінісуммной завданням комівояжера. Покажемо тепер, щозавдання (1) дійсно еквівалентна мінімаксного задачі комівояжера.
У вищезгаданому повному орієнтованому графі G1 ми можемо напевнознайти Гамільтоном цикл. Нехай це буде цикл Ф1, і нехай вага найдовшоюйого дуги дорівнює? 1. Видаливши з G1 будь-яку дугу, вага якої не менше? 1,отримаємо орієнтований граф G2. Знайдемо в орієнтованому графі G2Гамільтоном цикл Ф2, і нехай вага його найдовшою дуги дорівнює? 2. Видалимо з
G2 будь-яку дугу, вага якої не менше? 2, і так будемо продовжувати до тих пір,поки не отримаємо орієнтований граф Gm +1, який не містить жодногоГамільтона циклу. Гамільтоном цикл Фm в Gm (з вагою? M) є тоді повизначення рішенням мінімаксного задачі комівояжера, тому що через відсутністьГамільтона циклу в Gm 1 випливає, що в G1 не існує ніякогоГамільтона циклу, що не використовує принаймні одну дугу з вагою,більшим чи рівним? m.
Таким чином, алгоритм знаходження Гамільтона циклу ворієнтованому графі вирішує також мінімаксних завдання комівояжера.
Навпаки, якщо ми маємо в своєму розпорядженні алгоритмом рішення останнього завдання, тоГамільтоном цикл в довільному орієнтованому графі G може бути знайдений здопомогою побудови повного орієнтованого графа G1 з тим же самимбезліччю вершин, що і в G, дуг якого, відповідним дуг з G,приписані одиничні ваги, а іншим дуг - нескінченні ваги. Якщорішення мінімаксного задачі комівояжера для G1 має кінцевий вага (на самомсправі рівний одиниці), то в графі G може бути знайдений відповіднийГамільтоном цикл. Якщо ж рішення має нескінченний вагу, то в графі G неіснує ніякого Гамільтона циклу. Отже, дві зазначені завданняможна розглядати як еквівалентні, оскільки було продемонстровано,що алгоритм знаходження Гамільтона циклу дозволяє вирішувати мінімакснихзавдання комівояжера і навпаки.
З огляду на те, що обидві сформульовані вище задачі (1) і (2) частозустрічаються в практичних ситуаціях і (як ми побачимо пізніше) завдання (1)саму по собі вирішити набагато простіше, ніж як підзадачі задачі (2), ми обидві цізавдання розглянемо окремо.
§ 4. Методи побудови гамільтонових циклів в графі.
Поки невідомо жодного простого критерію або алгебраїчного методу,що дозволяє відповісти на запитання, чи існує чи ні в довільному графі GГамільтоном цикл. Критерії існування, дані вище, являютьтеоретичний інтерес, але є занадто загальними і не придатні длядовільних графів, що зустрічаються на практиці. Алгебраїчні методивизначення гаільтонових циклів не можуть бути застосовані з більш ніждекількома десятками вершин, тому що вони вимагають занадто великого часуроботи і великий пам'яті комп'ютера. Більш прийнятним є спосіб
Робертса та Флореса, який не пред'являє надмірні вимоги до пам'ятікомп'ютера, але час в якому залежить експоненціально від числа вершин уграфі. Однак інший неявний метод перебору має для більшості типівграфів дуже невеликий показник зростання часу обчислень в залежності відчисла вершин. Він може бути використаний для знаходження гамільтонових циклівв дуже великих графах. Нижче будуть описані алгебраїчний метод, перебір зповерненнями, його поліпшення, мультіцепной метод.
§ 5. Алгебраїчний метод побудови гамільтонових циклів
Цей метод включає в себе побудову всіх простих ланцюгів за допомогоюпослідовного множення матриць. «Внутрішнє твір вершин»ланцюга x1, x2, ..., xk-1, xk визначається як вираз виду x2 * x3 * ... xk-1, немістить дві кінцеві вершини x1 і xk. «Модифікована матрицясуміжності »B = [? (i, j)] - це (nЧn) - матриця, в якій? (i, j) - xj, якщоіснує дуга з xi в xj і нуль в іншому випадку. Припустимо тепер,що у нас є матриця PL = [pL (i, j)], де pL (i, j) - сума внутрішніхтворів всіх простих ланцюгів довжини L (L? 1) між вершинами xi і xj дляxi? xj. Покладемо pL (i, i) = 0 для всіх i. Звичайне алгебраїчне твірматриць B * PL = P'L +1 = [p'L 1 (s, t)] визначається як
тобто p'L 1 (s, t) є сумою внутрішніх творів всіх ланцюгів з xs вxt довжини l 1. Так як всі ланцюга з xk в xt, представлені внутрішнімитворами з pL (k, t), є простими, то серед ланцюгів, що виходятьіз зазначеного вислови, не є простими лише ті, внутрішнітвори яких в pL (k, t) містять вершину xs. Таким чином, якщо зp'L 1 (s, t) виключити всі складові, які містять xs (а це можна зробитипростий перевіркою), то отримаємо pL 1 (s, t). Матриця PL 1 = [pL 1 (s, t)], всідіагональні елементи якої рівні 0, є тоді матрицею всіх простихланцюгів довжини L 1.
Обчислюючи потім B * PL 1, знаходимо PL 2 і т.д., поки не буде побудованаматриця Pn-1, що дає всі Гамільтона ланцюга (що мають довжину n-1) між усімапарами вершин. Гамільтона цикли виходять тоді відразу з ланцюгів в Pn-1 ітих дуг з G, які з'єднують початкову та кінцеву вершини кожної ланцюга. Зіншого боку, Гамільтона цикли даються членами внутрішнього творивершин, що стоять у будь-який діагональної клітинці матриці B * Pn-1 (всідіагональні елементи цієї матриці однакові).
Очевидно, що як початкове значення матриці P (тобто P1)слід взяти матрицю суміжності A графа, поклавши всі її діагональніелементи дорівнюють нулю.
Недоліки цього методу цілком очевидні. У процесі множенняматриць (тобто коли L збільшується) кожен елемент матриці PL будескладатися з дедалі більшої кількості членів аж до деякого критичногозначення L, після якого число членів знову почне зменшуватися. Цевідбувається внаслідок того, що для малих значень L і для графів, звичайнозустрічаються на практиці, число ланцюгів довжини L 1, як правило, більше, ніжкількість ланцюгів довжини L, а для великих значень L має місце протилежна картина.
Крім того, так як довжина кожного члена внутрішнього твори вершинзбільшується на одиницю, коли L збільшується на одиницю, то обсягпам'яті, необхідний для зберігання матриці PL, росте дуже швидко аж домаксимуму при певному критичному значенні L, після якого цей обсягзнову починає зменшуватися.
Невелика модифікація вищенаведеного методу дозволяє у багато разівзменшити необхідний обсяг пам'яті і час обчислень. Так як насцікавлять тільки Гамільтона цикли і, як було зазначено вище, вони можутьбути отримані з членів внутрішнього твори будь-якої діагональної осередкуматриці B * Pn-1, то необхідно знати тільки елемент pn-1 (1,1). При цьому накожному етапі не обов'язково обчислювати і зберігати всю матрицю PL, достатньолише знайти перший стовпець PL. Ця модифікація зменшує необхідний обсягпам'яті і час обчислень в n разів. Однак навіть при використанні цієїмодифікації програма для ЕОМ, написана на мові PL/1, який дозволяєпорядково обробку літер і змінна Розподіле пам'яті, не булаздатна знайти всі Гамільтона цикли в неорієнтовані графах з більшніж приблизно 20 вершинами і середнім значенням ступеня вершини, великим 4.
Використовувався комп'ютер IBM 360/65 з пам'яттю 120 000 байтів. Більш того,навіть для графа з вищевказаними «розмірами» даний метод використовувавфактично весь обсяг пам'яті і час обчислень дорівнювало 1.8 хвилини. Чи нетаке вже незначний час для такого невеликого графа.
§ 6. Метод перебору Робертса та Флореса
На противагу алгебраїчних методів, за допомогою яких намагаютьсязнайти одразу все Гамільтона цикли і при реалізації яких припадаєзберігати тому всі ланцюги, які можуть виявитися частинами таких циклів,метод перебору має справу з одним ланцюгом, безперервно продовжуємо аж домоменту, коли або виходить Гамільтоном цикл, або стає ясно, щоцей ланцюг не може привести до Гамільтона циклу. Тоді ланцюг модифікуєтьсядеяким систематичним способом (який гарантує, що врешті-рештбудуть вичерпані всі можливості), після чого продовжується пошукГамільтона циклу. У цьому способі для пошуку потрібно дуже невеликийоб'єм пам'яті і за один раз знаходиться один Гамільтоном цикл.
Наступна схема перебору, що використовує звичайну техніку повернення,була спочатку запропонована Робертсом і Флорес. Починають з побудови
(kЧn)-матриці M = [mij], де елемент mij є i-а вершина (скажімо xq), дляякій у графі G (X, Г) існує дуга (xj, xq). Вершини xq в безлічі
Г (xj) можна порядок довільно, утворивши елементи j-го стовпцяматриці M. Число рядків k матриці M дорівнюватиме найбільшою полустепенірезультату вершини.
Метод полягає в наступному. Деяка початкова вершина (скажімо, x1)вибирається в якості відправної і утворює перший елемент множини S,яке кожен раз буде зберігати вже знайдені вершини будується ланцюга. До Sдодається першому вершина (наприклад, вершина a) у стовпці x1. Потім добезлічі S додається перша можлива вершина (наприклад, вершина b) встовпці a, потім додається до S перша можлива вершина (наприклад,вершина c) в стовпці b і т.д. Під «можливої» вершиною ми розуміємо вершину,ще не належить S. Існують дві причини, що перешкоджають включеннюдеякої вершини на кроці r в безліч S = (x1, a, b, c, ..., xr-1, xr):
У стовпці xr немає можливої вершини.
Ланцюг, що визначається послідовністю вершин в S, має довжину n-1, тобтоє Гамільтона ланцюгом.
У випадку 2) можливі наступні випадки:
У графі G існує дуга (xr, x1), і тому знайдений Гамільтоном цикл.
Дуга (xr, x1) не існує і не може бути отриманий ніякої Гамільтономцикл.
У випадках (1) і (2b) слід вдатися до повернення, у той час яку разі (2a) можна припинити пошук і надрукувати результат (якщо потрібнознайти тільки один Гамільтоном цикл), або (якщо потрібні всі такі цикли)зробити печатку і вдатися до повернення.
Повернення полягає у видаленні останньої включеної вершини xr з S,після чого залишається безліч S = (x1, a, b, c, ..., xr-1), і додаванні до Sперший можливої вершини, наступної за xr, у стовпці xr-1 матриці M.
