Графи дорожніх мереж та алгоритми роботи з ними. Математична модель

Твердження. Якщо для двох вершин існує маршрут, що їх пов'язує, то обов'язково знайдеться мінімальний маршрут, що з'єднує ці вершини. Позначимо довжину цього маршруту черезd(v,w).

Визначення. Величинуd(v,w) (кінцеву або нескінченну) називатимемо відстанню між вершинами v, w . Ця відстань задовольняє аксіомам метрики:

1) d(v,w) 0, причомуd(v,w) = 0 тоді і лише тоді, колиv=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Визначення. Діаметромзв'язкового графа називається максимально можлива відстань між двома його вершинами.

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

Приклад 82.

Для графа G, зображеного на рис. 3.16, знайти радіус, діаметр та центри.

Мал. 3.16. Граф для прикладу 82

Рішення.

Щоб визначити центри, радіус, діаметр графа G, знайдемо матрицю D(G)відстаней між вершинами графа, елементами d ijякою будуть відстані між вершинами v iі v j. Для цього скористаємося графічним поданнямграфа. Зауважимо, що матриця D(G)симетрична щодо головної діагоналі.

За допомогою отриманої матриці для кожної вершини графа Gвизначимо найбільше видалення з виразу: для i,j = 1, 2, …, 5. В результаті отримуємо: r(v 1) = 3,r(v 2) = 2,r(v 3) = 2,r(v 4) = 2,r(v 5) = 3.Мінімальне з одержаних чисел є радіусом графа Gмаксимальне – діаметром графа G. Значить, R(G) = 2і D(G) = 3, центрами є вершини v 2 ,v 3 ,v 4.

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

Ексцентриситетвершини графа - відстань до максимально віддаленої від неї вершини. Для графа, для якого не визначено вага його ребер, відстань визначається як числа ребер.

Радіусграфа – мінімальний ексцентриситет вершин, а діаметр графа – максимальний ексцентриситет вершин.

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

Периферійнівершини мають ексцентриситет, рівний діаметру.

Простий ланцюг з довжиною, що дорівнює діаметру графа, називається діаметральної .

Теорема 12.1.У зв'язному графі діаметр не більший за ранг його матриці суміжності.

Теорема 12.2.(Жордана) Кожне дерево має центр, що складається з однієї чи двох суміжних вершин.

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

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

Приклад 12.5.Знайти радіус, діаметр та центр графа, зображеного на рис. 12.1.

Рішення.У цій задачі зручно використовувати матрицю відстаней S. Елемент цієї квадратної симетричної матриці дорівнює відстаніміж вершиною iі вершиною j. Для графа показаного на рис. 12.1 матриця відстаней має наступний вигляд:

Обчислимо ексцентриситет кожної вершини. Цю величину можна визначити як максимальний елемент відповідного стовпця матриці відстаней (або рядки – оскільки матриця Sсиметрична). Отримуємо

Радіус графа r- Мінімальний ексцентриситет вершин. У даному випадку r= 2. Такий ексцентриситет мають вершини №2, №4 та №5. Ці вершини утворюють центр графа. Діаметр графа d– максимальний ексцентриситет вершин. В даному випадку d= 3. Такий ексцентриситет мають вершини №1 та №3, це периферія графа. У дослідженому графі вершини виявилися центральними, або периферійними. У графах більшого порядку є й інші вершини.

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

Теорема 12.4. Нехай - матриця суміжності графа G без петель і де . Тоді дорівнює числу маршрутів довжини k від вершини до вершини.

Розв'язання задач теорії графів за допомогою різних перетворень матриці суміжності називають методом алгебри .

Приклад 12.6.Знайти матрицю відстаней графа, зображеного на рис. 12.1, методом алгебри.

Рішення.Матриця суміжності даного графа дорівнює:

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

Діагональні елементи матриці відстаней – нулі. Помножуємо матрицю суміжності він:

Згідно з теоремою між вершинами 2 і 3, 1 і 4 і т.д. є кілька маршрутів довжиною 2 (оскільки ступінь матриці дорівнює двом). Число маршрутів тут не використовується, важливий сам факт наявності маршруту та його довжина, на що і вказує ненульовий елемент ступеня матриці, що не збігається з елементом, зазначеним при обчисленні маршруту меншої довжини. Проставляємо 2 незаповнені елементи матриці відстаней і отримуємо наступне наближення:

Залишилася невідомою відстань між вершинами 1 і 3. Помножуватимемо матрицю суміжності саму на себе доти, доки в матриці не з'явиться ненульовий елемент . Тоді відповідний елемент матриці відстаней дорівнює ступенюматриці суміжності: . На наступному кроці отримуємо

отже, , та остаточно

Отримана матриця збігається з матрицею відстаней S(12.2), знайденої безпосередніми обчисленнями на малюнку.

Нехай G(V,X) – псевдограф і нехай вершини v та w (v¹w) даного графа можна з'єднати маршрутом. Тоді обов'язково існує і мінімальний маршрут, який з'єднує ці вершини. Позначимо довжину цього маршруту d(v, w). Покладемо також d(v, v) =0 для будь-якої вершини vV; d(v, w) = ¥, якщо не існує маршруту, що з'єднує v та w.

Визначена таким чином величина d(v,w) для будь-яких вершин v і w графа G(V, X) називається відстанню між v і w.

Число відстаней у графі з n вершинами дорівнює числу поєднань C n 2 .

Нехай граф G(V,X) зв'язковий. Визначимо йому такі поняття:

Діаметр графа: d(G) = maxd(v, w).

Ексцентриситет (максимальне видалення) вершини: r(v) = maxd(v, w);

Радіус графа: r(G) = min r(v);

Центр графа: будь-яка вершина vÎV, така, що r(v) = r(G).

Діаметр графа, ексцентриситети вершин, радіус графа та центри графа називаються метричними характеристиками графа.

приклад. Знайти метричні характеристикиграфа, заданого діаграмою:

Знайдемо всі відстані, враховуючи, що d(v, w) = d(w, v).

Число відстаней у даному графі З 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, d(v 4 , v 5) = 1.

Діаметр графа d(G) =3.

Ексцентриситети вершин: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Радіус графа r(G) = 2.

Центри графа v2, v3, v4.

3. Мінімальні маршрути у навантажених графах

Граф G(V, X) називається навантаженим, якщо на множині ребер графа задана функція, звана ваговою, яка ставить у відповідність кожному ребру х ÎХ графа деяке число l(x). Значення l(x) називається довжиною дуги.

Величині l(x) можна надати різний сенс: витрати на транспортування, час проїзду, відстань між пунктами, витрата бензину та ін.

Сума довжин ребер, що входять до маршруту, називається довжиною маршруту.

Зауважимо, якщо для всіх х Î Х l(x) = 1, то граф можна розглядати як ненавантажений.

Маршрут у графі G(V, X) з вершини v до вершини w (v¹w) називається мінімальним, якщо він має мінімальну довжину серед усіх маршрутів у графі G(V, X) з вершини v до вершини w.

Обмежимося графами, котрим l(x)>0.

Під час пошуку мінімального маршруту в навантаженому графі з l(x)>0

скористаємося таким самим твердженням, що й для ненавантаженого графа, а саме:

будь-який мінімальний маршрут є простим ланцюгом.

Розглянемо тепер завдання пошуку мінімального маршруту у навантаженому графі.

Нехай граф G(V,X) навантажений, число вершин n ³ 2, необхідно побудувати мінімальний маршрут з v 1 до v n .

Наведемо алгоритм.

Крок 1. Кожній вершині присвоїти індекс a(vi): a(v 1) = 0, a(vi) = ¥, i ¹ 1. пофарбувати вершину v 1 і покласти v = v 1 .

Крок 2. Для кожної незабарвленої вершини v j змінити індекс за правилом:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Пофарбувати ту з вершин, для якої a(v j) виявиться найменшим.. пофарбувати також ребро, що веде до обраної даному кроцівершину v j. Покласти v = v j.

Крок 3. Якщо v = v j , закінчити процедуру, оскільки найкоротший маршрут з v 1 до v n . якщо v ¹ v n , перейти до кроку 2.

Зауваження. Крок 2 неможливий, якщо a(v j)= ¥. І тут вершина v n недосяжна.

Застосуємо викладений алгоритм до заданого діаграмою графу. Знайдемо у ньому найкоротший маршрут з v 1 до v 6 .

Крок 1. Пофарбуємо вершину v1. Надамо вершин індекси: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Вважаємо v 1 = v.

a(v 2) = min (¥, 0+4) = 4,

a(v 3) = min (¥, 0+7) = 7,

a(v 4) = min (¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

Фарбуємо вершину v 4 і ребро (v 1, v 4).

Крок 3. Оскільки вершина v 6 не забарвлена, виконуємо крок 2, вважаючи v = v 4 .

a(v 2) = min (4, 3+¥) = 4,

a(v 3) = min (7, 3+¥) = 7,

a(v 5) = min (¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

Фарбуємо вершину v 2 і ребро (v 1, v 2).

Крок 3. Оскільки вершина v 6 не забарвлена, виконуємо крок 2, вважаючи v = v 2 .

a(v 3) = min (7, 4+3) = 7,

a(v 5) = min (6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

Фарбуємо вершину v 5 і ребро (v 4, v 5).

Крок 3. Оскільки вершина v 6 не забарвлена, виконуємо крок 2, вважаючи v = v 5 .

a(v 3) = min (7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

Фарбуємо вершину v 3 і ребро (v 1, v 3).

Крок 3. Оскільки вершина v 6 не забарвлена, виконуємо крок 2, вважаючи v = v 3 .

a(v 6) = min (8, 7+2) = 8.

Фарбуємо вершину v 6 і ребро (v 5, v 6).

Так як вершина v 6 пофарбована, роботу припиняємо. Отримали мінімальний маршрут v 1 v 4 v 5 v 6 , довжина якого дорівнює 8 .

Зауважимо, що це у разі не єдиний для вершин v 1 і v 6 мінімальний маршрут, т.к. в алгоритмі була можливість пофарбувати замість ребра (v 4, v 5) ребро (v 2, v 5), тоді отримали інший маршрут тієї ж довжини.

4. Завдання на деревах

Ациклічним називається граф, у якому відсутні цикли.

Граф без циклів називається лісом.

Дерево – це зв'язковий ациклічний граф.

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

Периферійнівершини мають ексцентриситет, рівний діаметру.

Простий ланцюг з довжиною, що дорівнює діаметру графа, називається діаметральної .

Теорема 12.1.У зв'язному графі діаметр не більший за ранг його матриці суміжності.

Теорема 12.2.(Жордана) Кожне дерево має центр, що складається з однієї чи двох суміжних вершин.

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

Приклад 12.5.Знайти радіус, діаметр та центр графа, зображеного на рис. 12.1.

Рішення.У цій задачі зручно використовувати матрицю відстаней S. Елемент цієї квадратної симетричної матриці дорівнює відстані між вершиною iі вершиною j. Для графа показаного на рис. 12.1, матриця відстаней має такий вигляд:

. (12.2)

№

Радіус графа r- Мінімальний ексцентриситет вершин. В даному випадку r= 2. Такий ексцентриситет мають вершини №2, №4 та №5. Ці вершини утворюють центр графа. Діаметр графа d– максимальний ексцентриситет вершин. В даному випадку d= 3. Такий ексцентриситет мають вершини №1 та №3, це периферія графа. У дослідженому графі вершини виявилися центральними, або периферійними. У графах більшого порядку є й інші вершини.

Приклад 12.6.Знайти матрицю відстаней графа, зображеного на рис. 12.1, методом алгебри.

Рішення.Матриця суміжності даного графа дорівнює:

Діагональні елементи матриці відстаней – нулі. Помножуємо матрицю суміжності він:

Залишилася невідомою відстань між вершинами 1 і 3. Помножуватимемо матрицю суміжності саму на себе доти, доки в матриці не з'явиться ненульовий елемент . Тоді відповідний елемент матриці відстаней дорівнює ступеню матриці суміжності: . На наступному кроці отримуємо