Граф (математика)

Граф зі шістьма вершинами та сімома ребрами

Граф — це сукупність об'єктів із зв'язками між ними.

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

Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини — це статті, а дуги (орієнтовані ребра) — посилання на інші статті.

Історія

Першою працею з теорії графів як математичної дисципліни вважають статтю Леонарда Ейлера (1736), у якій розглядалася задача про Кенігсбергські мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень по електричних мережах, кристалографії, органічній хімії та іншим наукам.

Визначення

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

Граф

Граф або неорієнтований граф $G$ — це впорядкована пара $G := (V, E)$, для якої виконуються наступні умови:

• $V$ — множина вершин або вузлів,
• $E$ — множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.

$V$ (і так само $E$) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.

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

Орієнтований граф

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

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

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

Іноді є потреба пару вершин з'єднати більше, ніж одним ребром. Мультиграфом називають пару G=(V,E), де V — множина, елементи якої називають вершинами. E — сім'я ребер, кожне з яких — це пара вершин із V.

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

Мультиграф, який може мати петлі, іноді називають псевдографом.

Тип графу	Ребра	Кратні ребра
Простий граф	Неорієнтовані	Ні
Мультиграф	Неорієнтовані	Так
Орієнтований граф	Орієнтовані	Ні
Орієнтований мультиграф	Орієнтовані	Так

Поняття

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

Способи представлення графа в пам'яті ЕОМ

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

У подальшому будемо припускати, що вершини графа мають номери від 1 до N, а ребра — від 1 до M. Кожному ребру і кожній вершині зіставлена вага — ціле позитивне число.

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

:Детальніше Матриця суміжності

Матриця суміжності це двовимірний масив розміром N*N:

 // матриця суміжності
 
    Type TAdjacencyMatrix = array [1..N, 1..N] of Integer;
    Var Graph: TAdjacencyMatrix;

При цьому Graph[i, j] дорівнює 0, якщо вершини i та j не є суміжними, та 1 для суміжних вершин. Для зваженого графа Graph[i, j] дорівнює вазі вершини i, якщо i=j, а для суміжних вершин — вазі ребра (дуги) з вершини i у вершину j.

Просторова складність цього способу O(N²)

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

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

Детальніше Матриця інцидентності

Матриця інцидентності це двовимірний масив розміром N*M:

// матриця інцидентності
 
 Type TIncidenceMatrix = array [1..N, 1..M] of Integer;
 Var Graph: TIncidenceMatrix;

При цьому Graph[i, j] дорівнює 0, якщо вершини i та ребро j не є інцидентними, −1, якщо вершина i є кінцем орієнтованого ребра j, +1, якщо вершина i є початком орієнтованого ребра j. Інколи зручно користуватись означенням, у якому Graph[i, j] вазі ребра (дуги) j, що є інцидентним вершині i.

Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині x.

Списки суміжності

Детальніше Список суміжності

Список суміжності це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною:

// список суміжності
 
 Type TAdjacencyList = array [1..N] of record
   Count: Integer; {кількість елементів у списку}
   List: array[1..N] of 
       record {список}
        Node, {номер суміжної вершини}
        Weight: Integer; {вага ребра}
       end;
   end;
   Var Graph: AdjacencyList;

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.

Список ребер

Детальніше Список ребер

 // динамічний список ребер (із вказівниками)
 
 // застосовують тоді, коли кількість ребер невідома наперед і їх багато
 
   Type ListElPtr=^ListEl;   {вершини графа позначені числами }
                                             {(номерами)}
     ListE l= record
     Node1, Node2: integer; {список складаються із пар цілих чисел: }
                                 {перше - звідки ребро, друге - куди}
     Next:ListElPtr;              {вказівник на наступне ребро графа}
   end;
 // список (масив) ребер
 
 // застосовують тоді, коли кількість ребер відома наперед і невелика
 
 
   Type TBranchList = array [1..M] of 
      record
       Node1, Node2, {пари вершин, що зв'язує ребро}
       Weight: Integer; {вага ребра}
   end;
   Var Graph: BranchList;

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

Застосування графів

Застосування графа у моделюванні (описі) процесів збагачення корисних копалин

Графи широко використовуються в багатьох сферах науки і техніки, зокрема:

• Файлова система комп'ютера. Ієрархія файлів та тек в багатьох операціних системах має вигляд дерева, яке є окремим випадком графа;
• Молекули усіх хімічних речовин можна зобразити у вигляді графа, де атоми є вершинами, а зв'язки між ними — ребрами;
• Карта автомобільних чи будь-яких інших шляхів також є графом, причому кожна дорога може мати певне значення «ваги» (наприклад, щільність транспортного потоку), тоді такий граф є зваженим;
• Соціальні мережі також можна представити у вигляді графа, де кожна людина чи соціальна група є вершиною, а зв'язки між ними — ребрами;
• Генеалогічні дерева є прикладом бінарних дерев, що також є окремим випадком графа;
• Турнірні таблиці спортивних чемпіонатів також можуть бути зображені у вигляді графів;
• У біології та екології графи також використовуються вже давно. Прикладами можуть бути ланцюги харчування, екосистеми, генетичні послідовності та карти, таксономічна ієрархія живих організмів тощо;
• У археології та геології графи використовуються у стратиграфії для вивчення геологічних пластів;
• Будь-який виробничий процес також може бути зображений за допомогою графа (див. приклад — технологічна схема збагачення корисних копалин);
• Розробка програмного забезпечення та комп'ютерні науки взагалі є однією з тих галузей, де графи застосовуються найчастіше. Складність та велика кількість модулів і протоколів у сучасних програмних продуктах сильно ускладнює розуміння їх роботи, керування нею та її оптимізацію, тому дуже часто складаються графи програм, причому найчастіше це робиться автоматично трансляторами чи компіляторами. Графи також є зручними для зображення структур даних, блок-схем, потоків даних, схем баз даних та баз знань, скінченних автоматів, схем комп'ютерних мереж та окремих сайтів, схем викликів підпрограм тощо. Також графи широко використовуються у багатьох алгоритмах пошуку та сортування. Крім того, одним з головних напрямків сучасних досліджень у царині глобальних мереж є задане консорціумом W3C завдання побудови семантичної мережі (один з видів графів) на базі існуючої мережі Інтернет.

Див. також

• Дерево (теорія графів)
• Цикломатичне число
• Маршрут (теорія графів)
• Матриця суміжності
• Словник термінів теорії графів

Література

• Спекторський І. Я. (2004). Дискретна математика. "Політехніка". с. 220 c. ISBN 966-622-136-5. 
• (англ.) J.A. Bondy, U.S.R. Murty (1976). Graph Theory with Applications. Elsevier/North-Holland. с. 264 c. ISBN 0-444-19451-7. 
• (англ.) J.A. Bondy, U.S.R. Murty (2008). Graph Theory. Springer. с. 654 c. ISBN 978-1-84628-969-9. 
• (англ.) Jungnickel, Dieter (2008). Graphs, Networks and Algorithms. Springer. с. 650 c. ISBN 978-3-540-72779-8. 
• (англ.) Сик Дж., Ли Л., Ламсдэйн Э. (2006). C++ Boost Graph Library. Питер. с. 304 c. ISBN 978-5-469-00352-6. 
• (англ.) Robert Sedgewick (2003). Algorithms in Java, Third Edition, Part 5: Graph Algorithms. Addison Wesley. с. 528 c. ISBN 0-201-36121-3. 
• Березина Л. Ю. Графы и их применение. — М.: URSS, 2009. — 152 с.
• Берж К. Теория графов и ее применения. — М.: ИЛ, 1962. — 320 с.
• Голиков А. П., Черванёв И. Г., Трофимов А. М. Математические методы в географии. — Х.: Изд-во ХГУ, 1986. — 143 с.
• Ловас Л., Пламмер М. Прикладные задачи теории графов. — М.: Мир, 1998. — 656 с.
• Михеева В. С. Приложение теории графов: Курс лекций (ч. 2) // Математические методы в экономической географии. — М.: Изд-во МГУ, 1983.
• Оре О. Теория графов. — М.: Наука, 1980. — 336 с.
• Татт У. Теория графов. — М.: Мир, 1988. — 424 с.
• Фляйшнер Г. Эйлеровы графы и смежные вопросы. — М.: Мир, 2002. — 176 с.
• Харари Ф. Теория графов. — М.: Мир, 1973. — 304 с.