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

~

Лема 3. Нехай G=(V,E), p=|V|, q=|E|.

1) число зв'язних компонентів у G більше або дорівнює |V|-|E| (Nкомп.p-q);

2) якщо в G немає циклів, то число зв'язних компонентів у G дорівнює |V|-|E| (Nкомп.=p-q).

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

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

~

Наслідок 1 леми 3: якщо |E||V|-2, те граф G=(V,E) незв'язний (випливає безпосередньо з лемі 3).

Теорема 1. Любою зв'язний граф містить підграф, що є деревом.

Доказ: якщо в зв'язному графі немає циклів, то він уже є деревом по визначенню. Інакше знаходимо будь-як кільцеве ребро і видаляємо його; відповідно до лемми 2 граф залишається зв'язковим. Продовжуємо процес, поки в графі існують цикли. У силу кінцівки графа цей алгоритм побудує дерево за кінцеве число кроків.

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

~

Теорема 2. Для будь-якого дерева G=(V,E) вірно: |V|-|E|=1.

Доказ: по визначенню, у дереві немає циклів, отже, відповідно до леми 3 у ньому рівно |V|-|E| зв'язкових компонент. Але по визначенню дерево зв'язне, тобто складається з одного зв'язного компонента, тому |V|-|E|=1.

~

Теорема 3. Наступні властивості графів еквівалентні:

1.G=(V,E) - дерево;

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

3.G - граф без циклів, у якого |E|=|V|-1;

4.G - зв'язний граф, у якого |E|=|V|-1;

5.G - зв'язний граф, але при видаленні будь-якого ребра він стає незв'язним;