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

 

а) б)

Рис.3.18.

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

2. Матриці інцидентності

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

3. Cриски суміжностей

Подання за допомогою списку суміжностей є головною альтернативою представлення з допомогою матриці суміжності. Списком суміжності для вершини і називається список всіх вершин, суміжних з вершиною і , причому певним чином упорядкований. Списком суміжності для вершини v є просто список вершин з множини Гv, тобто це список кінцевих дуг, що виходять з вершини v у випадку орграфа, або список суміжних з v вершин у випадку графа. Граф представляється з допомогою |X| списків суміжності, по одному для кожної вершини. Якщо число дуг в орграфі досить мале в порівнянні з повним графом, то цей спосіб представлення досить ефективний. Списки суміжності займають об’єм пам’яті  |X|+|E| і легко реалізуються з допомогою спускових структур. Часто використовуються різні варіанти списків суміжності, наприклад, задаються списки вершин із Г^-1v, спільні списки вершин із Гv та Г^-1v і т.д. Менш зручний цей спосіб представлення для задання зважених графів, оскільки тоді виникає додаткова задача зберігати десь ваги дуг і встановлювати відповідні зв’язки між дугами і їх вагами. Таким чином, орграф G  можна представити за допомою масиву HEAD (Заголовок), чий елемент HEAD (і) є покажчиком на списку суміжності  вершини і. Подання орграфа за допомогою списків суміжності вимагає для зберігання обсяг памяті, пропорційний  сумі кількості вершин і кількості дуг. Якщо кількість дуг має порядок Q(n), то й загальний обсяг необхідної пам’яті має такий же порядок. Але й для списків суміжності час пошуку певної дуги може мати порядок Q(n), тому що такий порядок може бути у кількості дуг в певній вершині    [26, c.135-136].

Задача 3.6. На рис.3.19. показана структура даних, що представляє орграф з рис.3.18, а за допомогою зв’язаних списків суміжності. Якщо дуги мають мітки, то їх можна зберігати в осередках зв’язаних списків.

 

Рис.3.19.

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

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

for кожна вершина w, суміжна з вершиною v do {деякі дії з вершиною}

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

1. FIRST(v) повертає індекс першої вершини, суміжної з вершиною v. Якщо вершина v не має суміжних вершин, то повертається «нульова» вершина.
2. NEXT(u,L) повертає індекс вершини, суміжної з вершиною v, що випливає за індексом L. Якщо і – це індекс останньої вершини, суміжної з вершиною v, то повертається «нульова» вершина.
3. VERTEX(v,i) повертає вершину з індексом і з безлічі вершин, суміжних з v.
4. Списки дуг

Представлення за допомогою списка дуг застосовується в тому випадку, коли необхідно мати окрему, незалежну нумерацію дуг. При цьому способі кожній дузі співставляється трійка (1,х,у), де 1 – дуга, х – її початок, у – її кінець. Цей спосіб представлення графа легко узагальнюється на випадок зважених графів. Більше того, він найбільше пристосований для зберігання різноманітної інформації про дуги [26, c. 32-35].

Нехай, G – неорієнтований граф,  A(G) – його матриця суміжності. Так як A(G) симетрична відносно головної діагоналі, будемо розглядати її тільки верхню трикутну частину А′. Запишемо рядки  А′ послідовно одну за іншою і розглянемо  отриману послідовність з нулів та одиниць як двійкове число. Змінюючи нумерацію вершин, будемо для одного і того ж графа отримувати різні числа. Найбільше з них визначається для графа однозначно і носить назву коду Харарі. Код Харарі визначає граф однозначно, тому, наприклад, знаходження ізоморфізму двох графів можна звести до порівняння відповідних кодів Харарі. Але і цей метод настільки ж не ефективний як і інші методи встановлення ізоморфізму двох довільних графів. Нумерація вершин (і матриця суміжності), що відповідає коду Харарі, носить назву канонічної і використовується при перечисленні (генеруванні) графів із заданими властивостями.

3.5. Математика

 

В математиці теорія графів широко використовується при розв′язуванні  задач прикладного характеру, а  також різноманітних головоломок. Приклади розв’язування таких задач  наведені в розроблених нами факультативних заняттях. Використання  елементів  теорії  графів  при  вивченні  математики,  зокрема  при  розв′язуванні  задач  присвячених праці Л.Ю.Березиної,  М.П.Барболіна, А.І.Глобіна, однак недостатньо досліджені  задачі,    які б стосувались розв’язування систем  лінійних  рівнянь за  допомогою графів.  

У  7  класі  учні  навчаються  розв′язувати  системи  двох  лінійних  рівнянь  з  двома  змінними  графічним  способом  та  способами  підстановки.  Інші,  нетрадиційні  способи  розв’язання  систем  лінійних  рівнянь  у 7-9  класах  не  вивчаються.  Тому розв′язування  систем  лінійних  рівнянь, що ґрунтується на використанні графів, варто  розглянути  на  факультативних заняттях. Сьогодні  факультативне навчання математики має поглиблювати знання  учнів,  здобуті  ними  під  час вивчення  основного  курсу,  а  також  розвивати  логічне  мислення,  цікавість до математики, творчі здібності. Але цей спосіб  розв′язування передбачає  ознайомлення  з основними поняттями елементів теорії графів. Учні мають знати,  що  під графом  розуміють систему точок (вершин)  і відрізків (їх називають ребрами графа),  що з’єднують деякі з цих точок.  Ребро графа називається орієнтованим,  якщо одну  вершину вважають  початком ребра, а другу – кінцем. На  рисунку орієнтоване ребро зображують стрілкою (рис.3.20). Говорять, що  орієнтоване ребро виходить  з вершини А  і входить в вершину В. Граф,  всі ребра якого орієнтовані, називається орієнтованим  графом  (рис.3.21.).

          

Рис.3.20.                           Рис.3.21.

Одна  і  та  ж  вершина  орієнтованого  графа  може  бути початком для одних ребер і  кінцем для  других.  Відповідно  розрізняють  дві степені  вершини:  степінь  виходу  і степінь  входу. Степенем  виходу  вершини  А орієнтованого графа називається число ребер,  які виходять  з А  (позначення:  ρ⁺(А)). Степенем  входу вершини А орієнтованого графа називається число ребер,  які входять в А  (позначення:  ρ^-(А)) [30, c.14-18].

Задача 3.7. Знайти степені входу і степені виходу для вершин А, B, C, D, E, F для графа, зображеного на рис.3.21.

Розв’язання: ρ⁺(А)=2,     ρ^-(А)=1;    ρ⁺(B)=1,    ρ^-(B)=1; Ρ⁺(C)=2,    ρ^-(C)=2;    ρ⁺(D)=0,   ρ^-(D)=2;  Ρ⁺(E)=0,     ρ^-(E)=0;    ρ⁺(F)=1,   ρ^-(F)=0.

В  орієнтованих  графах  будемо розрізняти вершини чотирьох видів. Вершина, у якої степені виходу і входу  дорівнюють  0  (ρ⁺ =0,  ρ^- =0), називається ізольованою.  Вершина,  у якої  степінь виходу  більша  0       (ρ⁺ > 0),  а степінь входу дорівнює  0  (ρ^- = 0), називається джерелом. Вершина, у якої степінь входу більша 0 (ρ^- > 0), а степінь виходу  дорівнює  0  (ρ ⁺ = 0),  називається стоком. Вершина, у якої і степінь входу і степінь виходу більші 0 (ρ⁺ >0, ρ^- >0), називається простою каскадною. На рис.3.21. вершина Е – ізольована,  F – джерело,  D – сток,  A, B, C – прості  каскадні. Щоб застосувати графи до розв′язування лінійних  рівнянь з кількома  змінними  або їх  систем, вважатимемо,  що  вершина графа відповідає  змінній,  а ребро,  що виходить  з вершини, - коефіцієнту     при цій змінній.  Кожна вершина характеризується  імпульсом вершини x, y, z, t тощо, а ребро – вагою ребра α, β, γ, ε тощо. Ребро можна побудувати, якщо його вага відмінна від нуля.  Кожний  вхідний імпульс дорівнює  добуткові ваги  ребра і імпульсу вершини,  з якого це  ребро виходить. Ребра,  що виходять  з вершини,  на  її імпульс не впливають. Якщо у вершину входить кілька  ребер,  то  її  імпульс дорівнює  сумі  вхідних імпульсів. Розрізняють послідовні  і паралельні ребра графа.  Якщо  початок наступного ребра збігається з кінцем попереднього, то такі ребра називаються послідовними. Ребра,  які виходять  з одної і тої самої вершини і входять в одну і ту саму вершину,  не  проходячи через інші,  називають паралельними. 

Побудуємо тепер модель лінійного  рівняння  або  систем  рівнянь.  На  рис.3.22. подано окремі приклади таких  моделей. На  рис. 3.23.  подано  основні  перетворення графів  і  відповідні  алгебраїчні  перетворення  рівнянь  або  систем.  Їх  треба розуміти  так:  а)  два  або  кілька паралельних  ребер  можна  замінити одним,  вага  якого  дорівнює  сумі  ваг паралельних ребер (рис.3.23,а); б) два або кілька  послідовних ребер можна замінити  одним,  вага  якого дорівнює добутку ваг послідовних ребер (рис.3.23,б). На  рис.3.23,в  і рис.3.23,г  показано  перетворення послідовних ребер графа.

Рис.3.22.

Рис.3.23.

Щоб виразити одну змінну через  інші, треба вершину, яка відповідає цій змінній, зробити стоком. На  рис.3.24.  і  на рис.3.25  показано,  як змінюється  вага  кожного  ребра  при зміні стоку [30, c. 18-22].

1.   Якщо джерело  і сток міняються місцями (рис.3.24.), то вага ребра на ново-му  графі  виражається  числом, оберненим  значенню  ваги  ребра  на вихідному:   I (рис.3.24).

2.   При  зміні   стоку  вага  ребра (рис.3.25,б),  яка виходить  з того  самого джерела, наприклад y, дорівнює добутку числа,  протилежного  значенню  ваги ребра (-β),  яка спочатку  виходила  з цього джерела (рис.3.25,а),  і нової ваги ребра, яка змінила напрям :

    (Рис.6)

Рис.3.24.

Рис.3.25.

Отже,  за  допомогою  графа  одну змінну  можна  виразити  через  інші, незалежно  від  їх  кількості.  У  процесі перетворення  графа  треба  прагнути  до поступового  перетворення  вершин-джерел у прості каскадні. Наприклад,  розв′яжемо  даним способом систему рівнянь (рис.3.26, назвемо  її базовою).

Задача 3.8. Розв’язати систему лінійних рівнянь:

 

Розв′язання: граф,  поданий на  рис.3.26,а, відповідає  базовій системі.  Граф  на рис.3.26,б,  дістали змінивши  сток. Вершина-джерело х  перетворилась  в просту каскадну вершину [21].

Рис.3.26.

Граф  на  рис.3.26,в,  дістали, змінивши послідовні й паралельні ребра графа (рис.3.26,б) окремими ребрами. Розв′язування системи зводиться до  розв′язування рівняння  першого степеня з однією  змінною,  яке відповідає  графу,  зображеному на рис.3.26,в:   - .

Щоб  знайти  х,  треба в рівняння, що  відповідає  графу,  поданому  на рис.3.26,б, замість змінної y  підставити її значення.  Оскільки  ребра,  що  виходять з вершини, на її імпульс не впливають, досить  розглянути  частину графа,  де вершина х  є стоком  (рис.3.27.)  і записати відповідне  рівняння:

Рис.3.27.

Відповідь: (5;2).

Спробуємо розв’язати системи  лінійних рівнянь, що не мають розв′язку  або мають нескінчену множину  розв’язків.

Задача 3.9. Розв’язати системи лінійних рівнянь:

1.                2) 

Розв′язання: на рис.3.28  і рис.3.29 зображені розв′язання для цих двох систем рівнянь. Вершина,  що  відповідає  змінній, ізольована  від  стоку,  оскільки  вага відповідного  ребра  дорівнює  нулю. Згідно з прийнятими вище домовленостями таке ребро не можна побудувати [21].

Рис.3.28.

Рис.3.29.

На рис.3.28,в ми маємо , це неправильна числова рівність,  а отже система 1) розв′язків не має.  На рис.3.29,в ми  маємо ,  це  правильна числова рівність,  і система 2)  має нескінченну множину розв′язків. 

Задача 3.10. Розв′яжемо  систему  трьох лінійних рівнянь з трьома змінними: