тованому графі ставлення суміжності несиметрично).
Шляхом з вершини u в вершину v довжиною k ребер називають послідовність ребер графа. Часто той же шлях позначають послідовністю вершин. Якщо для даних вершин u , v існує шлях з u в v , то говорять, що вершина v досяжна з u . Шлях називається простим , якщо всі вершини в ньому різні. Циклом називається шлях, у якому початкова вершина збігається з кінцевою. При цьому цикли, що відрізняються лише номером початкової точки, ототожнюються.
Граф називається пов'язаним , якщо для будь-якої пари його вершин існує шлях з однієї вершини в іншу.
Якщо кожному ребру графа приписано якесь число ( вага ), то граф називають зваженим .
При програмуванні вершини графа зазвичай зіставляють числах від 1 до N , де - кількість вершин графа, і розглядають. Ребра Нумер числами від 1 до M , де. Для зберігання графа в програмі можна застосувати різні методи. Найпростішим є зберігання матриці суміжності , тобто двовимірного масиву, скажімо A , де для незваженого графа (або 1), якщо і (або 0) в іншому випадку. Для зваженого графа A [ i ] [ j ] дорівнює вазі відповідного ребра, а відсутність ребра в ряді завдань зручно позначати нескінченністю. Для неорієнтованих графів матриця суміжності завжди симетрична щодо головної діагоналі ( i = j ). C допомогою матриці суміжності легко перевірити, чи існує в графі ребро, з'єднує вершину i з вершиною j . Основною ж її недолік полягає в тому, що матриця суміжності вимагає, щоб обсяг пам'яті пам'яті був достатній для зберігання N 2 значень, навіть якщо ребер в графі істотно менше, ніж N 2 . Це не дозволяє побудувати алгоритм з часом порядку O ( N ) для графів, що мають O ( N ) ребер.
Цього недоліку позбавлені такі способи зберігання графа, як одновимірний масив довжини N списків або множин вершин. У такому масиві кожен елемент відповідає одній з вершин і містить список або безліч вершин, суміжних їй.
Для реалізації деяких алгоритмів більш зручним є опис графа шляхом перерахування його ребер. У цьому випадку зберігати його можна в одновимірному масиві довжиною M , кожен елемент якого містить запис про номери початкової та кінцевої вершин ребра, а також його вазі у разі зваженого графа.
Нарешті, при вирішенні задач на графах, в тому числі і за допомогою комп'ютера, часто використовується його графічне представлення. Вершини графа зображують на площині у вигляді точок або маленьких гуртків, а ребра - у вигляді ліній (не обов'язково прямих), з'єднують відповідні пари вершин, для неорієнтованого графа і стрілок - Для орієнтованого (якщо ребро спрямовано з u в v , то з точки, що зображує вершину u , проводять стрілку у вершину v ).
Графи широко використовуються в різних галузях науки (в тому числі в історії!) і техніки для моделювання відносин між об'єктами. Об'єкти відповідають вершинам графа, а ребра - відносинам між об'єктами). Детальніше про цю структуру даних можна прочитати в [5 - 7].
3. Пошук шляху між парою вершин незваженого графа
Нехай ми маємо довільний граф, орієнтований або неорієнтоване. Якщо в невиважені графі існує шлях, то назвемо довжиною шляху кількість ребер в ньому. Якщо шляху немає взагалі, то відстань вважається нескінченним. Шлях мінімальної довжини при цьому називається найкоротшим шляхом у графі. Легко показати, що будь-які частини найкоротшого шляху також є найкоротшими шляхами між відповідними вершинами. Адже якщо це не так, тобто існує відрізок найкоротшого шляху, між кінцями якого можна побудувати більш короткий шлях, то ми можемо замінити цей відрізок найкоротшого шляху між вершинами u і v на коротший, тим самим зменшивши і довжину найкоротшого шляху між u і v , що неможливо. Це властивість найкоротших шляхів дозволяє вирішувати задачу їх знаходження методом динамічного програмування. Покажемо спочатку як можна записати "хвильової алгоритм" так, що завдання пошуку найкоротшого шляху між двома вершинами графа вирішуватиметься за O ( N 2 ) дій.
Задача 12 . Для ліній метрополітену деякого міста відомо, між якими парами ліній є пересадочна станція. Необхідно визначити, за скільки пересадок можна дістатися з лінії m на лінію n або повідомити, що зробити це неможливо.
Рішення. Такий метрополітен зручно описувати за допомогою графа, вершини якого є лінії метрополітену (а не станції!), а наявність ребра між вершинами i і j графа відповідає наявності пересадково...
