Теорія графів

Означення 2.15. Граф називається „зв'язний", якщо кожні дві його вершини зв'язні; якщо ж у графі знайдеться хоча б одна пара незв'язних вершин, то граф називається „незв'язним".

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

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

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

            а)                                б)                              в)

 

Означення 2.16. Деревом називається зв'язний граф, що не містить циклів.

До речі, граф, який складається  з однієї ізольованої вершини, теж  є деревом.

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

Для кожної пари вершин дерева існує  єдиний шлях, який їх з'єднує. Вершина дерева, степінь якої рівна одиниці, називається висячою вершиною або листям (рис. 2.9) (Зображені в кольорі).

              А

Рис. 2.9. Дерево графа.

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

Означення 2.17. Незв'язний граф, що складається винятково з дерев, називається лісом.

Означення 2.18. Дерево, усі п вершин якого мають номера від 1 до п, називають деревом з пронумерованими вершинами.

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

Означення 2.20. Ейлеревим шляхом називається шлях, який починається в вершині А, а закінчується в вершині Б, і всі ребра проходять лише по одному разу. Граф, який включає в себе Ейлерів цикл, називається Ейлеревим.

Розглянемо таке поняття, як формула  Ейлера.

Нехай в плоскому графі t - кількість вершин; р - кількість ребер; g – кількість граней з врахуванням зовнішньої (рис.2.10).

Рис. 2.10. Формула Ейлера.

Перетворимо даний граф в дерево, яке має всі його вершини. Для  цього видалимо деякі ребра графа, розриваючи по черзі всі його прості цикли, при чому так, щоб граф залишався зв'язним і без перегородок. Помітимо, що при такому видалені одного ребра число граней зменшується на 1, так як при цьому пропадає один простий цикл, або два простих цикла перетворюються на один. Тобто значення різниці p-g не змінюється. На малюнку видалені ребра зображуються штриховими лініями. В отриманому дереві позначимо:

t₁ - кількість вершин; р₁ - кількість ребер; g₁ - кількість граней.

Справедлива рівність р - g = p₁ – g₁.

Дерево має тільки одну грань, тобто  р - g = pi - 1. Операція видалення ребер не міняє кількості вершин, тобто t = t₁. Так як дерево з п вершинами має п-1 ребро, в даному дереві t₁ – p₁ = 1, звідси t – р₁ = 1, тобто p₁ = t -1, а тому р - g = t - 2 або t -р + g = 2. Отже, доведено, що для плоского графа з t вершинами, р ребрами, g гранями, справедлива формула t -р + g = 2.Ця формула називається формулою Ейлера.

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

3. ОСНОВНІ ТЕОРЕМИ ТЕОРІЇ ГРАФІВ

Спираючись на приведені вище основні  поняття теорії графів, приведемо  формулювання і доведення теорем, що потім знайдуть своє застосування при вирішенні задач.

Теорема 3.1. В будь-якому графі сума степенів його вершин дорівнює подвоєному числу його ребер.

Доведення. Нехай А_1, А₂, Аз, ..., А_п — вершини даного графа, а p(A₁)_t р(А₂), ..., р(А_n) - степені цих вершин. Підрахуємо число ребер, що сходяться в кожній вершині, і просумуємо ці числа. Це рівносильно знаходженню суми степенів усіх вершин. При такому підрахунку кожне ребро буде враховано двічі (адже воно завжди з'єднує дві вершини).

Звідси  випливає;р(А₁)+р(А₂ )... +p(A_n)=2N,

де N— число ребер.

Теорема 3.2. Число непарних вершин будь-якого графа парне.

Доведення. Нехай а_1, а₂, а₃, .... а_k — це степені парних вершин графа, а 6₁, 6₂, 6з,,.., 6_т — степені непарних вершин графа. Сума а ₁+ а₂ + а₃ + ... +а_k+6₁+6₂+6з+ ...6m рівно в два рази перевищує число ребер графа. Сума а₁+ а₂+ а₃ ...+ а_k парна (як сума парних чисел), тоді сума 6₁ + 6₂+6₃+...+ 6_т повинно бути число парне. Це можливо лише в тому випадку, якщо т — парне, тобто парним є і число непарних вершин графа. Що і було потрібно довести.

Теорема  3.3.   У  будь-якому  графі  з  п  вершинами, де  (n≥ 2),  завжди знайдуться дві чи більше вершини і однаковими степенями.

Доведення. Якщо граф має п вершин, то кожна з них може мати степінь 0, 1, 2,..., (п-1). Припустимо, що в деякому графі всі його вершини мають різний степінь, і покажемо, що цього бути не може. Дійсно, якщо р(А)=0, то це значить, що А — ізольована вершина, і тому в графі не знайдеться вершини X зі степенем p(X)=n-1

Cправді, ця вершина повинна бути з'єднана з усіма вершинами, у тому числі і з А, але А виявилася ізольованою. Отже, у графі, що має п вершин, не можуть бути одночасно вершини степеня 0 і (п-1). Це значить, що з п вершин знайдуться дві, що мають однакові степені.

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

Теорема 3.5. Якщо у графа всі прості цикли парної довжини, то він не містить жодного циклу непарної довжини.

Малюнок 3.1 пояснює умову теореми. На зображеному  графі всі 5 простих циклів-парні.

Рис. 3.1. Граф із простими циклами парної довжини

 

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

Теорема 3.6. Для того, щоб граф був Ейлеревим, необхідно і достатньо, щоб він був зв'язним і всі його вершини мали парний степінь.

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

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

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

Доведення цієї теореми дуже цікаве і характерне для теорії графів. Його також варто вважати конструктивним. Для доведення до вихідного графа приєднуємо ребро (А, У); після цього усі вершини графа стануть парними. Цей новий граф задовольняє всім умовам теореми 3.6, і тому в ньому можна прокласти Ейлерів цикл. І якщо тепер у цьому циклі видалити ребро (А, У), то залишиться шуканий ланцюг АВ.

Рис. 3.2. Ейлерів граф

На   цьому   прийомі   ґрунтується    доведення    наступної теореми, яку варто вважати узагальненням теореми 3.7.

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

Теорема 3.9. Різних дерев з п пронумерованими вершинами можна побудувати n^n-2.

Ця теорема відома, в основному, як висновок англійського математика А.Келі (1821—1895). Графи-дерева здавна привертали увагу вчених. Сьогодні двійкові дерева використовуються не тільки математиками, а і біологами, хіміками, фізиками й інженерами.

Теорема 3.10. Повний граф з п'ятьма вершинами не є плоским.

Доведення. Скористаємося формулою Ейлера: В-Р+Г=2, де В — кількість вершин плоского графа, Р — кількість його ребер, Г— кількість граней. Формула Ейлера справедлива для плоских зв'язних графів, у яких жоден з многокутників не лежить усередині іншого. На малюнку 3.3 зліва зображений граф, до якого формула не застосовна - заштрихований багатокутник знаходиться усередині іншого. Праворуч приведене зображення графа, до якого формула застосовна.

Рис. 3.3. Повний граф

Цю формулу можна довести  методом математичної індукції. Це доведення ми опускаємо. Відзначимо тільки, що формула справедлива і для просторових многогранників. Нехай усі п'ять вершин графа з'єднані один з одним (рис. 3.3). Зауважуємо, що на графі немає жодної грані, обмеженої тільки двома ребрами. Якщо через φ₁ позначити число таких граней, то φ₂=0. Далі міркуємо від супротивного, а саме: припустимо, що досліджуваний граф плоский. Це значить, що для нього вірна формула Ейлера. Кількість вершин у даному графі В=5, кількість ребер Р=10, тоді кількість граней Г=2-В+Р-2-5+10=7.

Це число можна представити  у виді суми: Г= φ₁+φ₂+ φ₃+…, де φ ₃— кількість граней, обмежених трьома ребрами, φ₄ — число граней, обмежених чотирма ребрами і т.д.

З іншого боку, кожне ребро є границею двох граней, а тому число граней

дорівнює 2P_t у той же час 2Р=20= Зφз + 4φ₄ +… . Помноживши рівність Г=7=φ ₃+ φ ₄ + φ₅ + ... на три, одержимо ЗГ=21=3(φ ₃+ φ ₄ + φ₅+…).

Ясно, що (3φ₃+ 3φ₄ +3 φ₅+…)<(3φ₄+4φ₄+5φ_5…) чи ЗМ<2Р, але за умови, що 2Р=20, а ЗГ=21. Тому висновок, отриманий при введеному нами припущення (граф плоский), суперечить умові. Звідси робимо висновок, що повний граф з п'ятьма вершинами не є плоским.

Теорема 3.77. (Теорема Понтрягіна-Куратовского) Граф є плоским тоді і тільки тоді, коли він не має в якості підграфа повного графа з п'ятьма вершинами.

В розглянутому параграфі висвітлені тільки основні теореми теорії графів. їхнє практичне застосування ми розглянемо в наступних параграфах роботи.

4. ЗАДАЧІ НА ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ.

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

графів.

Задача 4.1.  Необхідно скласти  фрагмент розкладу для одного дня  з урахуванням наступних обставин:

1. Вчитель  історії може дати  або  перший,  або другий,  або  третій уроки, але тільки один урок;
2. Вчитель літератури може дати один, або другий, або третій урок;
3. Математик готовий дати або тільки перший, або тільки другий урок;
4. Викладач фізкультури згідний дати тільки останній урок.

Скільки і  які варіанти розкладу, що задовольняє  всім перерахованим вище умовам одночасно, може скласти завуч школи?

Розв'язання. Без сумніву, цю задачу можна вирішити шляхом звичайного перебору всіх можливих варіантів, але розв'язання буде найбільш простим, якщо намалювати граф у вигляді дерева. Необхідний граф зображений на мал. 4.1. На ньому виділені три можливих варіанти розкладу уроків.

Мал. 4.1. Варіанти розкладу уроків

Дана задача є класичним  прикладом вдалого використання теорії графів. В даний час існує програма "Розклад 3.0" комп'ютерної фірми Лин Тех, вирішена з використанням сучасних технологій.

 

 

 

Розглянемо  ще одну задачу, розв'язанням якої також  є граф.

Задача 4.2. У складі експедиції повинно  бути 6 фахівців: біолог, лікар, синоптик, гідролог, механік і радист. Маємо 8 кандидатів, з яких і потрібно вибрати  учасників експедиції; умовні імена  претендентів: А, В, С, D, E, F, G і Н. Обов'язки біолога можуть виконувати Е і G, лікаря - А і D синоптика - F і G, гідролога — В і F, радиста С і D, механіка — С і H. Передбачено, що в експедиції кожний з них буде виконувати тільки один обов'язок. Кого й на яку посаду варто включити до складу експедиції, якщо F не може їхати без В, D - без Н і С, С не може їхати разом з G, A - разом з В?

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

Стосовно до задачі про експедицію одна група вершин є група з 8 кандидатів, а друга - з 6 посад. Розв'язання задачі зображене на парному графі (мал. 4.2).

Мал. 4.2. Розв'язок задачі про склад експедиції

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

Розв'язання. Граф зображений на рисунку 4.3. має лише дві непарні вершини (їх позначено цифрами 2 і 6).

 

 

Мал. 4.3. Розв'язок задачі про снігоочисну машину

Отже, на основі властивості зв'язного графа, сформульованої ще Ейлером, яка

говорить про те, що граф з двома  непарними вершинами можна накреслити не

відриваючи олівця від паперу, причому  цей рух треба починати з однієї з цих

непарних вершин, а закінчувати  в іншій, приходимо до висновку, що водій має

почати роботу з перехрестя 2 або  з перехрестя 6 (якщо рух почне  з перехрестя 2, то