Размещено на http://www.allbest.ru/

18

Размещено на http://www.allbest.ru/

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

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

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

Зміст

Вступ

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

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

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

1.3 Шляхи і цикли

1.4 Дерева

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

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

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

1.8 Графи з атрибутами

1.9 Незалежні безлічі і покриття

2. Задача знаходження мінімального шляху в графах

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

2.2 Текст програми написаної на основі алгоритму Дейкстра

2.3 Результат виконання програми

2.4 Графічне зображення початкового графа та дерева мінімальних шляхів після виконання програми

Висновок

Література

Вступ

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

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

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

Граф (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.

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

Графи

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 шляхом кінцевого числа підрозділів ребер.

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

1.3 Шляхи і цикли

Шляхом у графі (чи маршрутом в орграфі) називається послідовність вершин, що чергується, і ребер (чи дуг - в орграфі) виду _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.4 Дерева

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

Лема 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.

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

Цикломатичрим числом графа 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) = ?(G). При додаванні кожного з цих ребер у T з'являється рівно один простий цикл у силу теоремі 3 п.6; всі одержувані при цьому прості цикли різні, тому що кожний з них містить принаймні одне унікальне ребро - те саме ребро G, не приналежне E', що було додано в дерево.

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

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

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

Теорема 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].

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

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

Хроматичним числом графа G називається мінімальне число n=?(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-й колір і одержимо правильне розфарбування.

Залишилося розглянути випадок, коли в розфарбуванні вершин v₁...v_k у графі G' використовується 5 квітів (k=5). Нехай c_i - колір вершини v_i (i=1..5). Розглянемо безліч A, що складається з вершини v₁ і усіх вершин графа G, крім v₀, у котрі можна дійти з v₁ тільки по вершинах квітів c₁ і c₃. Можливі два випадки:

1. v₃ПA;

2. v₃ОA.

У першому випадку поміняємо кольору вершин безлічі A (c₁?c₃); фарбування при цьому залишиться правильної. Дійсно, безліч A складається по визначенню з усіх вершин квітів c₁ і c₃, у котрі можна дійти з v₁, тому серед вершин, суміжних вершинам, що належать A, немає вершин квітів c₁ чи c₃. Після заміни квітів вершин безлічі A вершина v₁ одержить колір з₃, отже, можна використовувати колір c₁ для "фарбування" вершини v₀ і одержати в такий спосіб правильне розфарбування графа G.

Залишається другий випадок. З приналежності вершини v₃ безлічі A випливає, що існує шлях з v₁ у v₃ (v₁Sv₃), що проходить тільки по вершинах квітів c₁ і c₃ (див. малюнок). Розглянемо цикл L=v₁Sv₃(v₃,v₀)v₀(v₀,v₁)v₁ і замкнуту криву, що відповідає цьому циклу в геометричній реалізації графа. Вершина v₂ знаходиться усередині цієї замкнутої кривої, а v₄ - зовні. Це випливає, по-перше, з того, що лінії, що відповідають ребрам графа в його геометричній реалізації, не можуть перетинатися (не вважаючи кінців), і, по-друге, з (**).Визначимо безліч B, що складається з вершини v₂ і усіх вершин графа G, крім v₀, у котрі можна дійти з v₂ тільки по вершинах квітів c₂ і c₄. Вершина v₄ не належить B, оскільки будь-який шлях з v₂ у v₄ повинний проходити, принаймні, через одну вершину, що належить циклу L - тобто або через вершину v₀, або через вершину, пофарбовану в кольори c₁ чи c₃. Отже, як і в першому випадку, можна поміняти кольору вершин безлічі B (c₂?c₄) і "пофарбувати" v₀ у c₂.

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

Проблема чотирьох фарб залишалася невирішеної протягом багатьох літ. Затверджується, що ця теорема була доведена за допомогою хитромудрих міркувань і комп'ютерної програми в 1976 році (Kenneth Appel and Wolfgang Haken. Every Planar Map is Four Colorable. Contemporary Mathematics 98, American Mathematical Society, 1980). Короткий виклад ідеї їхнього доказу мається в [3].

1.8 Графи з атрибутами

У багатьох випадках елементам (вершинам і ребрам) графа ставляться у відповідність різні дані - атрибути (мітки). Якщо як атрибути використовуються цілі чи речовинні числа, то такі графи називають зваженими. Фактично, зважений граф - це функція, визначена на графі. Як атрибути можуть виступати і нечислові дані, тому я буду називати графів з атрибутами позначеними, чи атрибутованнями (Графами-а-графами). Наприклад, структурні формули хімічних сполук представляються молекулярними графами - А-графами, вершини яких відповідають атомам хімічної структури, а ребра - валентним зв'язкам між атомами. Для вершин молекулярного графа визначений, принаймні, атрибут "номер атома в періодичній таблиці елементів", для ребер - "тип валентного зв'язку (одинарна, подвійна, потрійна й ін.)"; можуть використовуватися додаткові атрибути, наприклад, заряд атома.

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

1.9 Незалежні безлічі і покриття

Незалежна безліч вершин (НМВ) - безліч вершин графа, ніякі дві вершини якого не інцидентні.

Максимальна незалежна безліч вершин (МНМВ) - НМВ, що не міститься ні в якому іншому НМВ.

Зауваження: у даному визначенні "максимальність" означає "нерозширюваність"; у загальному випадку граф може мати трохи МНМВ різної потужності.

Найбільша незалежна безліч вершин - НМВ максимальної потужності.

Потужність найбільшого НМВ (очевидно, це одне з МНМВ) називається верховим числом незалежності графа (а також нещільністю, числом внутрішньої чи стійкості числом верхового упакування графа); позначення - ?(G).

Незалежна безліч ребер (НМР), чи паросполучення - безліч ребер графа, ніякі два ребра якого не інцидентні.

Потужність найбільшого паросполучення називається числом паросполучення графа; позначення - n(G).

Домінуюче безліч вершин (ДМВ) - така безліч вершин графа, що кожна вершина графа або належить ДМВ, або інцидентна деякій вершині, що належить ДМВ.

Верхове покриття (ВП) - така безліч вершин графа, що кожне ребро графа інцидентне хоча б одній вершині, що належить ДМВ.

Потужність найменшого верхового покриття називається числом верхового покриття графа; позначення - t(G).

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

Потужність найменшого ДМР називається числом реберного покриття графа; позначення - ?(G).

На малюнку позначені реберне покритті графа (пунктиром), МНМВ (білі вершини) і верхове покриття (чорні вершини).

Величини a(G), n(G), t(G) і r(G) є інваріантами графа. Між цими інваріантами існує зв'язок, установлювана наступними лемами.

Лема 1. Безліч S є найменшим верховим покриттям графа G=(V,E) тоді і тільки тоді, коли T=V(G)\S є найбільшою незалежною безліччю вершин графа.

Доказ:

(=>)

1. доведемо, що ніякі дві вершини, що входять у T, не інцидентні (тобто T є НМВ). Допустимо зворотне:

$(v_i,v_j)ОE(G), v_iОT, v_jОT

Але це означає, що ребро (v_i,v_j) не покривається безліччю S - протиріччя з визначенням ВП.

2. T є найбільшим НМВ у силу мінімальності |S| і тотожності

|S| + |V(G)\S| є |V(G)|

(<=)

1. доведемо, що кожне ребро G інцидентне хоча б одній вершині S (тобто S є ВП). Допустимо зворотне:

$(v_i,v_j)ОE(G), v_iПS, v_jПS

Але це значить, що v_iОT, v_jОT - протиріччя з визначенням НМВ.

2. аналогічно доказу (=>).

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

G: t(G)+a(G)=|V(G)|

Лема 2. Якщо граф G=(V,E) не має ізольованих вершин, то сума його числа паросполучення і числа реберного покриття постійна і дорівнює кількості вершин

G: n(G)+r(G)=|V(G)|

Доказ:

1) Нехай C - найменше реберне покриття G, що містить ?(G) ребер. Розглянемо підграф GC графа G, утворений безліччю ребер C і інцидентними вершинами G; по визначенню покриття в нього входять усі вершини G. Оскільки C є найменшим, GC складається з однієї чи більшої кількості компонентів, кожна з який є деревом (дійсно, у противному випадку можна було б "викинути" з них кільцеві ребра й одержати покриття меншої потужності). По теоремі 2 кількість ребер у кожнім компоненті GS_i графа GC на одиницю менше кількості вершин:

|E(GC_i)| = |V(GC_i)| - 1

Просуммировав ці рівності для всіх i, одержимо:

|E(GC)| = |V(GC)| - p

де p - кількість компонентів у GС, отже,

p = |V(G)| - r(G)

З іншого боку, якщо взяти по одному ребру з кожного компонента GC, одержимо деяке паросполучення, отже,

n(G) і p = |V(G)| - r(G) і n(G) + r(G) і |V(G)| (*)

2) Нехай M - найбільше паросполучення G, що містить ?(G) ребер. Розглянемо безліч U вершин графа G, не покритих М. З визначення паросполучення випливає, що

|U| = |V(G)| - 2Ч|M| = |V(G)| - 2Чn(G)

Безліч U є незалежним (дійсно, якби дві довільні вершини U "зв'язувалися" ребром, то можна було б додати це ребро M і одержати паросполучення більшої потужності). Оскільки G за умовою не має ізольованих вершин, для кожної вершини, що входить у U, існує ребро, що покриває неї. Позначимо безліч таких ребер через S. Безлічі M і S не перетинаються, тому

|M И S| = |M| + |S| = n(G) + |U| = |V(G)| - n(G)

Об'єднання M і S є реберним покриттям графа по визначенню, отже

r(G) Ј |M И S| = |V(G)| - n(G) і r(G) + n(G)--Ј |V(G)| (**).

З нерівностей (*) і (**) випливає результат леми.

Подальші результати справедливі тільки для двочасткових графів.

Теорема 1 (мінімаксная теорема Кеніга). Якщо граф G є двочастковим, то

t(G) = n(G) (без доказу)

Визначення: зроблене паросполучення (1-фактор) - паросполучення, що покриває усі вершини графа.

Нехай X - довільна підмножина вершин графа G=(V,E). Позначимо через G(X) безліч вершин G, інцидентних вершинам X.

Теорема 2 (теорема про весілля). Якщо G - двочастковий граф з частками P₁ і P₂, то G має зроблене паросполучення тоді і тільки тоді, коли |P₁| = |P₂| і, принаймні, одне з P_i (i=1..2) володіє тим властивістю, що для будь-якого X Н--P_i виконується нерівність |X| Ј--|G(X)|. (без доказу)

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

2. Задача знаходження мінімального шляху в графах

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

Розглянемо задачу про найкоротший шлях. Нехай G=(V,E) - зважений зв'язний граф з ненегативними вагами ребер (дуг). Вага f(e) ребра e інтерпретуємо як відстань між вершинами, суміжними даному ребру. Для заданої початкової вершини s і кінцевої вершини t шукається простий ланцюг, що з'єднує s і t мінімальної ваги. (s,t) - ланцюг мінімальної ваги називають найкоротшим (s,t) - шляхом. Очевидно, рішення задачі існує. Опишемо один з можливих алгоритмів рішення (Е. Дейкстра, 1959 р.).

Ініціалізація:

1. усім вершинам v_i приписується мітка - речовинне число:

d(s)=0, d(v_i)=+Ґ для всіх v_i№s

2. мітки усіх вершин, крім s, вважаються тимчасовими, мітка s - постійної;

3. вершина s з'являється поточної (c:=s);

4. усі ребра (дуги) вважаються непоміченими.

Основна частина:

1. для усіх вершин u_j, інцидентних поточній вершині c, мітки яких є тимчасовими, перераховуємо ці мітки по формулі:

d(u_j):=min{d(u_j), d(c)+Weight(c,u_j)} (*)

де (c,u_j) - ребро (дуга), що з'єднує вершини c і u_j, а Weight(c,u_j) - її вага; при наявності кратних ребер вибирається ребро з мінімальною вагою;

2. якщо мітки усіх вершин є постійними або рівні +Ґ, те шлях не існує; ВИХІД("немає рішення");

3. інакше знаходимо серед вершин з тимчасовими мітками (серед усіх таких вершин, а не тільки тих, чиї мітки змінилися в результаті останнього виконання кроку (1)!) вершину x з мінімальною міткою, повідомляємо її мітку постійної, позначаємо ребро (дугу) (с',x), таке, що

d(x) = d(с')+Weight(с',x)

де с'=з або с' - вершина, що була поточної на одному з попередніх кроків (с'=з, якщо на кроці (1) при u_j=x реалізувалася друга частина формули (*)), і робимо цю вершину поточної (c:=x);

4. якщо c=t, то знайдений шлях довжини d(t), якому можна відновити в такий спосіб: це той шлях між s і t, що складається тільки з позначених на кроці (3) ребер (дуг) (можна довести, що він існує й единий); ВИХІД("рішення знайдене");

5. інакше переходимо на крок (1).

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

Алгоритм Дейкстра не завжди знаходить правильне рішення у випадку довільних ваг ребер (дуг) графа. Наприклад, для орграфа, зображеного на малюнку, алгоритм Дейкстра знайде маршрут s(s,t)t довжини 1 між вершинами s і t, а не мінімальний маршрут довжини 2+(-2)=0, що проходить через третю вершину графа.

Приклад орграфа, для якого не будем застосовувати алгоритм Дейкста.

2.2 Текст програми написаної на основі алгоритму Дейкстра

/* Алгоритм пошуку дерева найкоротших шляхів у зваженому графі */

/* Е.Дейкстра 1959 р. */

#include <stdio.h>

#include <stdlib.h>

#include <float.h>

int load_matrix(int n, double* weigh);/* Уведення матриці ваг*/

int deik(int n, int s, double* weigh, int* Q, double* L);/* Алгоритм пошуку*/

void print(int n, int* Q, double* L);/* Висновок результату*/

void main(void){

int n=0,s=0,ret=0;

double *weigh;

int* Q;/* Масив міток покажчиків на попередню вершину*/

double* L;/* Масив найдених ваг шляху до вершини*/

printf("\nАлгоpитм пошуку дерева найкоротших шляхів у зваженому графі.\n");

printf("Е.Дейкстpа, 1959 р.\n");

printf("\nВведіть кількість вершин..");

scanf("%d",&n);

if (n <= 1){

printf("\nКількість вершин повинне бути більше одиниці!\n");

exit(1);

}

printf("\nВведіть початкову вершину..");

scanf("%d",&s);

s--;

if ((s < 0)||(s > (n-1))){

printf("\nПочаткова вершина зазначена неправильно! \n");

exit(1);

}

Q=malloc(n*sizeof(int));

L=malloc(n*sizeof(double));

weigh=malloc(sizeof(double)*n*n);

if ((weigh == NULL)||(Q == NULL)||(L == NULL)){

printf("\nHедостатньо пам'яті для завантаження масиву! \n");

exit(2);

}

ret=load_matrix(n,weigh);

if (ret != 0){

printf("\nПомилка введення даних!\n");

exit(5);

}

ret=deik(n,s,weigh,Q,L);

if (ret != 0){

switch (ret){

case 1 :

printf("\nГpаф не є зв'язаним!\n");

exit(3);

case 2 :

printf("\nHедостаточно пам'яті для роботи!\n");

exit(4);

}

}

print(n,Q,L);

free(weigh);

free(Q);

free(L);

}

int load_matrix(int n, double* weigh){

int i,j,k;

double tmp;

for (i=0; i < n; i++){

for (j=0; j < n; j++){

weigh[n*i+j]=(-1);

}

}

printf("\nВведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.");

for (i=0; i < n; i++){

for (j=i+1; j < n; j++){

printf("\nВеpшини %d і %d ",i+1,j+1);

k=scanf("%lf",&tmp);

if (k != 1){return(1);}

weigh[i*n+j]=tmp;

}

}

return(0);

}

int deik(int n,int s, double* weigh, int* Q, double* L){

int i,j,k;

int* QI;/* Масив індикаторів сталості міток покажчиків */

double tmp;

QI=calloc(n,sizeof(int));

if (QI == NULL){return(2);}

QI[s]=1;

for (i=0; i < n; i++){

Q[i]=(-1);

L[i]=DBL_MAX;

}

Q[s]=s;

L[s]=0;

weigh[n*(n-1)+s]=0;

for (k=0; k < n; k++){/* Основний цикл по вершинах*/

for (i=0; i < n; i++){/* Цикл по рядках матриці ваг*/

for (j=i+1; j < n; j++){/* Цикл по стовпцях матриці ваг*/

if ((QI[i]+QI[j] == 1)&&

(QI[i]*QI[j] == 0)&&

(weigh[i*n+j] != (-1.0))&&

(((QI[i] == 1)&&((L[i]+weigh[i*n+j]) < L[j]))||

((QI[j] == 1)&&((L[j]+weigh[i*n+j]) < L[i])))){

if (QI[i] == 1){

L[j]=L[i]+weigh[i*n+j];

Q[j]=i;

}

else{

L[i]=L[j]+weigh[i*n+j];

Q[i]=j;

}

}

}

}

for (tmp=DBL_MAX,i=0; i < n; i++){

if ((tmp > L[i])&&(QI[i] == 0)){

tmp=L[i];

j=i;

}

}

QI[j]=1;

}

free(QI);

return(0);

}

void print(int n, int* Q, double* L){

int i;

printf("\n\nДеpево найкоротших шляхів:");

for (i=0; i < n; i++){

printf("\nВеpшина: %d Предок: %d Вага: %5.2lf",i+1,Q[i]+1,L[i]);

}

}_

2.3 Результат виконання програми

Алгоритм пошуку дерева найкоротших шляхів у зваженому графі. Е.Дейкстра, 1959 р.

Уведіть кількість вершин.. 6

Уведіть початкову вершину.. 6

Уведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.

Вершини 1 і 2 2

Вершини 1 і 3 -1

Вершини 1 і 4 2

Вершини 1 і 5 -1

Вершини 1 і 6 5

Вершини 2 і 3 2

Вершини 2 і 4 -1

Вершини 2 і 5 2

Вершини 2 і 6 -1

Вершини 3 і 4 -1

Вершини 3 і 5 -1

Вершини 3 і 6 12

Вершини 4 і 5 1

Вершини 4 і 6 2

Вершини 5 і 6 5

Дерево найкоротших шляхів:

Вершина: 1 Предок: 4 Вага: 4.00

Вершина: 2 Предок: 5 Вага: 5.00

Вершина: 3 Предок: 2 Вага: 7.00

Вершина: 4 Предок: 6 Вага: 2.00

Вершина: 5 Предок: 4 Вага: 3.00

Вершина: 6 Предок: 6 Вага: 0.00_

2.4 Графічне зображення початкового графа та дерева мінімальних шляхів після виконання програми

Тестовий зв'язний зважений для алгоритму пошуку дерева шляхів з вершини 6 (Е. Дейкстра 1959р.)

Рішення: дерево найкоротших шляхів з вершини 6

Висновок

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

Література

1. Зыков А.А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.

2. Харари Ф. Теорія графів. - М.: Світ, 1973.

3. Зыков А.А. Основи теорії графів. - М.: Наука, 1987.

4. Кристофидес Н. Теорія графів. Алгоритмічний підхід. - М.: Світ, 1978.

5. Майника Э. Алгоритми оптимізації на мережах і графах. - М.: Світ, 1981.

6. Ловас Л., Пламмер М. Прикладні задачі теорії графів. Теорія паросочетаний у математику, фізику, хімії. - М.: Світ, 1998.

Размещено на Allbest.ru

...