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

Залишилося  розглянути випадок, коли в розфарбуванні  вершин v₁...v_k у графі G' використовується 5 квітів (k=5). Нехай c_i - колір вершини v_i (i=1..5). Розглянемо безліч A, що складається з вершини v₁ і усіх вершин графа G, крім v₀, у котрі можна дійти з v₁ тільки по вершинах квітів c₁ і c₃. Можливі два випадки:

1. v₃ÏA;
2. v₃ÎA.

У першому  випадку поміняємо кольору вершин безлічі A (c₁«c₃); фарбування при цьому залишиться правильної. Дійсно, безліч A складається по визначенню з усіх вершин квітів c₁ і c₃, у котрі можна дійти з v₁, тому серед вершин, суміжних вершинам, що належать A, немає вершин квітів c₁ чи c₃. Після заміни квітів вершин безлічі A вершина v₁ одержить колір з₃, отже, можна використовувати колір c₁ для "фарбування" вершини v₀ і одержати в такий спосіб правильне розфарбування графа G.

 
 Залишається другий випадок.  З приналежності вершини v₃ безлічі A випливає, що існує шлях з v₁ у v₃ (v₁Sv₃), що проходить тільки по вершинах квітів c₁ і c₃ (див. малюнок). Розглянемо цикл L=v₁Sv₃(v₃,v₀)v₀(v₀,v₁)v₁ і замкнуту криву, що відповідає цьому циклу в геометричній реалізації графа. Вершина v₂ знаходиться усередині цієї замкнутої кривої, а v₄ - зовні. Це випливає, по-перше, з того, що лінії, що відповідають ребрам графа в його геометричній реалізації, не можуть перетинатися (не вважаючи кінців), і, по-друге, з (**).Визначимо безліч B, що складається з вершини v₂ і усіх вершин графа G, крім v₀, у котрі можна дійти з v₂ тільки по вершинах квітів c₂ і c₄. Вершина v₄ не належить B, оскільки будь-який шлях з v₂ у v₄ повинний проходити, принаймні, через одну вершину, що належить циклу L - тобто або через вершину v₀, або через вершину, пофарбовану в кольори c₁ чи c₃. Отже, як і в першому випадку, можна поміняти кольору вершин безлічі B (c₂«c₄) і "пофарбувати" v₀ у c₂.

~

Теорема про чотири фарби. Кожен компланарний граф без петель і кратних ребер є не більш ніж 4-хроматичним.

Проблема  чотирьох фарб залишалася невирішеної  протягом багатьох літ. Затверджується, що ця теорема була доведена за допомогою  хитромудрих міркувань і комп'ютерної  програми в 1976 році (Kenneth Appel and Wolfgang Haken. Every Planar Map is Four Colorable. Contemporary Mathematics 98, American Mathematical Society, 1980). Короткий виклад ідеї їхнього доказу мається в [3].

Графи з атрибутами

У багатьох випадках елементам (вершинам і ребрам) графа ставляться у відповідність  різні дані - атрибути (мітки). Якщо як атрибути використовуються цілі чи речовинні  числа, то такі графи називають  зваженими. Фактично, зважений граф - це функція, визначена на графі. Як атрибути можуть виступати і нечислові дані, тому я буду називати графів з атрибутами позначеними, чи атрибутованнями (Графами-а-графами). Наприклад, структурні формули хімічних сполук представляються молекулярними графами - А-графами, вершини яких відповідають атомам хімічної структури, а ребра - валентним зв'язкам між атомами. Для вершин молекулярного графа визначений, принаймні, атрибут "номер атома в періодичній таблиці елементів", для ребер - "тип валентного зв'язку (одинарна, подвійна, потрійна й ін.)"; можуть використовуватися додаткові атрибути, наприклад, заряд атома.

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

Незалежні безлічі і покриття

Незалежна безліч вершин (НМВ) - безліч вершин графа, ніякі дві вершини якого не інцидентні.

Максимальна незалежна безліч вершин (МНМВ) - НМВ, що не міститься ні в якому іншому НМВ.

Зауваження: у даному визначенні "максимальність" означає "нерозширюваність"; у  загальному випадку граф може мати трохи МНМВ різної потужності.

Найбільша незалежна безліч вершин - НМВ максимальної потужності.

Потужність  найбільшого НМВ (очевидно, це одне з МНМВ) називається верховим числом незалежності графа (а також нещільністю, числом внутрішньої чи стійкості числом верхового упакування графа); позначення - a(G).

Незалежна безліч ребер (НМР), чи паросполучення - безліч ребер графа, ніякі два ребра якого не інцидентні.

Потужність  найбільшого паросполучення називається  числом паросполучення графа; позначення - n(G).

Домінуюче безліч вершин (ДМВ) - така безліч вершин графа, що кожна вершина графа або належить ДМВ, або інцидентна деякій вершині, що належить ДМВ.

Верхове покриття (ВП) - така безліч вершин графа, що кожне ребро графа інцидентне хоча б одній вершині, що належить ДМВ.

Потужність  найменшого верхового покриття називається числом верхового покриття графа; позначення - t(G).

Домінуюче безліч ребер (ДМР), чи реберне покриття - така безліч ребер зв'язного графа, що кожна вершина графа інцидентна хоча б одному ребру, що входить у ДМР.

Потужність  найменшого ДМР називається числом реберного покриття графа; позначення - r(G).

На малюнку позначені реберне покритті графа (пунктиром), МНМВ (білі вершини) і верхове покриття (чорні вершини).

Величини  a(G), n(G), t(G) і r(G) є інваріантами графа. Між цими інваріантами існує зв'язок, установлювана наступними лемами.

Лема 1. Безліч S є найменшим верховим покриттям графа G=(V,E) тоді і тільки тоді, коли T=V(G)\S є найбільшою незалежною безліччю вершин графа.

Доказ:  
(=>)  
1. доведемо, що ніякі дві вершини, що входять у T, не інцидентні (тобто T є НМВ). Допустимо зворотне: $(v_i,v_j)ÎE(G), v_iÎT, v_jÎT. Але це означає, що ребро (v_i,v_j) не покривається безліччю S - протиріччя з визначенням ВП.  
2. T є найбільшим НМВ у силу мінімальності |S| і тотожності |S| + |V(G)\S| º |V(G)|.  
(<=)  
1. доведемо, що кожне ребро G інцидентне хоча б одній вершині S (тобто S є ВП). Допустимо зворотне: $(v_i,v_j)ÎE(G), v_iÏS, v_jÏS. Але це значить, що v_iÎT, v_jÎT - протиріччя з визначенням НМВ.  
2. аналогічно доказу (=>).

~

Наслідок 1 леми 1. Для будь-якого графа G=(V,E) сума числа верхового покриття і верхового числа незалежності постійна і дорівнює кількості вершин G: t(G)+a(G)=|V(G)|.

Лема 2. Якщо граф G=(V,E) не має ізольованих вершин, то сума його числа паросполучення і числа реберного покриття постійна і дорівнює кількості вершин G: n(G)+r(G)=|V(G)|.

Доказ:

1) Нехай  C - найменше реберне покриття G, що  містить r(G) ребер. Розглянемо підграф GC графа G, утворений безліччю ребер C і інцидентними вершинами G; по визначенню покриття в нього входять усі вершини G. Оскільки C є найменшим, GC складається з однієї чи більшої кількості компонентів, кожна з який є деревом (дійсно, у противному випадку можна було б "викинути" з них кільцеві ребра й одержати покриття меншої потужності). По теоремі 2 кількість ребер у кожнім компоненті GS_i графа GC на одиницю менше кількості вершин: |E(GC_i)| = |V(GC_i)| - 1. Просуммировав ці рівності для всіх i, одержимо: |E(GC)| = |V(GC)| - p, де p - кількість компонентів у GС, отже, p = |V(G)| - r(G). З іншого боку, якщо взяти по одному ребру з кожного компонента GC, одержимо деяке паросполучення, отже, n(G) ³ p = |V(G)| - r(G) і n(G) + r(G) ³ |V(G)| (*).

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

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

~

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

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

(без  доказу)

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

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

Теорема 2 (теорема про  весілля). Якщо G - двочастковий граф з частками P₁ і P₂, то G має зроблене паросполучення тоді і тільки тоді, коли |P₁| = |P₂| і, принаймні, одне з P_i (i=1..2) володіє тим властивістю, що для будь-якого X Í P_i виконується нерівність |X| £ |G(X)|.

(без  доказу)

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

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

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

 

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

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

1. усім вершинам v_i приписується мітка - речовинне число: d(s)=0, d(v_i)=+¥ для всіх v_i¹s;
2. мітки усіх вершин, крім s, вважаються тимчасовими, мітка s - постійної;
3. вершина s з'являється поточної (c:=s);
4. усі ребра (дуги) вважаються непоміченими.

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

1. для усіх вершин u_j, інцидентних поточній вершині c, мітки яких є тимчасовими, перераховуємо ці мітки по формулі: d(u_j):=min{d(u_j), d(c)+Weight(c,u_j)} (*), де (c,u_j) - ребро (дуга), що з'єднує вершини c і u_j, а Weight(c,u_j) - її вага; при наявності кратних ребер вибирається ребро з мінімальною вагою;
2. якщо мітки усіх вершин є постійними або рівні +¥, те шлях не існує; ВИХІД("немає рішення");
3. інакше знаходимо серед вершин з тимчасовими мітками (серед усіх таких вершин, а не тільки тих, чиї мітки змінилися в результаті останнього виконання кроку (1)!) вершину x з мінімальною міткою, повідомляємо її мітку постійної, позначаємо ребро (дугу) (с',x), таке, що d(x) = d(с')+Weight(с',x), де с'=з або с' - вершина, що була поточної на одному з попередніх кроків (с'=з, якщо на кроці (1) при u_j=x реалізувалася друга частина формули (*)), і робимо цю вершину поточної (c:=x);
4. якщо c=t, то знайдений шлях довжини d(t), якому можна відновити в такий спосіб: це той шлях між s і t, що складається тільки з позначених на кроці (3) ребер (дуг) (можна довести, що він існує й единий); ВИХІД("рішення знайдене");
5. інакше переходимо на крок (1).

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

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

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