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

Лема 1. Нехай G=(V,E) - зв'язний граф, вершини v1 і v2 якого не суміжні. Тоді в графі G'=(V,E+(v1,v2)) існує простий цикл, що проходить через ребро (v1,v2).

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

~

Лема 2. Нехай G=(V,E) - зв'язний граф, ребро e=(v1,v2) якого входить у деякий цикл. Тоді граф G'=(V,E-e) - також зв'язний, тобто при видаленні кільцевого ребра (ребра, що входить у деякий цикл) зі зв'язного графа цей граф залишається зв'язковим.

Доказ: тому що G - зв'язний, у ньому існує шлях S між будь-якими двома вершинами vi і vj. Якщо e не входить у шлях S=vi...vj, то цей шлях існує й у графі G', а виходить, G' залишається зв'язковим. Інакше (e входить у цей шлях): S=vi...v1(v1,v2)v2...vj. За умовою e - входить у деякий цикл, отже, існує замкнутий шлях C=v2(v2,v1)v1Tv2 (початком замкнутого шляху ми можемо вважати будь-яку його вершину), причому ребро e=(v1,v2) не входить у T (якщо існує шлях між вершинами, то існує і шлях, що є простим ланцюгом - див. HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Утв1" утвердження 1 ). Але тоді існує шлях S'=vi...v1Tv2...vj, у котрій не входить ребро e=(v1,v2) і, отже, цей шлях існує в графі G'.

~

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

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

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

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

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

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

~

Наслідок 1 леми 3: якщо |E|\xF0A3|V|-2, те граф G=(V,E) незв'язний (випливає безпосередньо з HYPERLINK "http://www.caravan.ru/~alexch/graphs/" \l "Лемма3" лемі 3 ).

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

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

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

~

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

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

~

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

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

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

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

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

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

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