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

(2)=>(1):

(а) граф G є зв'язковим по визначенню связаність (будь-які дві вершини графа з'єднані ланцюгом);

(б) допустимо, що в графі G існує цикл, що проходить через деяку вершину v: C=v(v,u1)u1....uk(uk,v)v. Але це означає, що між v і кожної з вершин ui існують, принаймні, два різних шляхи L1=v(v,u1)u1...ui-1(ui-1,ui)ui і L2=v(v,uk)uk...ui+1(ui+1,ui)ui (шляхи різні, тому що по визначенню в циклі відсутні повторювані ребра). У силу HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Утв1" утвердження 1 з цих шляхів можна "виділити" прості ланцюги, що також будуть різні (у L1і L2 немає співпадаючих ребер), - одержали протиріччя з (2).

З (а), (б) і визначення дерева випливає, що G є деревом. (2)=>(3): по HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Т2" теорема 2 ;

(3)=>(4): по HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Лемма3" лемма 3 ;

(4)=>(5): т.к. |E|=|V|-1, те після видалення ребра в новому графі буде |V|-2 ребер, і по HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Сл1лем3" слідству 1 лемки 3 цей граф буде незв'язним;

(5)=>(6):

(a) доведемо першу частину твердження (G - граф без циклів): допустимо, у G є цикли; але тоді при видаленні будь-якого кільцевого ребра він залишиться зв'язковим, що суперечить (4);

(б) доведемо другу частину твердження (при додаванні будь-якого ребра в G з'являється рівно один простий цикл): зі связаність графа і HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Лемма1" лемма 1 випливає, що при додаванні будь-якого ребра в G з'являється, як мінімум, один простий цикл; у силу (2) цей простий цикл єдиний (зворотне означало б, що в G існують вершини, з'єднані більш ніж одним простим ланцюгом);

(6)=>(1): допустимо, G - не дерево, тобто граф чи не зв'язний містить цикли. Циклів не може бути в силу (5а), тому залишається варіант: G - незв'язний і складається мінімум із двох компонентів. Але тоді при додаванні ребра між вершинами, що належать різним компонентам, цикли не утворяться, а це суперечить (5б).

~

Основним деревом (кістяком) зв'язного графа називається будь-який його основний підграф, що є деревом.

Існування основного підграфа для будь-якого зв'язного графа доводиться HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Т1" теоремою 1 .

Загальне число основних дерев зв'язного графа може бути дуже велика. Так, для повного графа з n вершинами воно дорівнює nn-2 (без доказу).



Граф і два його основних дерева (вилучені ребра показані пунктиром).

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

Цикломатичне число і фундаментальні цикли

Цикломатичрим числом графа G=(V,E) називається з k зв'язковими компонентами називається число \xF06E(G)=|E|-|V|+k.

Фундаментальним циклом графа G=(V,E) з основним деревом T=(V,E') називається простий цикл, одержуваний у результаті додавання в T одного з ребер G, не приналежного E'.

Твердження 1. Кількість фундаментальних циклів графа G=(V,E) при будь-якому фіксованому основним дереві T=(V,E') дорівнює цикломатичному числу G.

Доказ: відповідно до HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Лемма3" лемма 3 п.2 , k=|V|-|E'|, отже, <кількість ребер G, не приналежних E'> = |E|-|E'| = |E|-(|V|-k) = \xF06E(G). При додаванні кожного з цих ребер у T з'являється рівно один простий цикл у силу HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Т3" теоремі 3 п.6 ; всі одержувані при цьому прості цикли різні, тому що кожний з них містить принаймні одне унікальне ребро - те саме ребро G, не приналежне E', що було додано в дерево.

~

Компланарні графи

Зіставивши вершинам графа крапки на чи площині в просторі, а ребрам - лінії, що з'єднують крапки, що відповідають кінцям ребра, можна одержати діаграму - візуальне представлення даного графа.

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

Теорема 1. Для будь-якого графа існує геометрична реалізація в тривимірному евклідовому просторі.

Доказ:

реалізуємо |V| крапок, що відповідають вершинам графа, на одній прямій;