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

1.7. Маршрути та  зв’язність у графах

 

Маршрутом у графі 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_n.  Цей маршрут можна позначити (v₀,  v₁, …,  v_n-1, v_n),  не  вказуючи  ребер.  Число n називається довжиною  маршруту.  Для систематичності міркувань вводиться тривіальний,  або нуль-маршрут — маршрут, що  складається з єдиної  вершини й має довжину 0. Інші маршрути вважаються нетривіальними.

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

Якщо v₀ = v_n, то маршрут називається замкненим, або циклічним. Його останнє та перше ребро вважаються сусідніми. Нетривіальний замкнений ланцюг називається циклом. Цикл (v₀, v₁, …,  v_n-1, v_n)  називається простим,  якщо  його  вершини v₁, …, v_n-1, v_n  попарно різні.  Відмітимо, що  кожний  простий цикл  є циклом,  а довжина будь-якого нетривіального  замкненого  маршруту (v₀, v₁, …,  v_n-1, v_n),  де  v₀ = v_n,  з попарно різними ребрами не  менше 3,  оскільки  треба вийти з вершини та повернутися в неї,  але по  різних  ребрах.  Отже,  цикл  і простий цикл  повинні проходити принаймні через три вершини [32, c.171].

Зауважимо,  що  за  принципом  Діріхле  довжина  довільного  простого  циклу  в графі завжди не більше числа вершин n, а простого ланцюга — менше n. Якщо Z₁ = (v₀, v₁, …, v_i-1, v_i) і Z₂ = (v_i, v_i+1, …, v_n) — маршрути, то під Z₁·Z₂ будемо розуміти маршрут (v₀,  v₁, …, v_i-1,  v_i,  v_i+1, …, v_n),  а під Z₁^-1 — маршрут (v_i,  v_i-1, …,v₁, v₀).

Рис.1.35.

На  рис.1.35. маршрути (v₁,  v₅,  v₄, v₁), (v₂,  v₃,  v₅, v₂)  та (v₆,  v₈,  v₉,  v₇, v₆)  є простими циклами, (v₅, v₂, v₃, v₅, v₄, v₁, v₅) — циклом, але не простим, (v₁, v₅, v₆, v₇, v₈, v₉) – простим ланцюгом, (v₇,  v₆,  v₈,  v₇, v₉) – ланцюгом ,  але не простим,  а (v₈,  v₆,  v₇,  v₈, v₇, v₉) не є ланцюгом [36, c.26].

Через C_n позначається граф, утворений одним простим циклом з n вершин, P_n – простим ланцюгом з n вершин. Граф C₃ часто називається трикутником. Це цикл і простий цикл з найменшою кількістю вершин.

Граф, що не має циклів, називається ациклічним.

Граф,  довільні  дві  вершини  якого можуть  бути  з’єднані  деяким  маршрутом (є  зв’язаними), називається зв’язним. Інакше граф називається незв’язним.

Максимальний  за  відношенням  ⊆  зв’язний  підграф графа називається компонентою зв’язності (чи зв’язною компонентою). На рис.1.36. наведено приклад графа з двома компонентами зв’язності K₃ і K₂.

Рис.1.36.

Відношення  зв’язності  на  множині  вершин  графа  G = (V, E)  є еківалентністю; позначимо її R. vRw має місце тоді й тільки тоді, коли вершини v і w є зв’язаними в графі. За еквалентністю R побудуємо фактор-множину V/R = {V₁, V₂, …, V_n}, яка є розбиттям множини вершин. Неважко переконатися, що підграфи G(V_i), 1 ≤ i ≤ n, є компонентами  зв’язності  графа G (максимальними зв’язними підграфами),  а сам граф  можна подати  як  пряму суму  його  зв’язних  компонент G = ∑G(V_i). Отже, одержуємо наступну теорему.

Теорема 1.20.  Кожний  граф  можна однозначно  подати  як  пряму суму  зв’язних компонент.

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

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

Розглянемо деякі властивості  маршрутів.

Теорема 1.21.  Будь-який  маршрут,  що  веде  з вершини v  у вершину  w (v ≠ w), містить простий ланцюг, що веде з v в w.

Доведення: Нехай є маршрут Z = (v₀, e₁, v₁, …, e_n, v_n), де v₀ = v, v_n = w. Побудуємо за ним простий ланцюг, що  веде  з v у w. Якщо  всі вершини маршруту  Z  різні,  то  він є простим ланцюгом. Інакше, нехай v_i = v_j при деяких i та j, 0 ≤ i < j ≤ n. Вилучивши частину маршруту Z між v_i та v_j, одержимо маршрут (v₀, e₁, v₁, …, e_i, vi, e_j+1, v_j+1, …, e_n, v_n), довжина якого менше довжини Z. Умова v ≠ w гарантує, що  i ≠ 0 або j ≠ n, тому новий маршрут з’єднує v і w. Якщо він не є простим ланцюгом, то застосуємо до нього таке саме скорочення. Кількість вершин графа та початковий маршрут Z скінченні,  і на  кожному кроці зменшується довжина маршруту,  тому  на  деякому скінченному кроці буде  одержано  маршрут,  що  з’єднує вершини v та  w  і має попарно різні вершини, тобто є простим ланцюгом [34, c.57]. 

Доведено 

Висновок  1.21.1. Будь-який найкоротший маршрут, що веде з вершини v у вершину w (v ≠ w), є простим ланцюгом.

Висновок  1.21.2. Довільний цикл містить простий цикл.

Теорема 3. Нехай G′ — це  граф,  який  одержано після вилучення зі  зв’язного графа G = (V, E) деякого ребра e∈E. Тоді:

а) граф G′ зв’язний, якщо ребро e належить циклу в графі G;

б)  граф G′ незв’язний,  і має тільки дві компоненти  зв’язності, якщо ребро e не входить у жодний цикл у графі G.

Доведення:  а) Нехай ребро e належить циклу Z = (w₁, w₂, …, w_n), де w_n = w₁. Без обмеження загальності можна вважати,  що  e = (w₁, w₂). Через Z′  позначимо маршрут (w₂, …, w_n). Z є циклом, тому Z′ не містить ребра e й є маршрутом в графі G′.

Доведемо, що дві довільні різні вершини v  і w графа G′ зв’язані. Очевидно, що вони зв’язані в G. Можливі два випадки: маршрут від v до w у G містив ребро e або не містив. Якщо не містив, то маршрут від v до w у G′ збігається з маршрутом у G. Якщо маршрут у G містив e, то він мав вигляд  (v, …, w₁, w₂, …, w) чи (v, …, w₂, w₁, …, w).  Замінимо  в ньому ребро (w₁, w₂)  маршрутом (Z′)^-1 чи  Z′,  відповідно,  і одержимо маршрут у G′. Отже, довільні дві вершини графа G′ зв’язані,  тобто він зв’язний.

б) Припустимо, що ребро e = (v, w), v ≠ w, не належить жодному циклу графа G, але при його вилученні вершини v та w зв’язані між собою в графі G′ = G-e. Тоді в графі G′  існує маршрут M = (v,  v₂, …,  v_n, w).  Без обмеження загальності можна вважати, що M є простим ланцюгом, який не містить ребра e. Тоді в графі G існує маршрут M·(v, w), який не містить однакових ребер, а тому є циклом,  і до того ж містить ребро e.  Отримана  суперечність  доводить  хибність  припущення.  Отже, вершини v та w незв’язані в графі G′, тому G′ - незв′язний  граф.

Доведемо,  що  він  має  рівно  дві  компоненти  зв’язності.  Розглянемо  дві непорожні підмножини V₁ = {v}∪{x | існує маршрут з v в x, що не містить ребра e} та V₂ = {w}∪{x | існує маршрут з w в x, що не містить ребра e}. Доведемо, що вони утворюють розбиття  множини вершин  графа G.  Оскільки  вершини v та  w  є незв’язними в графі G′, то множини V₁ і V₂ не перетинаються.

Доведемо,  що  кожна  вершина  графа  належить  одній  з  множин  V₁  або V₂. Розглянемо довільну  вершину u  графа G,  відмінну  від v  та w. Оскільки  граф G  є зв’язним, у ньому є маршрут (v₀, e₁, v₁, e₂, v₂, …, e_n, v_n), де v₀ = u, v_n = v. Якщо він не містить e,  то  вершина u  належить  підмножині V₁. Нехай i, 1 ≤ i ≤ n,  є таким, що маршрут (v₀, e₁, v₁, e₂, v₂, …, e_i, v_i) не містить ребра e, і_ei+1 = e. Тоді v_i – це  v або w, тобто для вершини u існує маршрут, що не містить ребра e й веде в v або w. Звідси кожна вершина графа належить одній з множин V₁ та V₂, тобто V₁∪V₂ = V.

В графі G′ кожні дві вершини з V₁ зв’язані між собою, як і кожні дві вершини з V₂.  У G′  вершини  v  та  w  незв’язані,  тому  підграфи  G(V₁)  та  G(V₂)  є двома компонентами зв’язності графа G′, тобто G′ = G(V )∪G(V ) [24, c.137-138].

Доведено 

Теорема 1.22.   Нехай G – зв’язний граф,  що  має не  менше ніж три вершини.

Наступні твердження еквівалентні:

1. G – блок;

2)  довільні дві вершини  графа G належать деякому спільному простому циклу;

3)  довільна  вершина   і  довільне  ребро  графа  G  належать  деякому спільному простому циклу;

4)  довільні два ребра  графа G належать деякому спільному простому циклу;

5)  для довільних двох  вершин і довільного ребра  графа G існує простий ланцюг, що з’єднує ці вершини і містить дане ребро;

6)  для довільних трьох  різних вершин графа G існує простий ланцюг, що з’єднує дві з них і проходить через третю;

7)  для довільних трьох  різних вершин графа G існує простий ланцюг, що з’єднує дві з них і не проходить через третю.

Теорема 1.23.  В довільному  графі з n  вершинами,  k  компонентами  зв’язності  і кількістю ребер m задовольняються нерівності n−k ≤ m ≤ (n-k)(n-k+1)/2, причому ці оцінки є досяжними.

  Доведення: Нижню оцінку m ≥ n-k доведемо індукцією за кількістю ребер у графі G.

Якщо m = 0, то n = k, n-k = 0 і m ≥ n-k, тобто нерівність виконується.

Припустимо, що для всіх графів з кількістю ребер m ≤ t (t ≥ 0) нерівність m ≥ n-k виконується.  Розглянемо  граф  G  з n вершинами,  k  компонентами  зв’язності,  у якому t+1  ребро.  Вилучимо  з графа G  довільне  ребро.  Згідно  з теоремою 3 одержимо  граф  G',  у якому k чи  k+1  компонента  зв’язності.  За  припущенням індукції, у цих випадках         t ≥ n-k  та  t ≥ n-(k+1),  звідки  t+1 ≥ n-(k+1)+1 =  n-k. Отже, нерівність  для графа G  також виконується,  і за  принципом індукції  твердження доведено. Нижня оцінка досягається, наприклад, на будь-якому графі, що є прямою сумою k простих ланцюгів.

Доведемо  верхню  оцінку m ≤ (n-k)(n-k+1)/2.  Розглянемо  довільний граф G, що має n вершин, k компонент зв’язності та максимально можливу кількість ребер m. Тоді  всі його  зв’язні компоненти  є повними графами. Нехай у графі є дві повні компоненти  зв’язності, що  містять t  і s  вершин,  причому t ≥ s  ≥ 2.  Разом ці  дві компоненти  мають                    (t(t-1)+s(s-1))/2  ребер.  Кількість ребер у двох  повних компонентах зв’язності з t+1 та s-1 вершинами дорівнює

((t+1)t+(s-1)(s-2))/2 = (t(t-1)+s(s-1))/2+(t-s+1) > (t(t-1)+s(s-1))/2.

Звідси найбільша кількість  ребер можлива в графі, який має k-1  ізольовану точку (тривіальну  компоненту  зв’язності)  та  одну  повну         (n-k+1) – вершину компоненту, кількість ребер у якій дорівнює                    (n-k)(n-k+1)/2. 

Доведено 

Висновок 1.23.1.  Якщо  в графі з n  вершинами кількість ребер більше  ніж (n-1)(n-2)/2, то граф зв’язний.

 Доведення: Якщо граф має k компонент зв’язності та m ребер, то        m ≤ (n-k)(n-k+1)/2, звідки (n-1)(n-2) ≤ (n-k)(n-k+1), що можливо лише при k = 1, тобто граф зв’язний. 

Доведено

Висновок 1.23.2. Якщо m < n-1, то граф з n вершинами та m ребрами незв’язний.

   Доведення: Зв’язний  граф має  одну  компоненту  зв’язності  і  за  теоремою 5  m ≥ n-1, що уперечить умові. Тому граф не є зв’язним. 

Доведено

Висновок 1.23.3. Якщо граф з n вершинами незв’язний, то кількість його ребер не більше, ніж (n-1)(n-2)/2.

  Доведення: Це твердження є протилежним до висновку 1.23.1.

Доведено 

1.8. Дерева та  ліси

 

Ациклічний  зв’язний  граф  називається  деревом.  Кістяковим  деревом  граф називається такий його  суграф (підграф,  що  містить всі вершини графа),  що   деревом. Ациклічний граф називається лісом. Відповідно, кістяковим лісом граф називається пряма сума  кістякових  дерев усіх  компонент зв’язності  графа Кістяковий ліс зв’язного графа складається з єдиного дерева. Приклад дерева показаний на рис.1.37.

Рис.1.37.

Кістякові дерева з’явилися  в роботах Кірхгофа, який у 1847 р. розробив теорію дерев  для  визначення  сили  струму  в  кожному  провіднику  та  кожному  контурі електричної  схеми. Пізніше, в 1857 р. Келі розглядав  дерева як модель насичених вуглеводнів  та розв’язав задачі перерахування  дерев.

Дерева (головним  чином,  кореневі  орієнтовані  з  навантаженими  вузлами  та дугами) широко  використовуються  в  обробці  інформації. Досить назвати  такі,  як пошук та сортування, трансляція, стискання даних та штучний інтелект [20, c. 54].

Теорема 1.24. Для довільного графа T = (V, E) з n вершинами і m ребрами наступн твердження рівносильні:

1) T – дерево (ациклічний зв’язний граф);

2) T – зв’язний  граф і m = n−1;

3)Т – ациклічний  граф  і m = n−1.

Доведення:  (1)⇒(2)  За  означенням  дерева  достатньо довести,  що              m = n−1.  Зробимо це індукцією за  кількістю вершин  n.  При n = 1  та       n = 2  деревами  є K₁  і K₂,  в яких m = n−1.  Нехай твердження  виконується  для  всіх  дерев  з  кількістю  вершин  не більше  t (t ≥ 2). Розглянемо  довільне  дерево  з t+1  вершиною  й вилучимо  з нього довільне  ребро.  Граф  ациклічний,  тому  за  теоремою 5(1.6)  одержимо  граф  з  двома компонентами  зв’язності. Кількості вершин  t₁  і t₂ у цих компонентах не більше  t, тому  для  них  виконується  припущення  індуції,  тобто  загальна  кількість  ребер  в одержаному  графі  дорівнює (t₁-1) + (t₂-1),  причому t₁+t₂ =  t+1.  З урахуванням вилученого  ребра  загальна  їх  кількість  у  дереві  з  t+1  вершиною  дорівнює (t₁-1) + (t₂-1) + 1 = t. Отже, за індукцією твердження доведено.