Алгоритм Дейкстра, Детальна інформація

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

Величини \xF061(G), \xF06E(G), \xF074(G) і \xF072(G) є інваріантами графа. Між цими інваріантами існує зв'язок, установлювана наступними лемами.

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

Доказ:

(=>)

1. доведемо, що ніякі дві вершини, що входять у T, не інцидентні (тобто T є НМВ). Допустимо зворотне: \xF024(vi,vj)\xF0CEE(G), vi\xF0CET, vj\xF0CET. Але це означає, що ребро (vi,vj) не покривається безліччю S - протиріччя з визначенням ВП.

2. T є найбільшим НМВ у силу мінімальності |S| і тотожності |S| + |V(G)\S| \xF0BA |V(G)|.

(<=)

1. доведемо, що кожне ребро G інцидентне хоча б одній вершині S (тобто S є ВП). Допустимо зворотне: \xF024(vi,vj)\xF0CEE(G), vi\xF0CFS, vj\xF0CFS. Але це значить, що vi\xF0CET, vj\xF0CET - протиріччя з визначенням НМВ.

2. аналогічно доказу (=>).

~

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

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

Доказ:

1) Нехай C - найменше реберне покриття G, що містить \xF072(G) ребер. Розглянемо підграф GC графа G, утворений безліччю ребер C і інцидентними вершинами G; по визначенню покриття в нього входять усі вершини G. Оскільки C є найменшим, GC складається з однієї чи більшої кількості компонентів, кожна з який є деревом (дійсно, у противному випадку можна було б "викинути" з них кільцеві ребра й одержати покриття меншої потужності). По HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Т2" теоремі 2 кількість ребер у кожнім компоненті GSi графа GC на одиницю менше кількості вершин: |E(GCi)| = |V(GCi)| - 1. Просуммировав ці рівності для всіх i, одержимо: |E(GC)| = |V(GC)| - p, де p - кількість компонентів у GС, отже, p = |V(G)| - \xF072(G). З іншого боку, якщо взяти по одному ребру з кожного компонента GC, одержимо деяке паросполучення, отже, \xF06E(G) \xF0B3 p = |V(G)| - \xF072(G) і \xF06E(G) + \xF072(G) \xF0B3 |V(G)| (*).