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

Теорема 1.7. Кожний граф  G = (V,E) укладається в тривимірний евклідів простір E³.

   Доведення: Вершини  графа  розміщуємо  в  різних  точках  осі  Ox.  З  в’язки  площин,  що проходять  через  Ox,  виберемо  |E|  різних.  Кожне ребро   (v, w)∈E  відображаємо  у відповідній площині півколом, що проходить через вершини v та w. В результаті одержимо укладання графа G в E³ , оскільки всі ребра лежать в різних площинах і не перетинаються у внутрішніх точках [1, c.102]. 

Доведено

Планарним називається граф, який можна укласти на площині, плоским — граф, який  вже укладено  на  площині.  Таким чином,  планарним називається граф, ізоморфний деякому плоскому графу.

Гранню плоского графа називається максимальна за включенням множина точок площини, кожну пару яких можна з’єднати неперервною лінією без само перетинів і перетинів ребер графа в точках, відмінних від її кінців. Кожний плоский граф має рівно одну необмежену грань, яка називається зовнішньою; інші грані називаються внутрішніми.  Межею  грані  будемо  вважати множину ребер,  що  належать  грані. Множину всіх граней плоского графа позначатимемо через P.

Плоскою  картою  називається  зв’язний  плоский  граф  разом  з  усіма  своїми гранями.

Приклади планарних графів та їх плоских карт наведено на рис. 1.20.

Рис.1.20.

Теорема 1.8. Граф є планарним тоді й тільки тоді, коли він укладається на сфері.

  Доведення: (⇒) Граф скінченний, тому його можна вмістити в круг C скінченного радіуса R  з центром у деякій  точці O₁   (на  межі  круга точок графа немає).  Проведемо з центра O₁  скінченний перпендикуляр О₁О₂ до площини. Нехай точка O — середина відрізка О₁О₂. Побудуємо сферу S з центром у точці O та радіусом r = |OO₁|, якадотикається  площини у точці  

(|О₁Х|   <   R)  побудуємо площину P_х,  що  проходить через О₁О₂   та  X.  Точці X поставимо у відповідність точку Y сфери, Y∈P X∩S, для якої               l / (πr) = |О₁Х| / R, де l — довжина криволінійного відрізка сфери О₁Y. Позначимо цю відповідність через φ. За  означенням, ϕ  є взаємно-  однозначним відображенням множини внутрішніх точок круга C на множину точок сфери S\{O₂}. Тоді, якщо граф був плоским, його образ на сфері є сферичним укладанням.

(⇐) Нехай граф укладено на сфері S. Візьмемо довільну сферичну грань графа та оберемо на  ній довільну  точку O₂,  що  не  належить  графу.  З обраної точки побудуємо діаметр сфери О₁О₂ та  в  точці  O₁   проведемо площину,  дотичну до сфери. Побудуємо на ній круг C з центром у точці дотику O₁   та радіусом R (R   >   0). Зворотне  відображення  φ^-1   множини точок сфери S\{O₂}  на  внутрішню  частину круга  C  також є взаємно однозначним і переводить  сферичне  укладання графа в плоске  укладання,  причому грань,  яка містить точку O₂,  відображається  в зовнішню грань графа. 

Доведено

Висновок  1.8.1.  Для довільного  ребра (довільної вершини)  планарного  графа знайдеться  така  укладка графа на  площині,  що  це  ребро (ця  вершина)  належить зовнішній грані.

   У  доведенні   теореми  при  побудові  відображення  сферичного  графа  на площину  в якості точки O₂  треба взяти внутрішню точку грані, яка містить вказане ребро чи вершину. 

Зауваження: При переході від плоского укладання до сферичного й навпаки в доведенні теореми 2 кількість граней залишається незмінною.

Неважко  бачити,  що  кожен  підграф  планарного  графа  є  планарним,  а  граф  є планарним  тоді й тільки тоді, коли планарна кожна  з його зв’язних компонент.

Теорема 1.9.  (Ейлера).  Якщо  G =  (V, E) — зв’язний  плоский граф,  то    |V|−|E|+|P| = 2.

Доведення:   Для довільного плоского графа побудуємо його кістякове дерево (V, E₀), для якого формула справджується.  Це  кістякове дерево  є плоским графом  з однією гранню, тобто |P₀| = 1. Тоді для нього |E₀| = |V|−1, звідки |V|−|E₀|+|P₀| = 2. Далі  будемо  послідовно  додавати  ребра графа,  що  не  увійшли до  кістякового дерева.  Нехай на  деякому кроці утворено  граф  (V, E_k)  (k =  0,  1,  …,  ν(G)-1),  для якого |V|−|E_k|+|P_k| = 2. При додаванні ребра e кількість ребер збільшується на 1, але при цьому деяка грань розділяється на дві частини, тобто кількість граней також збільшується  на  1.  При цьому утворюється граф  (V, E_k+1),  де  E_k+1 = E_k∪{e}  і             |P_k+1| = |P _k|+1. Для нього |V|−|E_k+1|+|P_k+1| = |V|−(|E_k|+1)+(|P_k|+1) = |V|−|E_k|+|P_k| = 2.  При додаванні останнього  ребра утворюється граф  (V, E_v(G)) =  (V, E),  для якого |V|−|E|+|P| = 2 [8, c.179]. 

Доведено

Висновок 1.9.1. Якщо G = (V, E) — плоский граф з k зв’язними компонентами, то |V|−|E|+|P| = k+1.

Висновок 1.9.2. Кількість граней будь-якої плоскої карти для планарного графа G =  (V, E)  є величиною сталою  й дорівнює  |E|-|V|+k+1,  де k — кількість зв’язних компонент графа G.

Зауваження: Різні плоскі карти одного й того самого планарного графа можуть мати грані з різними наборами степенів. Приклад наведено на рис. 1.21.

Рис.1.21.

Висновок  1.9.3.  Якщо  граф  має n  вершин,  m  ребер (m ≥ 2),  k  компонент зв’язності й є планарним, то m ≤ 3n−3k-3 ≤ 3n-6.

Висновок 1.9.4. Граф K₅  не є планарним.

  Доведення: K₅  має 5 вершин і 10 ребер. Оскільки 10 > 3⋅5-6 = 9, то планарним він бути не може.

1.4.1. Застосування  теореми Ейлера до деяких завдань

 

Переформулюємо теорему  Ейлера в дещо простішому для розуміння  стилі.

Теорема Ейлера: нехай на площині задано  m точок і n попарно непересічних дуг, кожна з яких попарно з’єднує які-небудь дві дані точки і не проходить через інші m – 2 точки, і нехай ці дуги ділять площину на l областей. Якщо з кожної даної точки можна потрапити в будь-яку іншу точку, рухаючись по цих дугах, то

m – n + l = 2

У випадку, зображеному на рис.1, всі умови теореми Ейлера виконані, m = 12, n = 18, l = 8 і m – n + l = 2.

Рис.1.22.

На рис.1.23(а,б) зображені випадки, коли умови теореми Ейлера не виконуються. Так, на рис.1.23(а) з точки А₁  не можна потрапити в точку А₅ і     m – n + l =3 ≠ 2, а на рис.1.23(б) лінія, що з’єднує точки А₁ і А₂, є самоперетинаючою і знову m – n + l =3 ≠ 2. [1, c.104].

а) б)

Рис.1.23.

Тепер можемо перейти до розв’язання задач.

Задача 1.4. Чи можна десять міст з′єднати між собою неперетинаючими дорогами так, щоб з кожного міста виходило п’ять доріг, які ведуть в п’ять інших міст?

Розв’язання:

Припустимо, що міста можна  з’єднувати між собою дорогами так, як вказано в задачі. В такому випадку, якщо які-небудь два міста  опиняться не з’єднаними дорогою  безпосередньо, то знайдеться третє  місто, яке уже буде безпосередньо  з’єднане з кожним з них. Зобразивши на площині міста точками, а дороги – дугами, отримаємо, що будь-які  дві точки з’єднані ланцюгом дуг. Так як в кожній точці сходиться п’ять дуг, то загальне число дуг рівне 5*10:2=25. За теоремою Ейлера, ці дуги ділять площину на       2+25-10=17 областей. Кожна з цих сімнадцяти областей обмежена принаймні трьома дугами, так як в протилежному випадку знайшлись би два міста, безпосередньо з’єднані принаймні  двома дорогами, а це суперечить умові задачі. Отже, число дуг не менше  3*17:2=25,5. Таким чином, вихідне припущення приводить нас до протиріччя, і міста не можна зєднати між собою так, як це вимагається в умові задачі [5, c.17].

Задача 1.5. Чи можна семикутник розрізати на випуклі шестикутники?

Розв’язання: припустимо, що деякий семикутник вдалося розрізати на випуклі шестикутники. Позначимо число тих вершин шестикутників, які лежать всередині  вихідного семикутника, через m, а число вершин, що лишились (тобто лежачих на межі семикутника) – через m^′. В якості дуг, які з’єднують вершини, оберемо прямолінійні відрізки сторін многокутників, які задовольняють наступним умовам: відрізок повинен з’єднувати дві вершини і не проходити через інші вершини. Позначимо через n число таких дуг і через l – число областей, на які ці дуги ділять площину (число l на одиницю більше числа шестикутників). Зрозуміло, що будь-які дві вершини виявляться з’єднаними ланцюгом дуг. За теоремою Ейлера

m + m^′ - n + l = 2.           (*)

Так як зовнішня область  обмежена m^′ дугами, а кожна з інших – не менше, ніж шести дугами, то

2*n ≥ 6*(l – 1) + m^′.      (**)

З деяких вершин на межі семикутника  виходять тільки дві дуги. Позначимо  число таких вершин через а. з будь-якої іншої вершини виходять принаймні три дуги, так, що

3*m + 3*( m^′ - a) + 2*a ≤ 2*n.

Звідси, в силу рівності (*), маємо

n ≤ 3*l + a – 6 .

Прирівнявши цю нерівність і нерівність (*), ми отримуємо 

2*a - m^′ ≥ 6.                 (***)

Так як на межі семикутника  знайдуться принаймні дві вершини, з яких виходять дуги, що ведуть в  середину семикутника, то m^′ - a ≥ 2. З цієї нерівності і нерівності (***) слідує, що а ≥ 8.

З іншого боку, так як семикутник розрізаний на випуклі многокутники, то будь-яка вершина, з якої виходять дві дуги, є вершиною семикутника, і тому а ≤ 7. Таким чином, семикутник не можливо розрізати на випуклі шестикутники [5, c. 19].

1.4.2. Критерії планарності

 

У  цьому  підрозділі  розглядаються  дві  необхідні  й  достатні  умови  планарності  графів. У цих умовах використовуються непланарні графи K_3,3  і K₅ , а також одна з двох додаткових операцій з графами — підрозбиття ребра та стягування вершин.

Почнемо з підрозбиття. Нехай  граф G = (V, E) має ребро e ∈ E, e =    (v, w). Операція підрозбиття ребра e полягає в тому, що з графа вилучається ребро e, до множини вершин додається нова вершина u, а до множини ребер — нові ребра (v, u) і (u, w). Таким чином, утворюється граф G' = (V∪{u}, (E\{(v, w)})  ∪ {(v, u), (w, u)}). Степені всіх вершин з множини V у графі G' залишаються такими самими, як і в G, а додана вершина має степінь 2.  Відмітимо,  що  це  перетворення  зберігає  різницю між кількостями ребер та вершин графа.

Графи називаються гомеоморфними, якщо їх можна одержати з одного й того ж графа за допомогою підрозбиття його ребер. Наприклад,  граф  Петерсена  (рис.1.24,  а)  не  містить підграфа,  гомеоморфного графу K₅,  оскільки  число вершин  степеня,  не  рівного 2,  в гомеоморфних  графах однакове,  а граф  Петерсена на  відміну від графа K₅   не  містить жодної  вершини степеня 4.

Рис. 1.24.

У той же час, якщо з графа  Петерсена вилучити, наприклад, ребра DE і FH, то залишиться  граф,  гомеоморфний  непланарному  графу K_3,3   (на  рис.1.24, б  трійки вершин  B,  I,  J  та  A,  C,  G  утворюють його  частки,  а D,  E,  F,  H  одержуються в результаті підрозбиття його ребер).

Теорема 1.10.  Операція  підрозбиття ребер графа зберігає  характер  планарності графа.

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

Доведено 

Висновок 1.10.1. Гомеоморфні графи мають однаковий характер планарності.

Висновок 1.10.2.  (достатня  умова непланарності).  Граф,  що  містить підграф, гомеоморфний K₅  або K_3,3, не є планарним.

   Доведення: Якщо  граф  планарний,  то  кожен  його  підграф  планарний.  Але  планарний підграф  не  може  бути  гомеоморфним  непланарному  графу,  а  графи  K₅   і K_3,3 непланарні. 

Доведено

За  цим  висновком  граф  Петерсена  непланарний,  оскільки  містить  підграф, гомеоморфний непланарному K_3,3 (див. рис.1.24.).

Очевидно, що всі графи  з 1, 2, 3 чи 4 вершинами планарні, а  серед графів з 5 вершинами  непланарний  лише  K₅.  Розглянувши графи з 6  вершинами, негомеоморфні K₅, неважко переконатися, що найменшим (за включенням множин ребер)  непланарним з них є K_3,3.  І взагалі,  аналіз  непланарних графів  з більшою кількістю вершин свідчить, що кожен з них містить підграф, гомеоморфний K₅ або K_3,3.  Іншими  словами,  існування підграфа,  гомеоморфного K₅   або K_3,3,  є необхідною  умовою  непланарності.  Отже,  ці  два графи є мінімальними  (за відношенням “є підграфом”) непланарними графами, причому інших мінімальних не існує.

Наведені неформальні  міркування приводять до наступного твердження.

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

Розглянемо операцію стягування вершин. Нехай граф G = (V, E) має ребро e ∈ E,  e = (v, w). Операція стягування суміжних вершин v і w полягає в тому, що з графа вилучаються вершини v і w, додається нова вершина u∉V і з’єднується ребрами з усіма вершинами, які були суміжні з вилученими. Таким чином, утворюється граф G' = ((V\{v, w})∪{u},      ((E\(O(v)∪O(w))  ∪ {(u, x) | (v, x)∈E ∨ (w, x)∈E}). Степені всіх вершин у графі G' з множини V, що не були суміжні хоча б з однією з вилучених вершин,  залишаються без змін,  а степені вершин,  що  були  суміжні з обом вилученими вершинами, зменшуються на 1 [1, c.104].