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

Курсова робота

З дисципліни” Основи дискретної математики”

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

Зміст

1. Вступ

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

2. Елементи теорії  графів

Основні визначення

Граф (graph) - пари G=(V,E), де V - безліч об'єктів довільної природи, називаних вершинами (vertices, nodes), а E - сімейство пар e_i=(v_i1, v_i2), v_ijÎV, називаних ребрами (edges). У загальному випадку безліч V і/чи сімейство E можуть містити нескінченне число елементів, але ми будемо розглядати тільки кінцеві графи, тобто графи, у яких як V, так і E кінцеві.

У приведеному  визначенні графа E не випадково названо  сімейством пар, а не безліччю. Справа в тім, що елементи E можуть бути не унікальні, тобто можливі кратні ребра. Існує інше, більш коректне визначення: граф визначається як трійка G=(V,E,j), де V - безліч вершин, E - безліч ребер, а j=j(v,u,e) - тримісний предикат (булевська функція від трьох перемінних), що повертає True тоді і тільки тоді, коли ребро e інцидентне вершинам v і u. Однак такі "строгості" у нашому викладі є надмірними.

Якщо  порядок елементів, що входять у e_i, має значення, то граф називається орієнтованим (directed graph), скорочено - орграф (digraph), інакше - неорієнтованим (undirected graph). Ребра орграфа називаються дугами (arcs). Надалі будемо вважати, що термін "граф", застосовуваний без уточнень "орієнтований" чи "неорієнтований", позначає неорієнтований граф.

Приклад: G=(V,E); V={1,2,3,4}; E=<(1,1), (1,2), (1,3), (2,4), (2,4)>

  G  
Якщо e=(v,u), те вершини v і u називаються кінцями ребра. При цьому говорять, що ребро e є суміжним (інцидентним) кожної з вершин v і u. Вершини v і u також називаються суміжними (інцидентними). У загальному випадку, допускаються ребра виду e=(v,v); такі ребра називаються петлями.

Ступінь вершини графа - це число ребер, інцидентних даній вершині, причому петлі враховуються двічі. Оскільки кожне ребро інцидентне двом вершинам, сума ступенів усіх вершин графа дорівнює подвоєній кількості ребер: Sum(deg(v_i), i=1..|V|)=2×|E|.

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

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

Граф, вершини  якого можна розбити на непересічні  підмножини V₁ і V₂ так, що ніякі дві вершини, що належать тому самому підмножині, не суміжні, називається двочастковим (чи біхроматичним, чи графом Кенига) і позначається B_mn (m=|V₁|, n=|V₂|, m+n=|V|). Повний двочастковий граф - такий двочастковий граф, що кожна вершина безлічі V₁ зв'язана з усіма вершинами безлічі V₂, і навпаки; позначення - K_mn. Зауваження: повний двочастковий граф B_mn не є повним (за винятком B₁₁=K₂).

 B₃₃

Підграфом, чи частиною графа G=(V,E) називається такий граф G'=(V',E'), що V'ÍV і дві несуміжні вершини в G не суміжні в G'. Повним підграфом називається підграф, будь-яка пара вершин якого суміжна.

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

Ізоморфізм, гомеоморфізм

Графи G₁=(V₁,E₁) і G₂=(V₂,E₂) називаються ізоморфними (позначення: G₁~G₂), якщо між графами існує взаємо-однозначне відображення j: G₁«G₂ (V₁«V₂, E₁«E₂), що зберігає відповідність між ребрами (дугами) графів, тобто для будь-якого ребра (дуги) e=(v,u) вірно: е'=j(v,u)=(j(v),j(u)) (eÎE₁, е'ÎE₂). Відображення j називається ізоморфним відображенням.

Іншими  словами, ізоморфні графи розрізняються  тільки позначенням вершин.  
 
Ізоморфні графи. Одне з ізоморфних відображень: (0,0), (1,3), (2,5), (3,6), (4,7), (5,2), (6,1), (7,4), (8,9), (9,8).

Характеристики  графів, інваріантні відносно ізоморфизмов графів (тобто приймаючі однакові значення на ізоморфних графах), називаються інваріантами графів.

Підрозділом ребра (v₁,v₂) графи називається операція додавання в граф вершини v' і заміни цього ребра на два суміжних ребра (v₁,v') і (v',v₂): V'=V+{v'}, E'=E-{(v₁,v₂)}+{(v₁,v')}+{(v',v₂).

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

Дві графи  називаються гомеоморфними, якщо для них існують ізоморфні підрозділи.

Шляхи і цикли 

Шляхом у графі (чи маршрутом в орграфі) називається послідовність вершин, що чергується, і ребер (чи дуг - в орграфі) виду _v0, (_v0,_v1), _v1, ... , (v_n-1,v_n), v_n. Число n називається довжиною шляху. Шлях без повторюваних ребер називається ланцюгом, без повторюваних вершин - простим ланцюгом. Шлях може бути замкнутим (v₀=v_n). Замкнутий шлях без повторюваних ребер називається циклом (чи контуром в орграфі); без повторюваних вершин (крім першої й останньої) - простим циклом.

Твердження 1. Якщо в графі існує шлях, що веде з вершини v₀ у v_n, то існує і простий ланцюг між цими вершинами.

Доказ: такий простий ланцюг можна побудувати, "викинувши" зі шляху всі цикли.

~

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

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

Дерева 

Деревом називається довільний зв'язний граф без циклів.

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

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

~

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

Доказ: тому що G - зв'язний, у ньому існує  шлях S між будь-якими двома вершинами v_i і v_j. Якщо e не входить у шлях S=v_i...v_j, то цей шлях існує й у графі G', а виходить, G' залишається зв'язковим. Інакше (e входить у цей шлях): S=v_i...v₁(v₁,v₂)v₂...v_j. За умовою e - входить у деякий цикл, отже, існує замкнутий шлях C=v₂(v₂,v₁)v₁Tv₂ (початком замкнутого шляху ми можемо вважати будь-яку його вершину), причому ребро e=(v₁,v₂) не входить у T (якщо існує шлях між вершинами, то існує і шлях, що є простим ланцюгом - див. утвердження 1). Але тоді існує шлях S'=v_i...v₁Tv₂...v_j, у котрій не входить ребро e=(v₁,v₂) і, отже, цей шлях існує в графі G'.

~

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

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

(1)=>(2): допустимо, що деякі дві вершини v₁ і v₂ графа G з'єднані, принаймні, двома різними простими ланцюгами L₁=u₁....u_k, де u₁=v₁ і u_k=v₂, і L₂=w₁....w_m, де w₁=v₁ і w_m=v₂. З того, що ланцюги є простими і різними, випливає, що існує число j, 1<j<min(k,m), таке, що u_j-1=w_j-1, u_j¹w_j, ... , u_j+a-1¹w_j+b-1, u_j+a=w_j+b, де a³1, b³1. Отже, у G існує цикл ІЗ=u_j-1(u_j-1,u_j)u_j...u_j+a(w_j+b,w_j+b-1)w_j+b-1... w_j(w_j,w_j-1)w_j-1 (див. малюнок) - одержали протиріччя з (1).  
 
(2)=>(1):  
(а) граф G є зв'язковим по визначенню связаність (будь-які дві вершини графа з'єднані ланцюгом);  
(б) допустимо, що в графі G існує цикл, що проходить через деяку вершину v: C=v(v,u₁)u₁....u_k(u_k,v)v. Але це означає, що між v і кожної з вершин u_i існують, принаймні, два різних шляхи L₁=v(v,u₁)u₁...u_i-1(u_i-1,u_i)u_i і L₂=v(v,u_k)u_k...u_i+1(u_i+1,u_i)u_i (шляхи різні, тому що по визначенню в циклі відсутні повторювані ребра). У силу утвердження 1 з цих шляхів можна "виділити" прості ланцюги, що також будуть різні (у L₁і L₂ немає співпадаючих ребер), - одержали протиріччя з (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 вершинами воно дорівнює n^n-2 (без доказу).

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

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

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

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

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

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

Доказ: відповідно до лемма 3 п.2, k=|V|-|E'|, отже, <кількість ребер G, не приналежних E'> = |E|-|E'| = |E|-(|V|-k) = n(G). При додаванні кожного з цих ребер у T з'являється рівно один простий цикл у силу теоремі 3 п.6; всі одержувані при цьому прості цикли різні, тому що кожний з них містить принаймні одне унікальне ребро - те саме ребро G, не приналежне E', що було додано в дерево.

~

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

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

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

Доказ:

1. реалізуємо |V| крапок, що відповідають вершинам графа, на одній прямій;
2. проведемо через цю пряму |E| різних на півплощин;
3. реалізуємо кожне ребро у своїй на півплощині.

~

Виникає питання: чи будь-який граф можна реалізувати  на площині? Відповідь - негативний. Геометричну  реалізацію на площині допускають лише деякі графи; такі графи називаються компланарними.

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

 - 7 вершин, 8 ребер, 3 грані

Формула Ейлера. Для будь-якої геометричної реалізації графа G=(V,E) на площині вірно: p-q+r=2, де p=|V|, q=|E|, r - число граней (без доказу).

Теорема 2. Якщо в зв'язковому планарним графі немає циклів довжини менше k і k³3, то q£k(p-2)/(k-2), де p=|V|, q=|E|.

Доказ (не зовсім формальне): нехай граф реалізований на площині і при цьому вийшло r граней. Нехай q_i - число сторін у i-й грані (див. малюнок). Кожне ребро є стороною двох граней, тому 2q=Sum(q_i, i=1..r). По умови в графі немає циклів довжини менше k, але тоді q_i³k (тому що сторони грані утворять цикл) і 2q=Sum(q_i, i=1..r)³k×r. По формулі Эйлера r=2-p+q, отже, 2q³k×(2-p+q), з чого випливає доказувана нерівність.  
 
- 8 ребер, 3 грані, 3+6+7=16 сторін  
~

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

Доказ: тому що за умовою в графі немає  петель і кратних ребер, у ньому  немає і циклів довжини менше 3, тому, підставляючи k=3 у нерівність теоремі 2, одержуємо: q£k(p-2)/(k-2)=3(p-2).

~

Теорема 3. Граф K₅ не компланарний.

Доказ: K₅ зв'язний, у ньому немає петель і кратних ребер, але наслідок 1 теореми 2 не виконується - q=10>3(p-2)=9. Виходить, K₅ не компланарний.

~

Теорема 4. Граф K₃₃ не компланарний.

Зауваження: використання наслідку 1 теореми 2 тут не допоможе, тому що q=9<3(p-2)=12.

Доказ: у K₃₃ немає циклів довжини менше 4, тому застосуємо нерівність теоремі 2 безпосередньо (при k=4): q=9>4(p-2)/2=8. Отже, K₃₃ не компланарний.

~

Теорема Понтрягіна-Куратовского (критерій компланарності графів). Граф G планарин тоді і тільки тоді, коли він не містить підграфов, гомеоморфних K₅ чи K₃₃.

Доказ: необхідність випливає з тверджень 1-4 (див. нижче), а також з того факту, що графи K₅ і K₃₃ не компланарні (відповідно до теорем 3 і 4).

Твердження 1: якщо графи U₁ і U₂ ізоморфні, то U₁ компланарний тоді і тільки тоді, коли U₂ компланарний.

Доказ: будь-яка геометрична реалізація U₁ є геометричною реалізацією U₂, і навпаки.

Твердження 2: будь-який підрозділ U' графа U компланарний тоді і тільки тоді, коли U компланарний.

Доказ:  
(=>) граф U' компланарний, отже, існує його геометрична реалізація на площині R'. Побудуємо по R' плоску геометричну реалізацію R графа U. Для цього об'єднаємо всі лінії R', що відповідають ребрам U', отриманим у результаті виконання операцій підрозділу ребер. У силу існування R граф U є компланарним.  
<=) граф U компланарний, отже, існує його геометрична реалізація на площині R. Побудуємо по R плоску геометричну реалізацію R' графа U'. Для цього повторимо в будь-якій послідовності операції підрозділу ребер, що привели до побудови U'. Після виконання кожної з цих операцій будемо розбивати лінію, що відповідає ребру, що підрозділяється, на двох ліній (розбивка можна робити в будь-якій крапці, що не збігається з кінцями лінії). У силу існування R' граф U' є компланарним.  
 
Твердження 3: якщо графи U₁ і U₂ гомеоморфні, те U₁ компланарний тоді і тільки тоді, коли U₂ компланарний.

Доказ:  
(=>) за умовою U₁ і U₂ гомеоморфні ® {по визначенню} ® існують їхні ізоморфні підрозділи U₁' і U₂'. За умовою граф U₁ компланарний ® {по утв.2} ® граф U₁' компланарний ® {по утв.1} ® ізоморфний йому граф U₂' компланарний ® {по утв.2} ® граф U₂ компланарний.  
(<=) аналогічно.

Твердження 4: якщо підграф U' графа U не компланарний, те U також не компланарний.

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

Достатність теореми доводиться набагато складніше (див., наприклад, [3]).

~

Існують і інші критерії компланарності графів [3].

Розфарбування графів

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

Хроматичним числом графа G називається мінімальне число n=c(G), таке, що існує правильне n-розфарбування.

Лема 1. У будь-якому компланарному графі без петель і кратних ребер існує вершина ступеня не більш п'яти.

Доказ: допустимо, що ступеня усіх вершин перевершують 5. Тоді 2q=Sum(deg(v_i), i=1..|V|)³6p і q³3p. Але по слідству 1 теореми 2 повинне виконуватися нерівність q£3(p-2)<3p - одержали протиріччя.

~

Теорема про п'ять фарб. Кожен компланарний граф без петель і кратних ребер є не більш ніж 5-хроматичним.

Доказ: (індукцією по числу вершин).

При p=1 твердження теореми вірно. Допустимо, що (*) твердження вірне для всіх p<p₀. Доведемо, що тоді воно вірно і для p₀.

Розглянемо  компланарний граф G без петель і кратних ребер з p₀ вершинами; по лемі 1 у ньому є вершина v₀ ступеня не більш 5. По припущенню індукції (*) граф G', одержуваний видаленням з G вершини v₀ (очевидно, також компланарний), може бути розфарбований не більш, ніж у 5 квітів. Нехай (**) v₁...v_k, k=deg(v₀) - усі вершини-сусіди вершини v₀, розташовані по годинній стрілці відносно v₀. Якщо в розфарбуванні вершин v₁...v_k використовується не більш 4-х квітів, то "пофарбуємо" вершину v₀ у що залишився 5-й колір і одержимо правильне розфарбування.