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

(2)⇒(3) Достатньо довести ациклічність. Припустимо супротивне: зв’язний граф з n-1 ребрами має цикл. Тоді будь-яке ребро, що входить до складу цього циклу, можна  вилучити  і  за  теоремою 1.25  одержати  зв’язний  граф.  У цьому графі залишиться n-2 ребра, а це неможливо за теоремою  (зв’язний n-вершинний граф повинен мати принаймні n-1 ребро). Суперечність.

(3)⇒(1) Достатньо довести зв’язність графа. Припустимо супротивне: нехай він має k  компонент зв’язності  з кількостями вершин  n₁,  n₂, …, n_k;  n₁+n₂+ … +n_k = n. Граф  ациклічний,  тому  кожна його  компонента  зв’язності  є деревом,  і за переходом (1)⇒(2)  i-а компонента має n_i-1 ребро. Тоді  граф має (n₁-1)+(n₂-1)+ …+(n_i-1) = n-k ребер. За умовою кількість ребер дорівнює n-1, тому k = 1, тобто граф зв’язний [19, c. 89-90].

Доведено 

Щоб  отримати  кістякове  дерево  зв’язного  графа  G = (V, E),  можна послідовно вилучати з нього ребра, що входять до складу хоча б одного циклу. За теоремою 1.24 кожного разу одержується зв’язний граф. Граф скінченний, тому на деякому кроці залишиться  ациклічний  зв’язний  граф,  який  буде  кістяковим  деревом графа. При цьому ми  вилучимо |E|-|V|+1  ребер.  Зауважимо,  що  ребро зв’язного графа, інцидентне  кінцевій  вершині,  входить в усі зв’язні суграфи графа,  оскільки вилучення такого ребра робить відповідну вершину ізольованою.

Для побудови кістякового  ліса для незв’язного графа слід побудувати кістякове дерево  для  кожної  його  компоненти  зв’язності. Ця  операція  потребує  вилучення |E|-|V|+k ребер, де k — кількість компонент зв’язності графа. З наведеного алгоритму випливає наступне твердження.

Теорема 1.25. Зв’язний граф має кістякове дерево.

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

Отже, справджується наступна теорема.

Теорема 1.26. Граф G є лісом тоді й тільки тоді, коли ν(G) = 0.

Теорема 1.27.  Дерево з n вершинами має n-1 ребер.

Доведення: замість одного дерева розглянемо ліс, який складається з k зв’язних компонент, кожна з яких є деревом (див.рис.1.32). Для кожної з компонент число ребер на одиницю менше числа вершин.

Отже, твердження вірне.

Теорема 1.28. Ліс, який складається з k компонент і має n вершин, містить n – k ребер.

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

Рис.1.38.

Пошта всередині країни може бути позначена через А₁, пошта в Європу – через А₂, пошта на Далекий Схід – через А₃ і т.д. Місцева пошта А₁ ділиться на східну, західну, центральну, пошта в Європу А₂ ділиться по країнах і т.д.

 

РОЗДІЛ 2. ОРІЄНТОВАНІ ГРАФИ ТА РОЗФАРБУВАННЯ ГРАФІВ

 

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

 

2.1. Орієнтовані  графи

 

Ребро може мати напрям від  однієї вершини до іншої; в цьому  випадку  воно називається направленим, або орієнтованим, або дугою і  зображуться стрілкою, направленою  від вершини, яка зветься початком, до вершини, яка  зветься кінцем.  Граф, що містить направлені ребра (дуги) з початком  v′  і  кінцем v′′,  називається  орієнтованим  графом  (орграфом),  граф,  що містить ненаправлені ребра – неорієнтованим графом (н – графом).

2.1.1. Модель орграфа

Для  повноти  викладення  почнемо  з  означень,  які  вже  були  наведені  раніше. Нехай  V —  непорожня  скінченна  множина,  а E — довільна  підмножина  другого декартового степеня множини вершин,  тобто E ⊆V × V.  Пара (V, E)  називається орієнтованим  графом,  чи  орграфом,  елементи  множини V — вершинами,  або вузлами, а елементи множини E — орієнтованими ребрами, або дугами. Дуги (v, w) і (w, v) орграфа називаються симетричними. Орграф, що не має пар симетричних дуг,  називається направленим.  Кожну пару  симетричних дуг між різними вершинами v  та  w  можна розглядати  як  одне  неорієнтоване ребро {v, w}.  Дуга вигляду (v, v)  називається петлею. Надалі  під орграфом  будемо  розуміти  орграф без петель.  Таким чином,  за  означенням  в орієнтованому графі немає петель  та кратних дуг [12, c.53-54].

Розглянемо   тепер  задачу про  турнір  між  чотирма  футбольними командами, в якому  кожні дві команди зіграли  між собою не більше одного матчу.  Цей турнір можна подати орграфом, вершинами якого  є команди. Якщо дві команди зіграли між собою  матч, з’єднаємо відповідні вершини  дугою ребром, що веде від команди-переможця  до команди, що програла. Якщо дві команди  зіграли у  нічию,  проведемо  дві  симетричні  дуги.  Так  в  футбольному  турнірі, представленому в графі з рис. 2.1, команди "Динамо" та "Шахтар" зіграли у нічию, а "Динамо" виграло у "Спартака".

Рис.2.1.

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

Нехай  G = (V, E) – орграф,  e∈E  - дуга.  Кажуть,  що  дуга  e = (v, w)  веде  з вершини v у вершину w, а вершини v  і w є кінцевими вершинами дуги (v, w). При цьому вершину v називають початком дуги (v, w), w – кінцем , v – суміжною до w, а w — суміжна із v. Кожна дуга інцидентна своїм кінцевим вершинам. Дві різні дуги, інцидентні одній і тій самій вершині, називаються суміжними.

Півстепенем виходу δ⁺ (v) вершини v називається кількість вершин, суміжних  із v,  тобто,  кількість ребер,  що  виходять  з вершини v;  півстепенем  входу  δ^- (v) – суміжних   до  v,  тобто кількість ребер,  які входять у v.  Степенем  вершини  v називається кількість дуг,  інцидентних v,  і позначається  δ(v).  Оскільки розглядаються орграфи без петель, з цих означень випливає наступне твердження [14, c.17].

Теорема 2.1.  Для будь-якої  вершини v  орграфа справджується рівність  δ(v) = δ⁺ (v) + δ^- (v).

В орграфі з n вершинами півстепінь вершини може мати значення від 0 до n-1, а степінь — від 0 до 2(n-1).

Нехай  є  орграф G = (V, E),  де  V = {1, 2, 3, 4, 5, 6, 7},  E = {(1, 2),      (1, 3), (3, 4), (2, 4), (2, 7), (3, 7), (4, 6), (5, 6), (6, 7), (7, 5)}. Його діаграму подано на рис. 2.2.

.

Рис.2.2.

Для цього графа вершина 2 є суміжною із вершиною 1 та суміжною до вершини 4. Обчислимо півстепені  та  степені вершин: δ⁺(1) = 2, δ^-(1) = 0,  δ⁺(2) = 2, δ^-(2) = 1, δ⁺(3) = 2,  δ^-(3) = 1,  δ⁺(4) = 1,  δ^-(4) = 2,  δ⁺(5) = 1,  δ^-(5) = 1,  δ⁺(6) = 1,  δ^-(6) = 2, δ⁺(7) = 1, δ^-(7) = 3;  δ(1) = 2,  δ(2) = 3,  δ(3) = 3,  δ(4) = 3, δ(5) = 2,  δ(6) = 3,  δ(7) = 4.

Орграфом,  оберненим  до  даного  орграфа G = (V, E),  називається орграф  G′ =(V, E′), де E′ = {(w, v) | (v, w)∈E}.  Іншими словами, орграф, обернений до орграфа G,  одержується зміною  орієнтації  кожної  дуги  орграфа на  протилежну (рис.2.2). Для довільного орграфа G справджується очевидна рівність G′′ = G, тобто орграф, обернений до оберненого, збігається з початковим орграфом.

Рис.2.3.

Нам  уже  знайомі  такі “обернені”  поняття,  як  півстепінь  виходу  та  пів степінь входу. Відносно  орієнтації  всі  поняття  пов’язані між  собою  достатньо  потужним принципом.

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

У довільному орграфі кожна  дуга має рівно один початок та рівно один кінець, тому справджується  наступне твердження.

Теорема 2.2. Для довільного орграфа G = (V, E) виконується                  ∑ δ⁺(v) = ∑ δ^-(v) = |E|.

Ця теорема є аналогом “леми про рукостискання” для  неорієнтованих графів;  її інколи називають  “орлемою про рукоcтискання”.

2.1.2. Маршрути в  орграфах

 

Для  орграфів  маршрут  означається  аналогічно  неорієнтованим  графам.  В орграфі G = (V, E)  послідовність вершин  і дуг (v₀,  e₁,  v₁, …,  v_n-1,  e_n, v_n),  де  v₀, …,v_n - вершини,  e_i = (v_i-1, v_i), 1 ≤ i ≤ n, - дуги,  називається (орієнтованим) маршрутом.  Дуги  e_i та  e_i+1 (1 ≤ i ≤ n-1) є сусідніми дугами  маршруту  й  мають принаймні одну спільну вершину. Вказаний маршрут веде  з v₀ у v_n. Цей маршрут можна позначити (v₀,  v₁, …,  v_n-1, v_n), не  вказуючи його  дуги. Число n називається довжиною маршруту. Для систематичності міркувань вводиться тривіальний, або нуль-маршрут - маршрут,  що  складається з єдиної  вершини й має довжину 0. Інші маршрути вважаються нетривіальними [2, c.156-157].

Маршрут називається  ланцюгом,  якщо  всі його ребра попарно  різні,  і простим ланцюгом, або  шляхом, якщо всі його вершини попарно  різні.

Якщо v₀ = v_n, то маршрут називається замкненим, або циклічним. Для замкненого маршруту його остання та перша дуги вважаються сусідніми. Кістяковий маршрут містить всі вершини орграфа.  Нетривіальний замкнений ланцюг  називається циклом. Цикл (v₀,  v₁, …,  v_n-1, v_n)  називається простим,  або контуром,  якщо  його вершини v₁, …,  v_n-1, v_n  попарно різні.  Зауважимо,  що  тривіальний маршрут є замкненим за  означенням.  На  відміну від неорієнтованих  графів,  найменша можлива довжина контура дорівнює двом, наприклад, в орграфі   G = ({1, 2}, {(1, 2), (2, 1)})  існує контур (1, 2, 1)  довжини 2.  Цикл,  що  містить усі дуги  орграфа, називається ейлеровим. Ланцюг, що містить усі дуги  орграфа,  також називається ейлеревим [6, c.85].

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

Кожен  маршрут  є  орієнтованим  від  своєї  першої  вершини  до  останньої.  Для орграфів  вводиться  також  поняття  півмаршруту,  який  не  має  орієнтації  й  є аналогічним  маршруту  в  графі.  Півмаршрутом в орграфі називається послідовність вершин  і дуг (v₀,  e₁,  v₁, …,  v_n-1,  e_n, v_n), де  v₀, …,  v_n – вершини,  але дугою e_i , 1 ≤ i ≤ n, може бути як (v_i-1, v_i), так і (v_i, v_i-1). Півшлях, півконтур та  інші поняття означаються аналогічно.

У  графі  на  рис.2.3.  існує контур (5, 6, 7, 5),  який  одночасно є півконтуром,  та півмаршрут (6, 7, 3), який не є маршрутом. Також у цьому графі існують шляхи (1, 3, 4, 6, 7) та (1, 2, 7), що ведуть з вершини 1 в вершину 7.

Як  і  для  неорієнтованих  графів,  якщо  Z₁ = (v₀, v₁, …,  v_і-1, v_і)  і Z₂ = (vi,  vi+1, …, vn) – маршрути (півмаршрути), то під Z₁·Z₂ розуміється маршрут (півмаршрут) (v₀, v₁, …, v_і-1, v_і, v_і+1, …, v_n) , а під Z₁^-1 - півмаршрут (v_і, v_і-1, …, v₁, v₀).

Вершина,  з  якої  недосяжна  жодна  інша  вершина  орграфа,  називається тупиковою. Згідно з означенням, з тупикової вершини не виходить жодного ребра, тому має місце наступна теорема [19, c.45-47].

Теорема 2.3. Вершина орграфа є тупиковою тоді  й тільки  тоді,  коли  вона  має нульовий півстепінь виходу.

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

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

У графі на рис. 2.2 вершина 1 є недосяжною, а на рис. 2.3 вершина 1 є тупиковою.

Існують  типи  вершин,  протилежні  до  тупикових  та  недосяжних.  Джерелом  в орграфі називають вершину,  з якої  досяжна будь-яка вершина орграфа.  Стік визначається двоїстим чином: стоком у орграфі називають вершину, яка досяжна з будь-якої вершини орграфа. Наприклад, у графі на рис. 2.2 вершина 1 є джерелом, а вершини 5, 6, 7 — стоками.

Поняття  зв’язності  для  орграфів  означається  у  три  різних  способи.  Орграф називається  сильно  зв’язним,  або сильним,  якщо  дві довільні  його  вершини є взаємно досяжними; однобічно зв’язним, або однобічним, якщо для довільних двох його  вершин  принаймні одна  є досяжною  з іншої;  слабо  зв’язним,  або слабким, якщо  довільні  дві його  вершини можна з’єднати  півмаршрутом.  Зрозуміло,  що кожен сильний орграф  є  однобічним,  а  однобічний —  слабким,  але  зворотні твердження  в  загальному  випадку  хибні.  Наприклад,  орграф  на  рис. 2.4, а  є сильним, на рис. 2.4, б є однобічно, але не сильно зв’язним; приклад слабкого, але не  однобічного орграфа наведено  на  рис. 2.4, в.  Орграф  на  рис. 34  також є прикладом слабкого, але не однобічного орграфа.

Рис.2.4.

Орграф  називається  незв’язним,  якщо  він не  є слабо зв’язним.  У незв’язному орграфі не має ні стоків, ні джерел.