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

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

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

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

 

 

Зміст

 
 

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.