Алгоритм Дейкстра

2) Нехай M - найбільше паросполучення G, що містить \xF06E(G) ребер. Розглянемо безліч U вершин графа G, не покритих М. З визначення паросполучення випливає, що |U| = |V(G)| - 2\xF0D7|M| = |V(G)| - 2\xF0D7\xF06E(G). Безліч U є незалежним (дійсно, якби дві довільні вершини U "зв'язувалися" ребром, то можна було б додати це ребро M і одержати паросполучення більшої потужності). Оскільки G за умовою не має ізольованих вершин, для кожної вершини, що входить у U, існує ребро, що покриває неї. Позначимо безліч таких ребер через S. Безлічі M і S не перетинаються, тому |M \xF0C8 S| = |M| + |S| = \xF06E(G) + |U| = |V(G)| - \xF06E(G). Об'єднання M і S є реберним покриттям графа по визначенню, отже, \xF072(G) \xF0A3 |M \xF0C8 S| = |V(G)| - \xF06E(G) і \xF072(G) + \xF06E(G) \xF0A3 |V(G)| (**).

З нерівностей (*) і (**) випливає результат леми.

~

Подальші результати справедливі тільки для двочасткових графів.

Теорема 1 (мінімаксная теорема Кеніга). Якщо граф G є двочастковим, то \xF074(G) = \xF06E(G).

(без доказу)

Визначення: зроблене паросполучення (1-фактор) - паросполучення, що покриває усі вершини графа.

Нехай X - довільна підмножина вершин графа G=(V,E). Позначимо через \xF047(X) безліч вершин G, інцидентних вершинам X.

Теорема 2 (теорема про весілля). Якщо G - двочастковий граф з частками P1 і P2, то G має зроблене паросполучення тоді і тільки тоді, коли |P1| = |P2| і, принаймні, одне з Pi (i=1..2) володіє тим властивістю, що для будь-якого X \xF0CD\xF020Pi виконується нерівність |X| \xF0A3 |\xF047(X)|.

(без доказу)

Назва теореми зв'язана з наступною "несерйозною" задачею: визначити, чи можливо "переженити" групу юнаків і дівчин так, щоб усі залишилися задоволені. Якщо допустити, що всі "симпатії" взаємні (припущення, прямо скажемо, нереалістичне), то задача зводиться до перебування зробленого паросполучення в двочастковому графі, вершини однієї з часток якого відповідають юнакам, іншої - дівчинам, і дві вершини зв'язані ребром тоді і тільки тоді, коли юнак і дівчина подобаються один одному.

2.Задача знаходження мінмального шляху в графах:

Алгоритм Дейкстра

Розглянемо задачу про найкоротший шлях. Нехай G=(V,E) - зважений зв'язний граф з ненегативними вагами ребер (дуг). Вага f(e) ребра e інтерпретуємо як відстань між вершинами, суміжними даному ребру. Для заданої початкової вершини s і кінцевої вершини t шукається простий ланцюг, що з'єднує s і t мінімальної ваги. (s,t) - ланцюг мінімальної ваги називають найкоротшим (s,t) - шляхом. Очевидно, рішення задачі існує. Опишемо один з можливих алгоритмів рішення (Е. Дейкстра, 1959 р.).

Ініціалізація:

усім вершинам vi приписується мітка - речовинне число: d(s)=0, d(vi)=+\xF0A5 для всіх vi\xF0B9s;

мітки усіх вершин, крім s, вважаються тимчасовими, мітка s - постійної;

вершина s з'являється поточної (c:=s);

усі ребра (дуги) вважаються непоміченими.

Основна частина:

для усіх вершин uj, інцидентних поточній вершині c, мітки яких є тимчасовими, перераховуємо ці мітки по формулі: d(uj):=min{d(uj), d(c)+Weight(c,uj)} (*), де (c,uj) - ребро (дуга), що з'єднує вершини c і uj, а Weight(c,uj) - її вага; при наявності кратних ребер вибирається ребро з мінімальною вагою;

якщо мітки усіх вершин є постійними або рівні \xF02B\xF0A5, те шлях не існує; ВИХІД("немає рішення");

інакше знаходимо серед вершин з тимчасовими мітками (серед усіх таких вершин, а не тільки тих, чиї мітки змінилися в результаті останнього виконання кроку (1)!) вершину x з мінімальною міткою, повідомляємо її мітку постійної, позначаємо ребро (дугу) (с',x), таке, що d(x) = d(с')+Weight(с',x), де с'=з або с' - вершина, що була поточної на одному з попередніх кроків (с'=з, якщо на кроці (1) при uj=x реалізувалася друга частина формули ( HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "f1" * )), і робимо цю вершину поточної (c:=x);

якщо c=t, то знайдений шлях довжини d(t), якому можна відновити в такий спосіб: це той шлях між s і t, що складається тільки з позначених на кроці (3) ребер (дуг) (можна довести, що він існує й единий); ВИХІД("рішення знайдене");

інакше переходимо на крок (1).

Алгоритм можна модифікувати так, щоб він закінчував роботу після одержання усіма вершинами графа G постійних міток, тобто знаходяться найкоротші шляхи з s в усі вершини графа. Алгоритм визначить основне дерево D найкоротших шляхів з вершини s. Для будь-якої вершини v єдиний (s,v) - шлях у дереві D буде найкоротшим (s,v) - шляхом у графі G.

Алгоритм Дейкстра не завжди знаходить правильне рішення у випадку довільних ваг ребер (дуг) графа. Наприклад, для орграфа, зображеного на малюнку, алгоритм Дейкстра знайде маршрут s(s,t)t довжини 1 між вершинами s і t, а не мінімальний маршрут довжини 2+(-2)=0, що проходить через третю вершину графа.



Приклад орграфа, для якого не будем застосовувати алгоритм Дейкста.

Текст програми написаної на основі алгоритму Дейкстра