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

Існує  окремий  випадок,  у  якому  стягування  вершин  та  підрозбиття  ребра  є взаємно  оберненими  операціями  (з  точністю  до  ізоморфізму).  Якщо  під  розбиття ребра  (v, w)  утворює ребра (v, u)  і       (w, u),  то  стягування  кінців  одного  з них є оберненим до цього підрозбиття.

Кажуть, що граф G₁ стягується до графа G₂, якщо G₂  можна утворити з G₁ за скінченну кількість застосувань операції стягування вершин             [36, c.138].

Теорема 1.12.  Стягування  суміжних  вершин  планарного  графа перетворює  його на планарний граф.

Доведення:   Формальне доведення цього інтуїтивно  очевидного  твердження  досить громіздке,  хоча  неважко переконатися,  що  стягування  суміжни .

Доведено 

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

Доведення:     Кожен підграф планарного  графа є планарним,  операція  стягування перетворює  планарні  графи на  планарні.  Звідси  випливає,  що  стягування планарного графа не може утворити непланарний K₅ чи K_3,3, тому підграф і весь граф непланарні. 

Доведено

Наприклад, якщо в графі  Петерсена стягнути вершини A і F, B і G, C і H, I і D, J і E, то утвориться граф, ізоморфний непланарному графу K₅.

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

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

Як бачимо, K₅  чи K_3,3  є мінімальними непланарними графами й за відношенням “є результатом стягування”.

1.5. Одна задача  про плоскі графи

 

Розглянемо тепер два  приклади застосування графів для вирішення  задач.  В обох випадках задача зводиться  до того, щоб з’ясувати, чи можна  деякий граф зобразити на площині  так, щоб його ребра не мали зайвих точок перетину. В якості першої задачі розглянемо одну дуже давню  головоломку (« Задача про три  домівки і три криниці»).

Задача 1.6. На одній ділянці землі було побудовано три домівки і викопані три криниці для їх жителів. Природа країни і її клімат такий, що криниці часто пересихають, тому важливо, щоб від кожної із трьох домівок був підхід до кожної із трьої криниць. Через деякий час жителі домівок А, В, С серйозно посварились між собою і вирішили прокласти до трьох криниць X, Y, Z так, щоб по шляху до криниці і назад їм не доводилось зустрічати один одного. З’ясувати, чи можливо побудувати таким чином ці доріжки?

Розв’язання: На рис.1.25. зображений граф, який відповідає природньому розміщенню доріжок, коли всі вони прямолінійні.

Рис. 1.25.

Ці доріжки, або ребра  графа, перетинаються в багатьох точках, відмінних від точок розміщення домівок А, В, С і криниць X, Y, Z. Число зайвих точок перетину можна звести до 1, якщо провести доріжки так, як показано на рис.1.26.

Рис. 1.26.

Питання, яке ми хотіли поставити, виявлялося в наступному: чи є відповідний  граф плоским, т.б. чи можна провести доріжки так, щоб вони ніде не перетинались, крім вершин графа A, B, C, X, Y, Z. Скільки не намагайтесь, Ви не знайдете потрібного розв’язку. Однак наша неможливість вирішити задачу безпосередніми спробами і повторними намаганнями не дають математичного доказу тому, що це взагалі не можливо зробити. Суворе ж доведення засновано на наступній теоремі [28, c.22-23].

 Теорема 1.14. ( Жордана про криві): Нехай К – неперервна замкнута лінія на площині ( вона може бути задана прямокутником,  околом, еліпсом або будь-якою кривою дещо складнішою кривою). Лінія К ділить площину на внутрішню і зовнішню області так, щоб будь-яка безперервна крива α, яка з’єднує довільну точку Р внутрішньої області з деякою точкою Q зовнішньої області, перетинає К (див. рис.1.27.) [9, c.11-13].

Рис.1.27.

Твердження теореми Жордана  цілком очевидно; інтуїтивні геометричні  уявлення переконують нас в її справедливості. Однак, довести цю теорему досить складно; основна складність полягає в точному визначенні поняття «кривої». Ми опустимо тут це визначення. Приймаємо дану теорему за факт.

Із теореми Жордана  витікає той, також інтуїтивно очевидний  факт, що якщо будь-які 2 точки замкнутої лінії К, скажемо А і Y, з’єднати кривою AY, не маючи з К спільних точок, відмінних від А і Y, то вся ця крива, за винятком її кінців, лежить або зовні К, або в середині К (див. рис.1.28.).

Рис. 1.28.

Нехай тепер на замкнутій  лінії К маємо 4 точки, розміщені в порядку A, B, Y, Z, і проведені лінії AY і BZ, які не перетинаються між собою. Тоді обов’язково одна з них, нехай AY, лежить всередині К, а інша BZ – зовні К (див.рис.1.28.). Це можна довести за допомогою теореми Жордана, але ми можемо прийняти це і без доведення.

Нехай, на лінії К маємо шість точок, розподілених таким чином: A, X, B, Y, C, Z (рис.1.28.). Тоді три з’єднуючі їх криві AY, BZ, CX  не можуть не перетинатися.

Для того, щоб переконатися в цьому, зазначимо, що ці дві криві  повинні бути розміщені в двох площинах – внутрішній і зовнішній  по відношенню до К, в крайньому випадку дві з них потраплять в одну і ту ж площину і, таким чином, обов’язково перетнуться.

Це міркування ми безпосередньо  застосуємо до нашої задачі про трьох  ворогуючих сусідів і їх криниці. Припустимо, що граф на рис. 1 плоский . Зобразивши перетинаючі ребра AX, XB, BY, YC, CZ, ZA цього графа, ми отримаємо на площині замкнуту криву. Але тоді, як ми щойно пояснили, ребра AY, BZ, CX уже не можна провести так, щоб вони не перетинались.

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

1.6. Ейлерові графи

 

Ейлеровим шляхом у графі називається шлях, що містить всі ребра графа. Ейлеровим циклоом в графі називається шлях, що містить всі ребра графа і починається та закінчується в одній вершині. Зв'язний граф G називається ейлеровим, якщо існує замкнутий ланцюг, що проходить через кожне його ребро. Такий ланцюг називається ейлеровим ланцюгом [1, c.34].

Приклад 1.7.

Граф, зображений на рис.1.29, а має власний ейлерів ланцюг, а граф, зображений на рис.1.29, б – не має.

а) б)

Рис. 1.29.

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

Рис.1.30.

Приклад 1.8.

Граф, зображений на рис.1.31,а  має ейлерів цикл,  а граф, зображений на рис.1.31, б – не має.

а) б)

Рис.1.31

Зауважимо, що припущення про  зв'язність графа G введено тільки заради зручності, тому що воно дозволяє не розглядати тривіальний випадок графа, що містить кілька ізольованих вершин.

Рис.1.31.

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

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

Теорема 1.15. Якщо граф G має ейлерів цикл, то він є зв'язним, а всі його вершини є парними.

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

Доведено

Теорема 1.16. Якщо граф G зв'язний і всі його вершини парні, то він містить ейлерів цикл.

Доведення: Якщо розпочати шлях з довільної вершини графа G, то знайдеться  такий цикл, що містить всі ребра графа,  наприклад, граф, зображений на рис. 1.32.

 

Рис.1.32.

Нехай v_а - довільна вершина графа. З v_а почнемо шлях l по одному з ребер і продовжимо його, проходячи кожен раз по новому ребру. Всі вершини графа мають парну степінь, тому якщо є "вихід" з v_а, то повинен бути і "вхід" в v_а, так само як і для будь-якої іншої вершини. І якщо є «вхід» в вершину, то повинен бути і «вихід». Так як число ребер скінчене, то цей шлях повинен закінчитися, причому в вершині v_а. На рис.1.32.  шлях l і напрям його обходу показані кривими лініями зі стрілками. Якщо шлях l, який замкнувся в v_а, проходить через всі ребра графа, то це означає,  що ми отримали шуканий ейлерів цикл. Якщо залишилися не пройдені  ребра, то повинна існувати вершина v_b,  що належить шляху l  і ребру, що не ввійшло в l. Так як вершина v_b – парна, то число ребер, яким належить v_b і які не увійшли в шлях l, теж парне. Почнемо новий шлях s з v_b  і використовуємо тільки ребра, що не належать l. Цей шлях скінчиться в v_b. На рис.1.32.  шлях s позначений прямими лініями зі стрілками. Об'єднаймо тепер обидва цикли: з v_a пройдемо по шляху l до v_b, потім по циклу s і, повернувшись в v_b, пройдемо по частині шляху назад в v_a. Якщо знову знайдуться ребра, які не увійшли в цей шлях, то знайдемо нові цикли. Число ребер і вершин скінчене, процес закінчиться [36, c. 83].

Доведено

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

Таким чином, замкнуту фігуру, в якій всі вершини - парні, можна  зобразити одним розчерком без  повторень, починаючи обводити її з  будь-якої точки.

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

Теорема 1.17. Якщо граф G має ейлерів шлях з кінцями v_a і v_b (v_a не співпадає з v_b), то граф  G є зв'язним, і v_a  та  v_b – єдині непарні його вершини.

Доведення:  Зв'язність графа випливає з визначення ейлерового шляху. Якщо шлях починається в   va, а закінчується в іншій вершині vb, то va і vb - непарні, навіть якщо шлях неодноразово проходив через v_a і v_b. В будь-яку іншу вершину графа шлях повинен був привести і вивести з неї, тобто всі інші вершини повинні бути парними. Вірно і зворотне твердження.

Доведено

Теорема 1.18. Якщо граф G зв'язний і v_а  і  v_b  - єдині його непарні вершини, то граф G містить ейлерів шлях з кінцями v_а  і  v_b.

Доведення: Вершини   v_a  і   v_b   можуть бути з'єднані ребрами в графі (див. рис.1.33, а), а можуть бути і не з'єднані(див. рис.1.33, б).

 

a)                                                                                                    б)

Рис.1.33.

 Якщо v_a  і v_b з'єднані ребром, то видалимо його. Тоді всі вершини стануть парними. Новий граф, згідно попередньої теореми, містить ейлерів цикл, початком і кінцем якого може служити будь-яка вершина. Почнемо ейлерів шлях у вершині v_a і закінчимо його в вершині v_a. Додамо ребро    (v_a,v_b) і отримаємо ейлерів шлях з початком в v_а  та кінцем в v_b.

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

Теорема 1.19. Якщо зв'язний граф G має 2k непарних вершин, то знайдеться сімейство із k шляхів, які в сукупності містять всі ребра графа в точності по одному разу.

Доведення:Половину непарних вершин позначимо v₁, v₂, …, v_k, а іншу половину – w₁, w₂, …, w_k (див. рис.1.34.).

Рис.1.34.

Якщо вершини v_і, w_і (1 ≤ i ≤ k)  з'єднані ребром, то видалимо з графа G ребро (v_і, w_і). Якщо вершини v_і, w_і  не з'єднані ребром, то додамо до графа G ребро (v_і, w_і). Всі вершини нового графа будуть парними, тобто в новому графі знайдеться ейлерів цикл. При відновленні графа G, цикл розіб'ється на k  окремих шляхів, що містять всі ребра графа.

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