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

Рис.3.3.

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

 

Рис.3.4.

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

Рис.3.5.

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

Розв’язання:  Електроенергія Е, витрачена електропоїздом, залежить від механічної роботи  А (в Дж), виконаної під час руху поїзда. Оскільки енергія Е (залежний вузол) залежить від механічної роботи А (незалежний вузол0, то потрібну залежність можна подати так, як показано на рис.3.6.

 

Рис.3.6.

Щоб підвести підрахунки в кВт · год, візьмемо до уваги, що               1 кВт · годстановить 3,6*1000000 (Дж) (див.рис.3.7.).

 

1/3,6*1000000

Рис.3.7.

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

 

                       1/3,6*1000000

                

Рис.3.8.

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

 

Рис.3.9.

Остаточно:

 

 

 

Рис.3.10.

За допомогою  графів вдається спростити розв’язання  задач з електротехніки. При цьому  застосовується така властивість електричного кола:

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

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

Так, якщо контур складається  з двох джерел струму (Е1, Е2) і трьох віток з опорами R1, R2, R3 (див.рис.3.11,а), то сила струму в одній з віток, наприклад з опором R1, визначається графом, поданим на рис.3.11,б [25, c. 278-280].

 

Рис.3.11.

Задача 3.2. Дано електричне коло, для якого відомі ЕРС, Е1, Е2, Е3 та опори R1, R2, R3.Потрібно знайти силу струму в вітці АВ (див.рис.3.12,а).

 

Рис. 3.12.

Розв’язання:

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

Крім того, застосувавши для визначення струму І1, І2, І3 сформульоване вище правило, дістанемо граф, зображений на рис.3.12, в.

Цей граф після еквівалентних  перетворень, подаємо так, як показано на рис.3.12, г.

3.2. Хімія

 

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

Займаючись практичними  задачами органічної хімії, Келлі в 1857 р. відкрив важливий клас графів, названих деревами. Він намагався  перерахувати ізомери вуглеводів СnH2n+2 з даним числом n атомів вуглеводню; деякі з цих вуглеводнів показані на рис.3.13.

 

    Метан           Етан           Пропан             Бутан           Ізобутан

Рис.3.13.

Звичайно, Келлі, перш за все, сформулював задачу абстрактно: знайти число всіх дерев з р вершинами, кожне з яких має вершини зі степенями 1 і 4. Йому не вдалося відразу розв’язати цю задачу, і він став змінювати формулювання задачі таким чином, щоб можна було розв’язати нову задачу про перерахування:

а) корінних дерев (в яких виділена одна із вершин);

б) всіх дерев;

в) дерев, у яких степені  вершин не перевищують 4;

г) дерев, у яких степінь  вершин рівний 1 і 4;

Пізніше в Жордан (1869 р.)  незалежно від Келлі ввів і  вивчав дерева як математичні об’єкти, і , як писав Сільвестр в 1882 р., він  зробив це, «навіть не підозрюючи про  значення свого відкриття для  сучасної хімічної науки» [25, c.48].

За допомогою графів зручно будувати структурні хімічні формули.

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

2Р = 4n + 1(2n + 2)

Крім того, до структурної  формули входить однакова кількість  атомів вугдецю та водню. Тому кількість  вершин дерева:

В = n + 2n+2 = 3n + 2

Для дерева маємо: Р = В – 1. У даному випадку справджується рівність

3n + 1 = (3n + 2) -1

Отже, вуглеводні. Структурні формули яких являють собою дерево, записують у вигляді СnH2n+2.

Нехай тепер відомо, що й  структурна формула вуглеводнів  виду СхНу (х, у ϵ N) є деревом, де х – кількість вершин степеня 4, у – кількість вершин степеня 1. Потрібно знайти значення х і у.

Можна записати:

4х + у = 2Р          (*)

Крім того, для дерева

Р = В – 1

У нашому випадку В = х + у.

Підставивши значення В і Р у (*), дістанемо:

4х + у =2(х  + у – 1),

або                                   у = 2х + 2

Оскільки нам вдалося  у подати через х, то формулу СхНу можна записати у вигляді СхН2х+2, або СnH2n+2.

Отже, формула вуглеводнів  справді має вигляд СnH2n+2.

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

Розв’язання: 1) n =1, дістанемо формулу СН4 (метан), якій відповідає граф, зображений на рис.3.14.

 

Рис.3.14.

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

Рис.3.15.

2. n =3, дістанемо формулу С3Н8 (пропан), якій відповідає граф, зображений на рис.3.16 [25, c. 49].

Рис.3.16.

3. 3. Біологія і  психологія

 

в 1936 р. психолог Левін висловив припущення, що «життєвий простір» індивідума можна представити за допомогою планарної карти. На такій  карті області представляють  різні види діяльності людини, наприклад, те що він робить на роботі, вдома, або  його хобі.

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

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

Задача 3.4. Скільки різних типів гамет може дати гібрид, гетерозиготний за 3, 4, 5, … незалежними ознаками?

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

Отже, ген кожної ознаки може з’явитись у гаметі двома способами (Рис.3.17.).

Рис. 3.17.

З графа видно, що три гени з І, ІІ, ІІІ ознаками з’являються  трьома способами.

Якщо є чотири, або  у загальному випадку, n ознак, то тип гамети визначається відповідно чотирьох, n генів. Якщо скласти відповідні графи, то дістанемо, що при наявності 4, n незалежних ознак може утворитись відповідно 2⁴ і 2ⁿ рызних типів гамет.

3.4. Інформатика

 

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

Визначення алгоритму  було сформульовано у формі трьох  класичних алгоритмічних систем: машин Тьюрінга і Поста, нормальних алгоритмів Маркова і рекурсивних  функцій. Класичні алгоритмічні системи  були в основному розроблені до появи  електронно-обчислювальних машин, виходячи із потреби самої математики. Практичне  обчислення задач на комп’ютері відкрила широке коло важливих проблем, досить далеких від розглянутих в класичних системах алгоритмів [16, c. 187].

Опис алгоритмів проведений з допомогою граф-схем:

1. Спрощує викладання основ теорії машин Тьюрінга;
2. Дозволяє вийти за рамки класичної теорії алгоритмів дякуючи тому, що в теорію включаються питання, поставлені практикою користування комп’ютером (що важливіше).

3.4.1. Програмування

 

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

Зв’язки між задачами                                                                  Таблиця 4

Задача системного програмування	Відповідна задача теорії графів
Оптимізація програм, в тому числі виділення  фрагментів (структуризація) і декомпозиція	Знаходження домінантів Перерахування компонентів Перерахування контурів Перерахування гамаків Перерахування лінійних компонент Знаходження вкладених зон Знаходження вкладених контурів Інтервальне представлення графа
Перевірка правильності програм	Знаходження транзитивного і оберненого транзитивного  замикання Знаходження замикання відносно множини  вершин Перерахування шляхів Перерахування контурів
Визначення  порядку обробки операторів при  потоковому аналізі, тестування програм	Нумерація вершин Побудова довгих послідовностей вершин Знаходження покриття дуг шляхами Знаходження покриття необхідних шляхів шляхами Знаходження найкоротшого шляху при  наявності додаткових обмежень Знаходження множини фундаментальних  циклів Визначення цикломатичного числа

 

3.4.2. Графи як  об’єкти обробки інформації

 

Представлення графів в пам’яті   ЕОМ суттєво залежить від типів структури даних, що допускаються використовуванню мовою алгоритмів.

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

Відомі різні подання  графа у пам’яті комп’ютера, які розрізняються обсягом займаної пам’яті й швидкістю виконання  операцій над графами. Подання часто  вибирається, виходячи з потреб конкретного  завдання. Наведені чотири найбільш часто використовуваних подання із вказівкою характеристики n(p,q) – обсягу пам’яті   для кожного подання. Тут p – число вершин, q – число ребер.

Для подання орієнтованих графів можна використовувати різні  структури даних. Вибір структури  даних залежить від операторів, які  будуть застосовуватись до вершин і дуг орграфа [17, c. 236-237].

1. Матриця суміжності

Одним із найбільш загальних  і розповсюджених подань графа             G = (V,E) є матриця суміжності. Припустимо, що є безліч вершин                   V = {1,2,…,n}.

Матриця суміжності для графа G – це матриця А=array [1..p, 1..p] of 0..1, розміру n×n зі значенням , булевого типу, де A[i,j] = true тоді і тільки тоді, коли дуга з вершини v_i у вершину v_j. Часто в матрицях суміжності значення true замінюється на 1, а значення false – на 0. Або

 

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

Матриця суміжності неорієнтованого  графа симетрична відносно головної діагоналі, тому достатньо зберігати  в пам’яті тільки половину її. Подання  графа з допомогою матриці  суміжності зручно ще і тоді, коли граф зважений і елементами матриці є не нулі і одиниці, а ваги дуг [20, c. 73-75].

Задача 3.5.  На рис.3.18,б показана матриця суміжності для поміченого орграфа, зображеного на рис.3.18,а. Тут дуги представлені міткою символьного типу, а пробіл використовується при відсутності дуг.