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

гараж міститься  на перехресті 6, і навпаки). Отже, задача має два розв'язки.

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

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

Нехай А' і В' - проекції точок А і В, а М' і N' - крайні точки проекції многогранника (у точки M' і N' проектуються вершини М і N). Якщо йти з вершини А так, що в проекції рух буде відбуватися по напрямку від M' до N', то, зрештою, ми обов'язково потрапимо у вершину N. Аналогічно з вершини В можна пройти в N. Таким чином, можна проїхати з А у В (через N).

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

 

 

 

 

 

Задача 4.5. Тенісна сітка  є прямокутником розмірами 20x600 клітинок. Яке максимальне число мотузок, з яких вона сплетена можна розрізати так, щоб сітка не розпалась?

Розв'язання. Тенісну сітку можна зобразити у вигляді графа, де місця переплетення мотузок - вершини, а самі мотузки - ребра. Тепер запитання можна сформулювати по-іншому: яке максимальне число ребер можна вилучити, щоб граф залишився зв'язним?

Оскільки, коли граф є плоским  і зв'язним, то для нього справджується формула Ейлера: В+Г-Р=2, звідси Р=В+Г-2, де В- кількість вершин, Р- кількість ребер, Г - кількість граней.

Для нашого графа: В=601x21=12621

Кількість граней з врахуванням зовнішньої Г=600х20+1=12001, отже

Р= 12621+12001 -2=24620.

Можна вилучати ребра графа  доти, доки не отримаємо дерево. А  так як дерево з n вершинами має n-1 ребро, то максимальна кількість ребер, яку можна вилучити (Р₁) буде обчислюватися так:

Р₁ = 24620-(12621-1)=12000.

Отже, максимальне число  мотузок, яке можна розірвати  так, щоб сітка не розсипалась- 12000.

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

Розв'язання. Зобразимо дану залізницю за допомогою графа, вершини якого- станції, а ребра - лінії залізниць.

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

 

 

 

вершини (щоб  кількість станцій була непарною) і тоді, враховуючи умову з'єднувати ці вершини ребрами.

 

Мал. 4.4.

На мал.4.4,а показано, що для семи вершин даний обхід можливий. Додавши вершини 8 і 9, будуємо ребра 2-8 і 3-9. Добавляючи наступні вершини, отримуємо ребра 8-10, 9-11, 4-12, 5-13, 8-14 і 9-15 (мал.4.4,б). За такого розташування ребер з вершини 1 можна пройти до будь якої іншої вершини, проходячи не більше, чим по двох вершинах. Максимальна кількість вершин даного графа - 15, так як вершини 2, 3, 4, 5, 8, 9 уже мають найбільший степінь 3, тому подальша побудова нових ребер неможлива.

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

 

Мал. 4.5.

На мал.4.5 зображено схему розташування залізничних ліній в Тернополі, де можлива найбільша кількість  станцій- 15.

 

Ефективним є застосування графів для розв'язання задач з хімії. Наприклад, за допомогою графів зручно будувати структурні формули хімічних елементів.

Так, усі вуглеводні, структурні формули яких являють собою дерево, подаються у вигляді С_nH_2n+2 (nЄN). Справді, у відповідній структурній формулі n - кількість тих вершин, степінь яких дорівнює 4 (валентність вуглецю), а 2n+2-кількість тих вершин степінь яких дорівнює 1 (валентність водню).

Побудуємо структурні формули (графи) вуглеводнів, якщо n=1, 2, 3.

1. Якщо n=1, дістанемо формулу СН₄ (метан), якій відповідає граф, поданий на мал.4.6.а.
2. Якщо n=2, дістанемо формулу С₂Н₆ (етан), якій відповідає граф, зображений на мал.4.6.б.

3. Якщо n=3, дістанемо формулу С₃Н₈ (пропан), якій відповідає граф, 
зображений на мал.4.6.в.

Мал. 4.6. Структурні формули  вуглеводів.

Розглянемо тепер, як графи застосовуються при розв'язуванні фізичних задач.

У графів розрізняють вузли (вершини) трьох видів: джерела, стоки і каскадні вузли. Вузол, з якого вітки тільки виходять, називають джерелом; вузол, в який вітки тільки входять, - стоком. Вузол, який має вхідні і вихідні вітки, називають простим каскадним.

Кожний вузол характеризується так званим вузловим сигналом (х, у тощо), а вітка - передачею (a,b, с тощо),

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

 

 

 

 

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

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

 

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

Мал. 4.9.

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

 

Мал. 4.10.

 

Ще деякі з еквівалентних  перетворень графів подано на мал.4.10,4.11.

 

Мал. 4.10.

 

 

Мал. 4.11.

Розв'яжемо тепер фізичну задачу, застосовуючи еквівалентні перетворення

графів.

Задача 4.7. Електропоїзд, маса якого m, почав рухатись по горизонталі і протягом t с розвинув швидкість v м/с. Скільки кВтхгод електроенергії було витрачено за цей час, якщо коефіцієнт корисної дії двигуна дорівнює η, коефіцієнт тертя к. Опором повітря знехтувати.

Розв'язання. Електроенергія Е, витрачена електропоїздом, залежить від механічної роботи А (в Дж), виконаної під час руху поїзда. Величину цієї роботи нам треба визначити. Оскільки механічна енергія Е (залежний вузол) залежить від механічної роботи А (незалежний вузол), то потрібну залежність можна подати так, як показано на мал.4.13.

                                          Рис.4.13.

Щоб провести підрахунки в кВтxгод, візьмемо до уваги, що 1  кВтхгод

Мал. 4.14.

становить 3,6х 10⁶ Дж (мал.4.14).

 

Оскільки робота А визначається як добуток потужності на витрачений час, то можна побудувати граф, поданий на мал.4.15.

 

Аналогічно, зображуючи за допомогою графів залежності між  повною (N₀) і корисною (N) потужностями та k, η; між корисною потужністю N, силою тяги F і середньою швидкістю v_cep; силою тяги F, силою тертя F_тep і силою F_a (сила, що надає прискорення); силою тертя F_тep , коефіцієнтом тертя k і силою тиску (ваги електропоїзда р); силою F_a , масою m поїзда, прискоренням а і часом t, дістанемо граф, поданий на мал.4.16.

 

Мал. 4.16.

Остаточно: 

мал.4.17.

Мал. 4.17.

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

Причому знак „плюс” береться тоді, коли напрям струму, що проходить через інші згадані вітки, збігається з напрямом обходу контуру, в протилежному випадку береться знак „мінус”.

Так, якщо контур складається  з двох джерел струму (E₁, E₂) і трьох віток з опорами R₁, R₂, R₃ (мал.4.18,а), то сила струму в одній з віток, наприклад з опором R₁, визначається графом, поданим на мал.4.18,б.

 

Мал. 4.18.

Розглянемо задачу.

Задача 4.7. Дане електричне коло, для якого відомі ЕРС, Е₁, Е₂, опори R₁,R₂, R₃. Потрібно знайти силу струму у вітці АВ (мал.4.19,а).

 

 

 

 

 

 

 

 

                                       

 

 

 

 

 

 

Мал. 4.19.

 

 

Розв'язання. Для вузла В, за першим законом Кірхгофа, маємо граф, поданий на мал.4.19,б.

Крім того, застосувавши для визначення сили струму 11 та І2 сформульоване  вище правило, дістанемо граф, поданий  на мал.4.19,в. Цей граф після еквівалентних перетворень, подаємо так, як показано на мал.4.19, г.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ У РІЗНИХ ГАЛУЗЯХ НАУКИ І ТЕХНІКИ.

Графи й  інформація

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

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

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

Графи і хімія А. Келі розглянув задачу про можливі структури насичених (граничних) вуглеводнів, молекули яких задаються формулою:

C_nH_2n+2.

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

Таким чином, підрахунок числа гомологів граничних вуглеводнів також приводить до задачі про перерахування дерев визначеного типу.

 

Графи і  біологія

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

Нас буде цікавити лише одне питання: у скількох випадках n-1 покоління однієї бактерії нараховує рівно к нащадків? Рекурентне співвідношення, що визначає число необхідних випадків, відоме в біології під назвою процесу Гальтона-Ватсона. Його можна розглядати як окремий випадок багатьох загальних формул.