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

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

Доказ: доведемо теорему в послідовності (1)<=>(2), (2)=>(3)=>(4)=>(5)=>(6)=>(1).

(1)=>(2): допустимо, що деякі дві вершини v1 і v2 графа G з'єднані, принаймні, двома різними простими ланцюгами L1=u1....uk, де u1=v1 і uk=v2, і L2=w1....wm, де w1=v1 і wm=v2. З того, що ланцюги є простими і різними, випливає, що існує число j, 1
(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 (шляхи різні, тому що по визначенню в циклі відсутні повторювані ребра). У силу утвердження 1 з цих шляхів можна "виділити" прості ланцюги, що також будуть різні (у L1і L2 немає співпадаючих ребер), - одержали протиріччя з (2).

З (а), (б) і визначення дерева випливає, що G є деревом. (2)=>(3): по теорема 2;

(3)=>(4): по лемма 3;

(4)=>(5): т.к. |E|=|V|-1, те після видалення ребра в новому графі буде |V|-2 ребер, і по слідству 1 лемки 3 цей граф буде незв'язним;

(5)=>(6):

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

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

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

~

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

Існування основного підграфа для будь-якого зв'язного графа доводиться теоремою 1.

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

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

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