Графи та їх застосування

Для  орграфів  означено  три  типи  компонент  зв’язності. Сильною  компонентою орграфа називається максимальний  сильно  зв’язний  підграф,  однобічною – максимальний  однобічний і слабкою – максимальний  слабкий підграф [24, c.153].

Неорієнтований мультиграф,  який  отримується  в  результаті  зняття  орієнтації  з дуг  орграфа G,  називається основою орграфа G. Орграф  є слабо зв’язним  тоді  й тільки  тоді,  коли  його  основа – зв’язний   мультиграф. (Поняття зв’язності  для мультиграфів означається аналогічно зв’язності неорієнтованих графів.)

Орієнтацією  графа G  називається орграф,  який  одержується приписуванням деякої  орієнтації  кожному ребру графа G.  При цьому граф  G  є основою своєї орієнтації.

2.1.3. Турніри

 

Турніром, або повним орграфом, називається направлений орграф, у якому будь-які дві вершини інцидентні деякій дузі. Іншими словами, орграф є турніром тоді й тільки  тоді,  коли  його  основа  є повним  графом.  Існує єдиний (з  точністю  до ізоморфізму)  турнір  з  однією  вершиною (рис. 2.5, а),  єдиний  турнір  з двома вершинами (рис.2.5, б)  і два турніри з трьома вершинами (рис.2.5, в, г). Турнір на рис.2.5, в  називається транзитивною  трійкою,  а турнір  рис. 2.5, г – циклічною трійкою.

Рис.2.5.

Відмітимо,  що  в  результаті  вилучення  довільної  вершини  нетривіального турніра одержується  турнір.

Теорема 2.5. Для будь-якої вершини v n-вершинного турніра          δ⁺(v)+δ^-(v) = n-1.

Доведення:  За теоремою 1 δ⁺(v)+δ^- (v) = δ(v). Кожна вершина дугою з’єднана з довільною іншою вершиною турніра рівно однією дугою, тому   δ(v) = n-1,  звідки  δ⁺(v)+δ^-(v) = n-1. 

Доведено 

Зауважимо, що теорема 5 дає  лише необхідну, але не достатню умову  того, щоб орграф був турніром. Відповідний  приклад наведено на рис. 6.

Рис.2.6.

Теорема 2.6. У турнірі існує шлях, який проходить через усі вершини орграфа.

Доведення:  Доведемо  це  твердження  індукцією за  кількістю вершин.  Для турнірів,  що мають одну  чи  дві вершини,  шлях,  який  проходить  через  усі  вершини  орграфа, існує. Нехай твердження виконується для всіх турнірів, що мають n (n ≥ 2) вершин. Розглянемо  довільний турнір G = ({v₀,  v₁,  v₂, …, v_n}, E)  з  n+1  вершиною. Орграф G-v₀  є n-вершинним турніром, тому  за припущенням індукції в ньому існує шлях, що проходить через усі його вершини. Без обмеження загальності можна вважати, що  це  шлях (v₁,  v₁, …, v_n).  Якщо  для деякого натурального  числа i, 1 ≤ i ≤ n-1, виконується (v_i, v₀), (v₀, v_i+1)∈E,  то (v₁, …,  v_i-1,  v_i,  v₀,  v_i+1,  v_i+2, …, v_n) — шлях  у G. Інакше,  оскільки  G  є турніром,  виконується або (v₀, v₁)∈E,  або (v1, v₀)∈E.  У першому випадку маршрут (v₀, v₁, v₂, …, v_n) є шуканим шляхом. У другому випадку виконано (v₂, v₀)∈E, (v₃, v₀)∈E, …, (v_n, v₀)∈E,  але тоді маршрут (v₁,  v₂, …,  v_n, v₀)  є шляхом  в орграфі G.  Згідно  з принципом математичної  індукції  твердження доведено.

Доведено 

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

 

Розфарбуванням  графа  називається таке приписування кольорів його вершинам, що ніякі дві суміжні  вершини не отримують однакового кольору. Множина всіх вершин одного кольору є незалежною одноколірним класом. В n-розфарбуванні графа G використовується n кольорів, і, таким чином, це розфарбування розбиває V на n одноколірних класів.

2.2.1. Хроматичне  число графа

 

Нехай  N_k = {1, 2, …,  k}.  Відображення  f : V→N_k  називається розфарбуванням графа  G = (V, E);  для кожної  v∈V  число f(v)  називається  кольором (фарбою  або номером  фарби).  Розфарбування f графа G  називається правильним,  якщо (v, w)∈E ⇒ f(v) ≠ f(w), тобто довільні дві суміжні вершини мають різні кольори.

Мінімальна  кількість  фарб,  для  якої  існує  правильне  розфарбування  графа  G, називається (вершинним)  хроматичним  числом  графа  G  й позначається  χ(G). Відповідне  розфарбування називається мінімальним.  До  побудови  правильного розфарбування та хроматичного числа можуть бути зведені такі практичні задачі, як задача складання розкладу, задача розподілу устаткування, задача проектування трансмісії та деякі інші.

Хроматичне  число  порожнього  графа  дорівнює 1.  Якщо  граф  має  хоча  б  одне ребро, його хроматичне число не менше 2. Очевидно, що для  довільного підграфа H графа G справджується нерівність χ(H) ≤ χ(G).

Теорема 2.7.  Хроматичне  число графа дорівнює  найбільшому з хроматичних чисел його зв’язних компонент.

Доведення:  Якщо для розфарбування кожної  зв’язної компоненти достатньо k фарб, то й для розфарбування всіх зв’язних компонент достатньо k фарб [36, c.152].

Доведено 

Теорема 2.8.  Якщо  в графі G вершина v  має степінь k  і граф  G-v  можна правильно розфарбувати  в k' > k  кольорів,  то  граф  G  можна правильно розфарбувати в k' кольорів.

 Доведення:  нехай вершини графа G-v  можна правильно розфарбувати  в k' кольорів. Вершина v має k суміжних вершин, тому серед k' кольорів є хоча б один, у який не пофарбовано вершини,  суміжні з v.  Пофарбуємо  її  в цей колір і одержимо правильне розфарбування всього графа в k' фарб [31, c. 78-79]. 

Доведено

Висновок 2.8.1.  Якщо  в графі G  вершина v  має степінь k  і          χ(G-v) > k,  то χ(G) = χ(G-v).

Доведення:  За теоремою χ(G) ≤ χ(G-v). Але G-v⊆G, тому                  χ(G-v) ≤ χ(G), і χ(G) = χ(G-v). 

Доведено 

Висновок 2.8.2. Якщо ∆(G) — найбільший зі степенів вершин графа G, то χ(G) ≤ 1+∆(G).

 Доведення:   Застосуємо  індукцію  за  кількістю вершин.  Якщо  граф  має одну  чи  дві вершини,  твердження  очевидне. Нехай для всіх  графів,  кількість вершин  у яких дорівнює n (n≥1), твердження справджується. Розглянемо граф G з n+1 вершиною й вилучимо  з нього довільну  вершину v.  Одержимо  граф  G-v,  у якому ∆(G-v) ≤ ∆(G).  Згідно  з припущенням індукції  для його  розфарбування достатньо 1+∆(G) фарб. Оскільки         δ(v) ≤ ∆(G) < 1+∆(G), за теоремою граф G можна правильно розфарбувати  не  більш як 1+∆(G) фарбами.  За  принципом математичної  індукції твердження доведено [32, c.155]. 

Доведено

2.2.2.  Гіпотеза  чотирьох фарб та теорема про  п’ять фарб для

планарних графів

 

Гіпотеза  чотирьох  фарб  пов’язана  з  розфарбуванням  політичних  географічних карт. Вважається, що територія кожної країни є зв’язною областю, а суміжні країни мають  спільну межу у вигляді лінії (а не однієї спільної точки). Території  суміжних країн фарбуються в різні  кольори. Гіпотеза полягає в тому, що для будь-якої карти достатньо  чотирьох фарб.

Ця гіпотеза має еквівалентне формулювання в термінах графів. Областям карти відповідають вершини графа, їх межам — ребра. Очевидно, що цей  граф плоский. Таким  чином,  гіпотеза  чотирьох  фарб  полягає  в  існуванні  правильного розфарбування  вершин  довільного  планарного  графа  не  більш ніж у чотири кольори [28, c. 146].

Ця  гіпотеза (для  карт)  з’явилася  ще  в  середині 19-го  століття.  Її  непрямо підтверджує  час (більше  століття),  протягом  якого  численні  спроби  побудувати контрприклади  залишалися  марними.  Гіпотезу  чотирьох  фарб  доведено  для окремих класів графів, наприклад, для графів, що мають не більше 41 вершини. В 1969  році  Х. Хеєш  звів  проблему  чотирьох  фарб  до  дослідження  великої,  але скінченної множини графів. Пізніше кількість графів цієї множини було зведено до 1482  і  вже  в 1976 році  колективу  математиків  і  программістів  під  керівництвом К. Аппеля  і В. Хейкена  за  допомогою ЕОМ  вдалося  розфарбувати  всі  ці  графи. У  1996  році  Н. Робертсон,  Д. Сендерс,  П. Сеймур,  Р. Томас  запропонували  нове, простіше  доведення  гіпотези  чотирьох  фарб,  але  знову  з  використанням комп’ютера.  Проте  з  повною  мірою  математичної  строгості  її  не  доведено, оскільки,  наприклад,  не  доведено  коректність  компілятора  та  коректність виконання  побудованого  програмного  коду,  за  допомогою  якого  будувалося розфарбування,  крім  того,  і  зведення  загального  випадку  до  перебору  скінченної множини графів, і розфарбування останніх складно повторити [4, c.60-61].

Обмежимося більш слабким  результатом (його одержав Хейвуд у 1890-му році).

Теорема 2.9. (про 5  фарб).  Для правильного розфарбування довільного планарного графа достатньо п’яти фарб.

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

Припущення  індукції:  всі  плоскі  графи  з  n (n ≥ 5)  вершинами можна розфарбувати у 5 фарб. Нехай G = (V, E) – плоский граф з n+1 вершиною. У будь-якому планарному графі існує вершина v степеня не більше 5. Граф G-v має n  вершин,  тому  його  можна правильно розфарбувати  фарбами 1, 2, 3, 4, 5. Нехай це розфарбування задається функцією f : V\{v} → {1, 2, 3, 4, 5}. Якщо деякий колір i (від 1 до 5) не  застосовується для вершин, суміжних  із v, візьмемо  f(v) = i, що залишить розфарбування графа правильним.

Нехай  δ(v) = 5  і вершини v₁,  v₂,  v₃,  v₄,  v₅,  суміжні з v,  пофарбовано в усі 5 кольорів, тобто f(v_і) = i (i = 1, 2, 3, 4, 5). Нехай вершини розташовано на площині так, як указано на рис.2.7.

Рис.2.7.

Нехай  V_і = {x |  x∈V\{v}  ∧  f(x) = i} – множина вершин,  пофарбованих  i-ю фарбою.  Розглянемо  G₁₃= G(V₁∪V₃) – підграф графа G,  визначений  множиною вершин V₁∪V₃.

Якщо  вершини  v₁  і v₃  належать  різним  компонентам зв’язності  графа G₁₃,  то  в компоненті,  яка містить v₃,  міняємо місцями кольори 1  і 3.  Отримаємо нову функцію f₁  правильного розфарбування,  для якої  f₁(v₁) = f₁(v₃) = 1,  f₁(v_і) = i,  i = 2, 4, 5. Покладемо f₁(v) = 3  і одержимо правильне розфарбування f₁ всього  графа у 5 фарб.

Якщо  вершини  v₁  і v₁  зв’язані  в G₁₃,  то  простий ланцюг,  що  їх  з’єднує, складається лише з вершин кольорів 1 і 3. Цей ланцюг разом з ланцюгом (v₁, v, v₃) дає простий цикл, що  обов’язково оточує  одну  з вершин  v₂  чи  v₄. В такому  разі вершини v₂ і v₄ не можна з’єднати простим ланцюгом, що містить тільки вершини кольорів 2  і 4.  Тоді  в графі             G₂₄ =  G(V₂∪V₄)  вершини v₂  і v₄  належать  різним компонентам зв’язності.  Тоді  в компоненті  графа G₂₄,  що  містить вершину v₄, міняємо місцями кольори 2  і 4,  утворюючи нову  функцію f₁  правильного фарбування,  для якої  f₁(v₂) =  f₁(v₄) = 2,  f₁(v_і) = i,  i = 1, 3, 5.  Покладемо f₁(v) = 4  і одержимо  правильне розфарбування f₁  всього  графа у 5  фарб.  За  принципом індукції твердження доведено [36, c.155-156].

Доведено   

РОЗДІЛ 3. ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ В ОКРЕМИХ ГАЛУЗЯХ НАУКИ

 

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

3.1. Фізика

 

В 1847 р. Кірхгоф розробив теорію дерев для розв’язання  сукупної системи лінійних алгебраїчних рівнянь, яка б давала змогу знайти значення сили струму в кожному провіднику (дузі) і в кожному контурі електричного ланцюга, що розглядається. Будучи фізиком  за освітою, він підходив до розв’язання  задачі як математик. Абстрагуючись  від електричних схем і ланцюгів, які містять опір, конденсатори, індуктивність і т.д., він розглядав  відповідні комбінаторні структури, які  містять тільки вершини і зв’язки (ребра і дуги), причому для  зв’язків не потрібно вказувати , яким типами електричних елементів вони відповідають. Таким чином, в дійсності  Кірхгоф замінив кожен електричний  ланцюг відповідним йому графом і  показав, що для розв’язання системи  рівнянь  не обов’язково розглядати окремо кожен цикл графа електричного ланцюга. Замість цього він запропонував просту, але ефективну методику (яка  пізніше стала стандартною процедурою), в відповідності з якою достатньо  обмежитися тільки незалежними простими циклами графа, визначеними будь-якими  з його «остовних дерев». На рис.3.1. показаний приклад електричного ланцюга N, відповідного йому графа G і остовного дерева Т [36, c.14].

Рис.3.1.

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

Кожен вузол характеризується так званим вузловим сигналом (х, у тощо), а вітки – передачею (а, в, с тощо).

Вітку можна побудувати, якщо її передача відрізняється від  нуля. Інакше відповідний вузол буде ізольованим. Розглянемо деякі еквівалентні перетворення графів.

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

Рис.3.2.

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