Лабораторна робота №10
Теорія графів останнім часом широко використовується в різних галузях науки і техніки. Швидкий розвиток дана теорія отримала зі створенням електронно-обчислювальної техніки, яка дозволяла вирішити багато завдань алгоритмізації.
Граф - це сукупність двох кінцевих множин: множини точок і безлічі ліній, попарно з'єднують деякі з цих точок. Безліч точок називається вершинами (вузлами) графа. Безліч ліній, що з'єднують вершини графа, називаються ребрами (дугами) графа.
Орієнтований граф (орграф) - граф, у якого всі ребра орієнтовані, тобто ребрам якого присвоєно напрямок.
Неорієнтовані граф (неорграф) - граф, у якого всі ребра неорієнтованого, тобто ребрам якого не задано напрямок.
Змішаний граф - граф, що містить як орієнтовані, так і неорієнтовані ребра.
Петлею називається ребро. з'єднує вершину саму з собою. Дві вершини називаються суміжними, якщо існує з'єднує їх ребро. Ребра. з'єднують одну і ту ж пару вершин, називаються кратними.
Простий граф - це граф, в якому немає ні петель, ні кратних ребер.
Мультіграф - це граф, у якого будь-які дві вершини з'єднані більш ніж одним ребром.
Маршрутом в графі називається кінцева чергується послідовність суміжних вершин і ребер, що з'єднують ці вершини.
Маршрут називається відкритим, якщо його початкова та кінцева вершини різні, в іншому випадку він називається замкнутим.
Маршрут називається ланцюгом. якщо всі його ребра різні. Відкрита ланцюг називається шляхом. якщо всі її вершини різні.
Замкнута ланцюг називається циклом. якщо різні все її вершини, за винятком кінцевих.
Граф називається зв'язковим, якщо для будь-якої пари вершин існує з'єднує їх шлях.
Вага вершини - число (дійсне, ціле або раціональне), поставлене у відповідність даній вершині (інтерпретується як вартість, пропускна здатність і т. Д.). Вага (довжина) ребра - число або кілька чисел, які інтерпретуються по відношенню до ребру як довжина, пропускна здатність і т. Д.
Зважений граф - граф, кожному ребру якого поставлено у відповідність деяке значення (вага ребра).
Вибір структури даних для зберігання графа в пам'яті комп'ютера має принципове значення при розробці ефективних алгоритмів. Розглянемо кілька способів подання графа.
Нехай заданий граф, у якого кількість вершин одно n, а кількість ребер - m. Кожне ребро і кожна вершина мають вагу - ціле позитивне число. Якщо граф не є позначеним, то вважається, що вага дорівнює одиниці.
Список ребер - це безліч, утворене парами суміжних вершин. Для його зберігання зазвичай використовують одновимірний масив розміром m, що містить список пар вершин, суміжних з одним ребром графа. Список ребер більш зручний для реалізації різних алгоритмів на графах в порівнянні з іншими способами.
Матриця суміжності - це двовимірний масив розмірності n x n, значення елементів якого характеризуються смежностьювершін графа. При цьому значенню елемента матриці присвоюється кількість ребер, які з'єднують відповідні вершини. Даний спосіб дієвий, коли треба перевіряти суміжність або знаходити вага ребра за двома заданими вершин.
Матриця інцидентності - це двовимірний масив розмірності n x m, в якому вказуються зв'язку між інцидентними елементами графа (ребро і вершина). Стовпці матриці відповідають ребрам. рядки - вершин. Нульове значення в осередку матриці вказує зв'язок між вершиною і ребром. Даний спосіб є найбільш ємним для зберігання, але полегшує знаходження циклів в графі.
Існує багато алгоритмів на графах, в основі яких лежить систематичний перебір вершин графа. такий що кожна вершина проглядається (відвідується) в точності один раз. Тому важливим завданням є знаходження хороших методів пошуку в графі.
При вирішенні багатьох завдань, що використовують графи, необхідні ефективні методи регулярного обходу вершин і ребер графів. До стандартних і найбільш поширених методів відносяться:
Ці методи найчастіше розглядаються на орієнтованих графах. але вони можуть бути застосовані і для неорієнтованих, ребра яких вважаються двонаправленими. Алгоритми обходу в глибину і в ширину лежать в основі вирішення різних завдань обробки графів, наприклад, побудови остовного лісу. проверкісвязності. ациклічності, обчислення відстаней між вершинами і інших.