НОУ ІНТУЇТ | лекція | Що таке граф? Визначення та приклади

1. Вступ
2. уявлення
3. Можливості підключення і відстань

Анотація: Введення. Уявлення. Можливості підключення і відстань. Остовне дерева. Кліки. Ізоморфізм. Планарність.

Вступ

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

кінцевий граф складається з кінцевого безлічі вершин і кінцевого безлічі ребер . Кожному ребру відповідає пара вершин: якщо ребро відповідає ребру , То говорять, що інцидентне вершин і . Граф зображується наступним чином: кожна вершина представляється точкою і кожне ребро представляється відрізком лінії, що з'єднує його кінцеві вершини. Граф називається орієнтованим, якщо пара вершин , Відповідна кожному ребру, впорядкована. У такому випадку говорять, що ребро орієнтовано з вершини в вершину , А напрямок позначається стрілкою на ребрі. Ми будемо називати орієнтовані графи орграфа. У неорієнтованому графі кінцеві вершини кожного ребра не впорядковані, і ребра не мають напрямки. Ребро називається петлею, якщо воно починається і закінчується в одній і тій же вершині. Кажуть, що два ребра паралельні, якщо вони мають одну і ту ж пару кінцевих вершин (і якщо вони мають однакову орієнтацію в випадку орієнтованого графа). Граф називається простим, якщо він не має ні петель, ні паралельних ребер. Якщо не вказується протилежне, будемо вважати, що розглянуті графи є простими. усюди в "Алгоритми на графах" і "Калейдоскоп з комбінаторних алгоритмів" лекції будемо використовувати символи і для позначення відповідно числа вершин і числа ребер в графі .

уявлення

Найбільш відомий спосіб представлення графа на папері полягає в геометричному зображенні точок і ліній. У ЕОМ граф повинен бути представлений дискретним способом, причому можливо багато різних уявлень. Простота використання, так само як і ефективність алгоритмів на графі, залежить від відповідного вибору представлення графа. Розглянемо різні структури даних для представлення графів.

Матриця смежностей. Одним з найбільш поширених машинних уявлень простого графа є матриця смежностей або з'єднань. Матриця смежностей графа є - матриця , в якій , якщо в існує ребро, що йде з -й вершини в -у, і в іншому випадку. Орграф і його матриця смежностей представлені на Мал. 12.1.

Орієнтований граф і його матриця смежностей

Зауважимо, що в матриці смежностей петля може бути представлена ​​відповідним одиничним діагональним елементом. Кратні ребра можна уявити, дозволивши елементу матриці бути більше 1, але це не прийнято, так як зазвичай зручно представляти кожен елемент матриці одним двійковим розрядом.

Для завдання матриці смежностей потрібно двійкових розрядів. У неориентированного графа матриця смежностей симетрична, і для її подання досить зберігати тільки верхній трикутник. В результаті економиться майже 50% пам'яті, але час обчислень може при цьому трохи збільшитися, тому що кожне звернення до має бути замінено наступним: if then else . У разі подання графа його матрицею смежностей для більшості алгоритмів потрібен час обчислення, принаймні пропорційне .

Матриця ваг. Граф, в якому ребру порівнювати число , Називається зваженим графом, а число називається вагою ребра . У мережах зв'язку або транспортних мережах ці ваги представляють деякі фізичні величини, такі як вартість, відстань, ефективність, ємність або надійність відповідного ребра. Простий зважений граф може бути представлений своєю матрицею ваг , де є вага ребра, що з'єднує вершини і . Ваги неіснуючих ребер зазвичай вважають рівними або 0 в залежності від додатків. Коли вага неіснуючого ребра дорівнює 0, матриця ваг є простим узагальненням матриці смежностей.

Список ребер. Якщо граф є розрідженим, то можливо, що більш ефектно представляти ребра графа парами вершин. Це уявлення можна реалізувати двома масивами і . Кожен елемент в масиві є мітка вершини, а -е ребро графа виходить з вершини і входить в вершину . Наприклад, орграф, зображений на Мал. 12.1, буде представлятися таким чином:

Ясно, що при цьому легко представимо петлі і кратні ребра.

Структура суміжності. В орієнтованому графі вершина називається послідовником іншої вершини , Якщо існує ребро, спрямоване з в . вершина називається тоді попередником . У разі неорієнтованого графа дві вершини називаються сусідами, якщо між ними є ребро. Граф може бути описаний його структурою суміжності, тобто списком всіх послідовників (сусідів) кожної вершини; для кожної вершини задається - список всіх послідовників (сусідів) вершини . У більшості алгоритмів на графах відносний порядок вершин, суміжних з вершиною в , Не важливий, і в такому випадку зручно вважати мультімножество (або безліччю, якщо граф є простим) вершин, суміжних з . Структура суміжності орграфа, представленого на Мал. 12.1 , Така:

Adj (v) 1: 6 2: 1, 3, 4, 6 3: 4, 5 4: 5 5: 3, 6, 7 6: 7: 1, 6

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

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

Матриця інцидентності - задає граф: , Якщо ребро виходить з вершини , , Якщо ребро входить в вершину , і в інших випадках.

Можливості підключення і відстань

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

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

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

Іноді недостатньо знати, що граф зв'язний; нас може цікавити, наскільки "сильно зв'язний" зв'язний граф. Наприклад, зв'язний граф може містити вершину, видалення якої разом з інцидентними їй ребрами роз'єднує решта вершини. Така вершина називається точкою зчленування або розділяє вершиною. Граф, що містить точку зчленування, називається разделімого. Граф без точок зчленування називається двусвязного або нероздільним. Максимальний двусвязний підграф графа називається двусвязного компонентою або блоком.

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