"> Рішення.
Припустимо, що в зв'язкового графі знайдеться Гамільтона циклу. Кожна вершина v включається в гамільтонів цикл З вибором двох інцидентних з нею ребер, а значить, ступінь кожної вершини в Гамільтона циклу (після видалення зайвих ребер) дорівнює 2. Ступінь вершин даного графа - 2 або 3. Вершини ступеня 2 входять в цикл разом з обома інцидентними з ними ребрами. Отже, ребра аb, ае, cd, cb, hi, hg і ij в тому чи іншому порядку входять в гамільтонів цикл С (див. Рис. 3.8).
Ребро bf не може бути частиною циклу С, оскільки кожна вершина такого циклу повинна мати ступінь 2. Значить, ребра fj і fg зобов'язані входити в цикл С, щоб включити в нього вершину f. Але тоді ребра je і gd ніяк можуть належати циклу С, оскільки в іншому випадку в ньому з'являться вершини ступені три. Це змушує нас включити в цикл ребро ed, що приводить нас до протиріччя: ребра, які ми були змушені вибрати, утворюють два незв'язних циклу, а не один, існування якого ми припускали. Висновок: граф, зображений на малюнку 3.8, не є гамільтоновим.
Рис.3.8. До доказу негамільтоновості графа
Розділ 4. Алгоритми Дейкстри і Флойда. Задачі знаходження найкоротшого шляху.
. 1. Математична модель вирішення задач методом Дейкстри
Будь-яка задача, що вимагає знаходження оптимальних маршрутів може бути виконана за допомогою алгоритму Дейкстри. Це стосується і мереж, і транспортних потоків, і обробка графів. Дуже часто використовується не сам алгоритм в чистому вигляді, а його модифікація.
Постановка завдання на максимум виглядає наступним чином:
Нехай дано граф G=(Х, Г), дугам якого приписані ваги (вартості довжини), що задаються матрицею С=[cij].
Завдання про «найкоротшому шляху» полягає в знаходженні найкоротшого шляху від заданої початкової вершини s? x до заданої кінцевої вершини t? x, за умови, що такий шлях існує t? R (s) (тут R (s) - безліч, досяжне з вершини s) і всі цикли в графі мають ненегативний сумарна вага. Бо якщо в графі буде присутній цикл з негативним сумарною вагою і хi - деяка його вершина, то, рухаючись від s до хi, обходячи цей цикл досить багато раз і потрапляючи, нарешті в t, вийде шлях зі як завгодно малим (?? ) вагою. Таким чином, в цьому випадку найкоротшого шляху не існує. Так що неорієнтовані дуги (ребра) графа G не можуть мати негативні ваги.
4.2 Опис методу вирішення завдань
Процедура знаходить шлях мінімальної ваги в графі G=(V, E) заданому ваговій матрицею W у якої елемент дорівнює вазі ребра з'єднує i-ую і j-ую вершини. При цьому передбачається, що всі елементи wij ненегативні. Шлях шукається з вершини номер u1 до вершини номер u2. Процедура використовує алгоритм Дейкстри. Для представлення ваги, рівного нескінченності, використовується число GM, передане в алгоритм. Це число можна задавати залежно від конкретного завдання.
Алгоритм по якому відбувається пошук полягає в наступному:
. Всім вершин приписується вага - дійсне число, d (i):=GM для всіх вершин крім вершини з номером u1, а d (u1):=0.
. Всім вершин приписується мітка m (i):=0.
. Вершина u1 оголошується поточної: t:=u1.
. Для всіх вершин які m (i) дорівнює 0, перераховуємо вагу за формулою
d (i):=min {d (i), d (t) + W [t, i]}.
5. Серед вершин для яких виконано m (i)=0 шукаємо ту для якої d (i) мінімальна, якщо мінімум не знайдений, тобто вага всіх не помічених вершин дорівнює нескінченності (GM), то шлях не існує, покидаємо алгоритм.
. Інакше знайдену вершину c мінімальною вагою вважаємо поточної та помічаємо (m (t):=1).
. Якщо t=u2, то знайдено шлях ваги d (t), покидаємо алгоритм і переходимо на наступний крок.
4.3. Функціональні тести
Завдання 1
Дан граф суміжності для знаходження мінімального шляху від вершини 1 до всіх інших (рис. 4.1.)
Рис. 4.1 Граф до задачі 1
Уявімо граф, у вигляді матриця довжин дуг
Таблиця 1. Представлення матриці до задачі 1
X1X2X3X4X5X6x1? 10187 ?? x210? +1699? x3? 16 ?? 15? x479 ??? 12x5 ????? 23x6 ?? 15? 23?
Стартова вершина, від якої будується дерево найкоротших шляхів - вершина 1.
Задаємо стартові умови: d (1)=0, d (x) =? Офарблюємо вершину 1, y=1.
Знаходимо найближчу вершину до пофарбованої нами, використовуючи формулу:
...
