Математична модель. Алгоритм виділення компонент сильної зв'язності

Нехай 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. Завдання на деревах

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

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

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

У минулому параграфі ми підкреслили, що введена там матриця суміжності $A$, точніше матриця вершинної суміжності графа, дуже грає істотну рольтеоретично графів. Ми відзначили як переваги цієї матриці - вона квадратна порядку, рівного числарядків матриці інцидентності $B$, тобто, як правило, містить менша кількістьелементів. По-друге, ця матриця зберігає всю інформацію про ребрах графа і при заданій нумерації вершин однозначно описує граф. Матриця суміжності, як і матриця інцидентності графа є (0,1)-матрицею, тобто. її елементи можна як елементи інших алгебраїчних структур, ніж як елементи безлічі цілих чисел. Зокрема, ми зазначили, що елементи матриці суміжності можуть розглядатися як елементи булевої алгебри, підпорядковані законам булевої арифметики, але не пояснили це належним чином. Перш ніж заповнити цю прогалину, підкреслимо переваги матриці суміжності, які з її квадратності.

Для цього нагадаємо правила множення матриць. Нехай дані довільні матриці з числовими елементами: матриця $A$ розмірності $n\times m$ з елементами $a_(ik)$ і матриця $B$ розмірності $m\times q$ з елементами $b_(kj)$. Матриця $C$ розмірності $n\times q$ називається добутком матриці $A$ на $B$ (порядок важливий), якщо її елементи $c_(ij)$ визначаються так: $c_(ij) = \sum\limits_( k = 1)^m (a_(ik) b_(kj))$. Твір матриць записується зазвичай $AB=C$. Як бачимо, добуток матриць вимагає узгодженості розмірів першого та другого співмножників (число стовпців першої матриці-співмножника дорівнює числу рядків другої матриці-співмножника). Ця вимога відпадає, якщо розглядати квадратні матриці одного порядку і, отже, можна розглядати довільні ступені квадратної матриці. Це одна з переваг квадратних матриць перед прямокутними. Інша перевага у тому, що ми можемо дати графову інтерпретацію елементам ступенів матриці суміжності.

Нехай матриця суміжності $A$ має вигляд: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & (a_(1n) ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(array) )) \right)$, а її $ k$-а ступінь - $A^k = \left(((\begin(array)(*c) (a_(11)^((k)) ) & (a_(12)^((k)) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & (.. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^(( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(array) )) \right)$, де $k = 2,3,...$ Очевидно, що $A^k$, як і матриця $A$ буде симетричною матрицею.

Нехай $k = 2 $. Тоді $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), і кожен доданок $a_(il) a_(lj)$ дорівнює або $0$, або $1$. Випадок, коли $a_(il) a_(lj) = 1$ означає, що у графі існують два ребра: ребро $\(i,l\)$ (оскільки $a_(il) = 1)$ і ребро $\( l,j\)$ (оскільки $a_(lj) = 1$) і, отже, шлях $\(( \(i,l\), \(l,j\) )\)$ з $i$- ой вершини в $j$-у довжиною два (шлях із двох ребер). Тут мова йдесаме про шлях, а не ланцюги, оскільки зазначений напрямок — із $i$-ої вершини до $j$-ої. Таким чином, $a_(ij)^((2))$ дає нам кількість всіх шляхів на графі (в геометричній інтерпретації графа) довжини 2, що ведуть з $i$-ої вершини в $j$-у.

Якщо $k=3$, то $A^3 = A^2A = AA^2 = AAA$ і $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_(l_1 l_2 ) a_(l_2 j) ) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

Доданок $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $ якщо воно дорівнює 1, визначає шлях довжини 3 що йде з $i$-ої вершини в $j$-у і проходить через вершини $l_1$ і $l_2$. Тоді $a_(ij)^((3))$ дає нам кількість шляхів довжини 3, що з'єднують $i$-у і $j$-у вершини. У загальному випадку$a_(ij)^((k))$ задає кількість шляхів довжини $k$, що з'єднують $i$-у і $j$-у вершини. У цьому $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

Зрозуміло, що $a_(ii)^((k)) $ дає нам кількість замкнутих шляхів довжини $k$, що починаються і закінчуються у вершині $i$. Так, шлях довжини 2 — $a_(il) a_(li)$, означає шлях, що проходить ребром $\( i,l \)$ з вершини $i$ у вершину $l$ і назад. Тому $a_(ii)^((2)) = s_i$, тобто. діагональні елементи матриці $A^2$ дорівнюють ступеням відповідних вершин.

Розглянемо тепер поряд із матрицею $A$ матрицю $\dot(A)$, яка відрізняється від матриці $A$ тільки тим, що в неї елементи (числа 0 або 1) розглядаються як елементи булевої алгебри. Тому дії з такими матрицями будуть проводитись за правилами булевої алгебри. Оскільки дії складання та множення матриць з булевими елементами зводиться до дій складання та множення елементів цих матриць за правилами булевої арифметики, то, сподіваємося, що це не призведе до труднощів. Матрицю з булевими елементами називатимемо булевою матрицею. Вочевидь, що операції додавання і множення булевих матриць замкнуті на безлічі булевих матриць, тобто. результат цих операцій буде знову булевою матрицею.

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

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

Проінтерпретуємо тепер другий ступінь булевої матриці суміжності $\dot(A)^2$ з елементами $\dot(a)_(ij)^((2)) = \sum\limits_(l = 1)^n (\dot ( a)_(il) \dot (a)_(lj) )$. Ясно, що $\dot(a)_(ij)^((2)) = 1$, якщо хоча б один доданок $\dot(a)_(il) \dot(a)_(lj) $ дорівнює 1 і $\dot(a)_(ij)^((2)) = 0$, якщо всі доданки дорівнюють 0. Якщо матриця $\dot(A)$ є матрицею суміжності деякого графа, тобто. є симетричною (0,1)-матрицею з нульовою головною діагоналлю, то матриця $ \ dot (A) ^ 2 $, взагалі кажучи, не є матрицею суміжності графа в прийнятому нами сенсі, оскільки у неї всі діагональні елементи рівні 1 (якщо у графа немає ізольованих вершин). Щоб і на такі матриці можна було дивитися як на матриці суміжності, ми повинні при розгляді зв'язків між вершинами певної зв'язаної системи, що визначають цю систему як граф, допустити зв'язок деяких вершин самих із собою. «Ребро», що визначає зв'язок деякої вершини самої із собою називається петлею. Ми далі, як і раніше, під словом граф розумітимемо граф без петель, а про граф із петлями, якщо це не буде ясно з контексту, так і говоритимемо — граф із петлями.

Розглянемо суму $\dot(A)^() = \dot(A) + \dot(A)^2$. Матриця $\dot (A)^()$ задає нам граф, отриманий з вихідного «насиченням» його додатковими зв'язками, що відповідають шляхам довжини 2. Тобто в новому графі вершини $i$ і $j$ суміжні, якщо вони суміжні у вихідному графі або ці вершини пов'язані яким-небудь шляхом довжини 2, і вершини $i$ і $j$ несуміжні, якщо вони несуміжні у вихідному графі і немає ніякого шляху довжини 2, що з'єднує ці вершини.

Аналогічно визначається $ dot (A) ^ () = \ dot (A) + \ dot (A) ^ 2 + \ dot (A) ^ 3 $. Тобто у графі, заданим матрицею$\dot (A)^()$ вершини $i$ і $j$ суміжні, якщо вони суміжні у графі $\dot (A)^()$ або ці вершини пов'язані яким-небудь шляхом довжини 3 у вихідному графі, і вершини $i$ і $j$ несуміжні, якщо вони несумежні у графі $\dot (A)^()$ і немає ніякого шляху довжини 3, що зв'язують ці вершини у вихідному графі. І так далі.

У загальному випадку $\dot(A)^([k]) = \sum\limits_(i = 1)^k (\dot(A)^i) $. Неважко бачити, що $\dot (A)^([k])$ при $k \ge n - 1$, де $n$ - порядок матриці $\dot (A)$, рівні між собою. Дійсно, якщо вершини $i$ і $j$ зв'язні, то існує шлях (ланцюг), що зв'язує ці вершини, а, отже, існує простий шлях (простий ланцюг), що зв'язує ці вершини. Максимальний можливий простий ланцюг у $n$-вершинному графі має довжину $n-1$ (простий ланцюг, що зв'язує всі різні вершини графа). Тому, якщо в матриці $\dot(A)^()$ на місці $(i,j)$ стоїть 1, то на цьому ж місці в матриці $\dot(A)^([k])$ при $k \ge n - 1$ буде стояти 1, оскільки матриця $\dot (A)^()$ входить як бульова доданку визначення матриці $\dot (A)^([k])$. Якщо ж у матриці $\dot(A)^()$ на місці $(i,j)$ стоїть 0, то це означає, що у графі не існує ніякого простого ланцюга, що з'єднує $i$-у та $j$- ну вершини, а, отже, не існує взагалі ніякого ланцюга, що зв'язує ці вершини. Отже, в даному випадку і в матриці $\dot (A)^([k])$ при $k \ge n - 1$ на місці ($i$,$j)$ стоятиме 0. Що і доводить наше твердження про рівність всіх матриць $\dot(A)^([k])$ при $k \ge n - 1$ матриці $\dot(A)^()$ і, отже, між собою.

Матрицю $\dot (A)^()$ називають матрицею транзитивного замикання матриці$\dot(A)$, а також матрицею суміжності транзитивного замикання графа, заданого матрицею $\dot(A)$. Досить очевидно, що матрицею транзитивного замикання зв'язкового графа буде матриця суміжності повного графа, тобто. квадратна матриця, Що складається з одних одиниць. Це спостереження дає і метод визначення зв'язності графа: граф зв'язний тоді і лише тоді, коли матриця транзитивного замикання його матриці суміжності складатиметься з одних одиниць (буде матрицею повного графа).

Матриця транзитивного замикання дозволяє вирішувати завдання розбиття графа на компоненти зв'язності.

Покажемо тепер як процедура транзитивного замикання дозволяє побудувати так звану «матрицю відстаней». Для цього визначимо відстань між вершинами $i$ та $j$. Якщо вершини $i$ і $j$ зв'язкові, то відстаннюміж ними назвемо довжину мінімального (за кількістю обходу ребер) простого шляху, що зв'язує ці вершини; якщо вершини $i$ і $j$ незв'язні, то покладемо відстань рівним нулю (нуль як заперечення будь-якого шляху, що зв'язує ці вершини). При такому визначенні відстані відстань між вершиною і нею самою дорівнює 2 (довжина шляху по ребру і назад). Якщо ж при вершині є петля, то відстань між вершиною і нею самою дорівнює 1.

Для побудови матриці відстаней для $n$-вершинного графа з матрицею суміжності $A$, яка вказувала б відстань між будь-якими двома вершинами, введемо до розгляду матриці $A^(\(k\)) = A^([k]) - A^()$, де $k = 2,3,...,n - 1$ і $A^(\(1\)) = A^() = A$. Відсутність точок над позначенням матриць показує, що ми розглядаємо матриці $A^([k])$ ($k = 1,2,...,n - 1)$ як числові (0,1)-матриці, які природно одержуються з матриць $ \ dot (A) ^ ([k]) $ (булеві елементи 0 і 1 ми тепер розглядаємо як числа 0 і 1). З способу побудови матриць $A^([k])$ слід, що $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$) і, отже, $A^(\(k\))$ ($k = 1,2,...,n - 1$) є (0,1)-матрицями. Причому матриця $A^(\(2\))$ містить 1 тільки тих місцях, де зумовлені цим місцем (номер рядка і номер стовпця) вершини з'єднані деяким шляхом довжини два і не з'єднані меншим шляхом. Аналогічно, $A^(\(3\))$ містить 1 тільки на тих місцях, де зумовлені цим місцем вершини з'єднані шляхом довжини три і не з'єднані жодним шляхом меншої довжини, і т.д. Таким чином, матриця $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ і буде шуканою матрицею відстаней. Елемент $d_(ij)$ цієї матриці і буде дорівнює відстаніміж вершинами $i$ та $j$. Відстань між вершинами $u$ і $v$ також позначатимемо як $d(u,v)$.

Зауваження.Конкретний твір-складник $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ елемента $a_(ij )^((k))$ $k$-ого ступеня матриці суміжності $A^k$ задає конкретний $(i,j)$-шлях $i\(i,l_1\)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ з $i$ -ої вершини в $j$-у. Послідовність суміжних вершин і ребер, що їх з'єднують $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ називають ще $(i,j)$-маршрутом. Маршрут відрізняється від ланцюга, що складається лише з різних суміжних ребер, ще тим, що у маршруті допускаються рівні ребра. Простий маршрут складається із різних суміжних вершин і ребер, тобто. практично збігається із простим ланцюгом.

Досить очевидно, що елемент $d_(ij) $ матриці відстаней визначає довжину мінімального ланцюга, що з'єднує $i$-у вершину з $j$-ою.

Розглянемо приклади графів, заданих малюнками 1 і 2, їх матриць суміжності та їх матриць відстаней.

Рис.1 (Граф $ \ Gamma _1 $, матриця суміжності $ A_1 $, матриця відстаней $ D_1 $).
$A_1 = \left(((\begin(array)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1&0&0&0&0&0&0&0&0&0&0&0\\1&1&0&1&1&0&0&0&0&0&1&0&0&1\\1& 1&1&0&0&0&0&0&0&0&0&0&0&0&0&0 \\0&0&1&0&0&1&1&1&0&1&0&0&1 \\0&0&0&0&0&1&0&1&1&0&0&0&0&0&0 \\0&0&0&0&0&1&1&0&1&0&0&0&0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(array) )) \right), $
$D_1 = \left(((\begin(array)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1&1&2&2&3&3&3&3&3&2&3&3&2 \\ 2&2&1&2&2&1&1&1&2&1&2&2&1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(array) )) \right) $

Рис. 2 (Граф $\Gamma _2$, матриця суміжності $A_2$, матриця відстаней $D_2$).
$A_2 = \left(((\begin(array)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \ \0&0&0&0&1&0&1&0&0&0&0&0\\0&0&0&0&0&1&0&1&0&0&0\\0&0&0&0&0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \endend (array) )) \right)$,
$D_2 = \left(((\begin(array)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \end(array) )) \right). $

За матрицями $D_1$ та $D_2$ легко визначаються діаметри$d_1$ графа $\Gamma _1$ і $d_2$ графа $\Gamma _2$ як максимальні значення елементів цих матриць. Так $d_1 = 3 $, а $ d_2 = 6 $.

Крім матриці відстаней, теорія графів розглядає й інші матриці, елементи яких визначаються через довжину шляху. Такий, наприклад, є матриця обходів. У матриці обходів$(i,j)$-й елемент дорівнює довжинінайдовшого шляху (найдовшого ланцюга) з $i$-ої вершини в $j$-у, а якщо таких шляхів немає взагалі, то відповідно до визначення відстані $(i,j)$-ий елемент матриці обходів вважається рівним нулю .

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

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

Ексцентриситет$e(v)$ вершини $v$ у зв'язному графі $\Gamma$ визначається як max $d(u,v)$ по всіх вершинах $u$ у $\Gamma$. Радіусом$r(\Gamma)$ називається найменший з ексцентриситетів вершин. Зауважимо, що найбільший із ексцентриситетів дорівнює діаметру графа. Вершина $v$ називається центральною вершиною графа $\Gamma$, якщо $e(v) = r(\Gamma)$; центрграфа $ Gamma - безліч всіх центральних вершин.

Так для графа $ \ Gamma _1 $ з рис.1, ексцентриситет вершини 13 дорівнюватиме 2 ($ e (13) = 2 $). Такі ж ексцентриситети матимуть вершини 3, 5 та 10 ($e(3) = e(5) = e(10) = 2$). Ексцентриситет дорівнює 2 буде найменшим для графа $ Gamma _1 $, тобто. $ r (\ Gamma _1) = 2 $. Центр графа $\Gamma _1$ складатиметься з вершин 3, 5, 10 і 13. Найбільший ексцентриситет дорівнюватиме 3 і дорівнюватиме, як зазначалося вище, діаметру графа $\Gamma _1$.

Для графа $ \ Gamma _2 $ з рис. 2 найменший ексцентриситет матиме єдина вершина 4 ($e(4) = r(\Gamma _2) = 3$). Отже, центр графа $Gamma _2$ складається з однієї вершини 4. Діаметр графа $\Gamma _2$, як зазначалося вище, дорівнює 6.

Граф $\Gamma _2$ є деревом, а структуру центру будь-якого дерева описує теорема, що наводиться нижче.

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

Доведення.Позначимо через $K_1$ граф, що з однієї ізольованої вершини, а через $K_2$ — граф — із двох вершин з'єднаних рубом. За визначенням покладемо $ e (K_1) = r (K_1) = 0 $. Тоді затвердження теореми буде виконано $K_1$ і $K_2$. Покажемо, що у будь-якого дерева $T$ ті ж центральні вершини, що й у дерева $(T)"$, отриманого з $T$ видаленням всіх його висячих вершин. Зрозуміло, що відстань від даної вершини $u$ до будь-якої іншої вершини $v$ може досягати найбільшого значеннятільки тоді, коли $v$ - висяча вершина.

Таким чином, ексцентриситет кожної вершини дерева $(T)"$ точно на одиницю менше ексцентриситету цієї ж вершини $T$. Звідси випливає, що вершини дерева $T$, що мають найменший ексцентриситет $T$, збігаються з вершинами, що мають найменший ексцентриситет $(T)"$, тобто. центри дерев $T$ і $(T)"$ збігаються. Якщо процес видалення висячих вершин продовжити, то ми отримаємо послідовність дерев з тим же центром, що й у $T$. В силу кінцівки $T$ ми обов'язково прийдемо або до $ K_1$, або до $K_2$ У будь-якому випадку всі вершини дерева отриманого таким способом утворюють центр дерева, який, таким чином, складається або з єдиної вершини, або з двох суміжних вершин.

Покажемо тепер, як за допомогою матриці відстаней можна визначити, наприклад, мінімальний ланцюг, що з'єднує вершину 4 з вершиною 8 на графі $Gamma _1$. У матриці $ D_1 $ елемент $ d_ (48) = 3 $. Візьмемо 8-й стовпець матриці $D_1$ і знайдемо у стовпці всі елементи цього стовпця рівні 1. Принаймні, один такий елемент знайдеться через зв'язність графа $D_1$. Насправді таких одиниць у 8-му стовпці буде три, і розташовані вони в 5-му, 6-му та 7-му рядках. Візьмемо тепер 4-й рядок і розглянемо в ньому елементи, розташовані в 5-му, 6-му та 7-му стовпцях. Ці елементи будуть 2, 3 та 3 відповідно. Тільки елемент, розташований у 5-му стовпці дорівнює 2 і разом з 1, розташованої на місці (5,8), дає суму 3. Значить, вершина 5 входить у ланцюг $\(\(4,?\), \(?) ,5 \), \ (5,8 \) \) $. Візьмемо тепер 5-ий стовпець матриці і розглянемо 1 цього стовпця. Це будуть елементи розташовані в 3-му, 6-му, 7-му, 8-му, 10-му та 13-му рядках. Знову повертаємося до 4-го рядка і бачимо, що тільки на перетині третього стовпця і 4-го рядка стоїть 1, що в поєднанні з 1 на місці (3,5) дає в сумі 2. Отже, ланцюг буде шуканий $\( \ (4,3), (3,5), (5,8) $). Подивившись тепер на рисунок 1, переконуємось у справедливості знайденого рішення.

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

Нехай G- Кінцевий н-граф.

Маршрутомв Gназивається послідовність ребер, в якій кожні два сусідні ребра мають загальну вершину:

Число ребер у маршруті називається його довжиною.

Маршрут М називається маршрутом загального вигляду ланцюгом простим ланцюгом – якщо його вершини не повторюються,

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

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

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

Вершини і називаються зв'язковими , якщо існує маршрут з початком у і кінцем у .

Твердження:Відношення зв'язності вершин графа є ставленням еквівалентності і визначає розбиття безлічі вершин графа на підмножини, що не перетинаються. .

Граф називається зв'язковим якщо для будь-яких двох різних вершин існує маршрут, що з'єднує їх.

Очевидно, що всі підграфи G(V i) цього графа зв'язкові і називаються зв'язковими компонентами графа.

Відстаньміж вершинами a і b називається довжина мінімального простого ланцюга, що зв'язує їх. Відстань позначається d(a, b) .

Аксіоми метрики:

1) d(a, b) =d(b,a);

2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;

3) d(a, b) ≤ d(a, c) + d(c, b)

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

			…
			…
			…
…	…	…	…	…	…
			…

В останньому стовпці матриці вказано ексцентриситет для кожної вершини: відстань від цієї вершини до найвіддаленішої вершини.

. (7.1)

Діаметрграфа G – максимальна відстаньміж вершинами графа. Діаметр знаходиться за формулою:

.

Використовуючи знайдені ексцентриситети вершин, діаметр можна знайти за формулою:

. (7.2)

Радіусграфа G – мінімальне значенняексцентриситету. Радіус знаходиться за формулою:

. (7.3)

Центрграфа G- Така вершина, для якої .

Зауваження.Центр у графі може бути не єдиним.

Діаметральний ланцюгграфа G діаметру,що з'єднує найбільш віддалені вершини графа.

Радіальний ланцюгграфа G– простий ланцюг, довжина якого дорівнює радіусу,що з'єднує центр і найбільш віддалену від нього вершину графа.

Приклад 7.1.

Для н-графа, наведеного малюнку 7.1, записати 1) маршрут загального виду, 2) не простий ланцюг, 3) простий ланцюг, 4) циклічний маршрут загального виду,5) не простий цикл, 6) простий цикл.

Рішення:

1) Маршрут загального виду – це маршрут, у якому початкова і кінцева вершина різні, і деякі ребра повторюються. М 1 = (1, 4 , 5, 1, 4 7, 3). Тут повторюється ребро (1, 4).

2) Не простий ланцюг – це маршрут, у якому не повторюються ребра, але повторюються вершини. М 2 = (4, 3, 1 , 5, 6, 7 , 4, 1 ). Тут повторюється вершина 1.

3) Проста ланцюг – це маршрут, у якому повторюються вершини. М 3 = (4, 3, 7, 5, 6).

4) Циклічний маршрут загального виду – це маршрут, у якому початкова і кінцева вершини збігаються, і ребра повторюються. М 4 = (1, 5 , 1, 5 , 1 ). Тут повторюється ребро (1, 5).

Малюнок 7.1. Побудова маршрутів

в неорієнтованому графі

5) Непростий цикл – це циклічний маршрут, у якому повторюються ребра, але повторюються вершини. М 5 = (3, 4 , 5, 7, 4 1, 3). Тут повторюється вершина 4.

Зауважимо,що непростий цикл буває лише у графах, у яких існує конфігурація типу «пісочний годинник».

6) Простий цикл – це циклічний маршрут, у якому повторюються вершини. М 6 = (5, 4, 3, 2, 1, 5).

Приклад 7.2.

Для н-графа, наведеного малюнку 7.1, побудувати матрицю відстаней. Визначити діаметр та радіус графа. Вказати центри графа. Записати діаметральні та радіальні ланцюги

Рішення:

Для побудови матриці відстаней, зіставимо рядки та стовпці вершин. На перетині рядків та стовпців зазначимо відстань між відповідними вершинами.

d( a, b)	1	2	3	4	5	6	7
1	0	1	1	1	1	2	2	2
2	1	0	1	2	2	3	2	3
3	1	1	0	1	2	2	1	2
4	1	2	1	0	1	2	1	2
5	1	2	2	1	0	1	1	2
6	2	3	2	2	1	0	1	3
7	2	2	1	1	1	1	0	2

На місці (1, 1) стоїть 0, тому що найкоротший маршрут між вершиною 1 і вершиною 1 – це вироджений маршрут (без ребер) довжини 0.

На місці (1, 2) стоїть 1, тому що найкоротший маршрут між вершиною 1 і вершиною 2 – це єдине ребро, що зв'язує ці вершини.

На місці (1, 6) стоїть 2, оскільки найкоротший простий ланцюг, між вершиною 1 і вершиною 6 - це ланцюг з двох ребер (1, 5, 6). Отже, відстань між цими вершинами дорівнює 2.

В останньому стовпці таблиці зазначено відстань від даної вершини до найвіддаленішої від неї вершини – ексцентриситет. Їхні значення знаходимо за формулою (7.1).

Максимум значень останнього шпальти – діаметр графа. Звідки d(G) = 3.

Мінімум значень останнього стовпця – радіус графа. Звідки r(G) = 2.

Центрами є вершини: 1, 3, 4, 5, 7. Їхні ексцентриситети рівні радіусу графа.

Для побудови діаметральних ланцюгів з'ясуємо за допомогою матриці відстаней, які вершини найбільш віддалені одна від одної. Так як максимальна відстань між вершинами - це діаметр графа, значить, знайдемо вершини, що знаходяться на відстані, що дорівнює діаметру. Це вершини 2 і 6. Отже, всі діаметральні ланцюги у графі пов'язують ці вершини. Таких ланцюгів два:

D 1 = (2, 1, 5, 6) та D 2 = (2, 3, 7, 6).

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

Від центру 1 на відстані радіуса, що дорівнює 2, знаходяться вершини 6 і 7. Отже, можна провести радіальні ланцюги:

R 1 = (1, 5, 6) та R 2 = (1, 4, 7).

Від центру 3 на відстані радіуса знаходяться вершини 5 і 6. Отже, можна провести радіальні ланцюги:

R 3 = (3, 4, 5) та R 4 = (3, 7, 6).

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

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

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

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

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

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

Теорема 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), знайденої безпосередніми обчисленнями на малюнку.

1. Привласнюємо p=1 (p − кількість компонент зв'язності), .

2. Включаємо у безліч вершин V p компоненти сильної зв'язності D pвершини, що відповідають одиницям першого рядка матриці S p . Як матриця A(D p) Візьмемо підматрицю матриці A(D AV p .

3. Викреслюємо з S pрядки та стовпці, що відповідають вершинам з V p. Якщо не залишається жодного рядка (і стовпця), то p- Кількість компонентів сильної зв'язності. В іншому випадку позначимо матрицю, що залишилася після викреслення термін і стовпців як S p +1 , присвоюємо p= p+1 та переходимо до п. 2.

приклад

Виділимо компоненти зв'язності орієнтованого графа, зображеного на рис. 1. У цій задачі кількість вершин n= 5.

Значить, для даного орієнтованого графа матриця суміжності матиме розмірність 5×5 і виглядатиме таким чином

.

Знайдемо матрицю досяжності для цього орієнтованого графа за формулою 1) із затвердження 3:

,
,

,

Отже,

.

Таким чином, матриця сильної зв'язності, отримана за формулою 2) твердження 3, буде наступною:

.

Привласнюємо p=1
і складаємо безліч вершин першої компоненти сильної зв'язності D 1: це ті вершини, яким відповідають одиниці у першому рядку матриці S(D). Таким чином, перша компонента сильної зв'язності складається з однієї вершини.
.

Викреслюємо із матриці S 1 (D) рядок та стовпець, що відповідають вершині v 1 , щоб отримати матрицю S 2 (D):

.

Привласнюємо p=2. Безліч вершин другої компоненти зв'язності становитимуть ті вершини, яким відповідають одиниці у першому рядку матриці S 2 (D), тобто
. Складаємо матрицю суміжності для компонентів сильної зв'язності
вихідного графа D − у її якості візьмемо підматрицю матриці A(D), що складається з елементів матриці A, що знаходяться на перетині рядків і стовпців, що відповідають вершинам V 2:

.

Викреслюємо із матриці S 2 (D) рядки та стовпці, що відповідають вершинам V 2 щоб отримати матрицю S 3 (D), що складається з одного елемента:

і присвоюємо p=3. Таким чином, третій компонент сильної зв'язності вихідного графа, як і перший, складається з однієї вершини
.

Таким чином, виділено 3 компоненти сильної зв'язності орієнтованого графа D:

Завдання 2. Відстань в орієнтованому графі

За допомогою алгоритму фронту хвилі знайти відстані в орієнтованому графіD: діаметр, радіус та центри.

Нехай
орієнтований граф сn³2 вершинами та v,w (v¹ w) – задані вершиниз V.

Алгоритм пошуку мінімального шляху з у орієнтованому графі

(алгоритм фронту хвилі).

В іншому випадку продовжуємо:

В іншому випадку ми знайшли мінімальний шлях з в
та його довжина дорівнює k. Послідовність вершин

є цей мінімальний шлях. Робота завершується.

Зауваження

Щоб знайти відстані в орієнтованому графі, необхідно скласти матрицю мінімальних відстаней R(D) Між його вершинами. Це квадратна матриця розмірності
, елементи головної діагоналі якої дорівнюють нулю (
,i=1,..,n).

Спочатку складаємо матрицю суміжності. Потім переносимо одиниці з матриці суміжності до матриці мінімальних відстаней (
, якщо
). Далі рядково заповнюємо матрицю в такий спосіб.

Розглядаємо перший рядок, у якому є одиниці. Нехай це рядок − i-тая і на перетині з j-Тим стовпцем стоїть одиниця (тобто
). Це означає, що з вершини можна потрапити у вершину за крок. Розглядаємо j-Ту терміну (рядок варто вводити на розгляд, якщо вона містить хоча б одну одиницю). Нехай елемент
. Тоді з вершини у вершину можна потрапити за два кроки. Таким чином, можна записати
. Слід зауважити, що якщо в рядках, що розглядаються, дві або більше одиниць, то слід опрацьовувати всі можливі варіанти попадання з однієї вершини в іншу, записуючи в матрицю довжину найкоротшого з них.

Примітка: У контрольній роботі найдовший шлях знайти з допомогою алгоритму фронту хвилі.

приклад

Знайдемо відстані у орієнтованому графі D, зображений на рис. 2. У цій задачі кількість вершин n= 7, отже, матриці суміжності та мінімальних відстаней між вершинами орієнтованого графа D матимуть розмірність 7×7.

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

.

Починаємо заповнювати матрицю R(D) мінімальних відстаней: спочатку ставимо нулі по головній діагоналі і r ij =a ij, якщо a ij=1, (тобто переносимо одиниці з матриці суміжності). Розглядаємо перший рядок. Тут є дві одиниці, тобто з першої вершини за один крок можна потрапити до другої та шостої. З другої вершини можна потрапити за один крок до третьої (шлях у першу вершину нас не цікавить), отже, можна записати
. З шостої вершини можемо дістатися за один крок у п'яту та сьому, а значить,
,
. Тепер шукаємо маршрути, що виходять з першої вершини, що складаються з 3 кроків: за 2 кроки йдемо в третю вершину, звідти за один крок потрапляємо до четвертої, тому
. У результаті отримуємо таку матрицю:

Таким чином, діаметром досліджуваного орієнтованого графа буде
.

Для кожної вершини заданого орієнтованого графа знайдемо максимальне видалення (ексцентриситет) у графі G від вершини її за формулою, що була наведена вище
:r(v i) − максимальна з відстаней, що стоять у i-Тому рядку. Таким чином,

r(v 1)=3, r(v 2)=3, r(v 3)=5, r(v 4)=4, r(v 5)=2, r(v 6)=2, r(v 7)=3.

Значить, радіусом графа Gбуде

Відповідно, центрами графа G будуть вершини v 5 і v 6, так як величини їх ексцентриситетів збігаються з величиною радіусу
.

Опишемо тепер знаходження мінімального шляху з вершини v 3 у вершину v 6 за алгоритмом фронту хвилі. Позначимо вершину v 3 як V 0 , а вершину v 6 - як W(Див. рис. 3). Безліч вершин, що належать образу V 0 складається з одного елемента - це вершина v 4 , яку, згідно з алгоритмом, позначаємо як V 1: FW 1 (v 3)={v 4). Оскільки вершина, що шукається, не належить фронту хвилі першого рівня
, продовжуємо роботу алгоритму Будуємо фронт хвилі другого рівня-це безліч вершин, що належать образу вершини V 1: FW 2 (v 3)={v 7), позначаємо v 7 ≡V 2 . В образ вершини V 2 входять дві вершини - v 5 і v 4 , але, оскільки v 4 вже була позначена як V 0 то фронт хвилі третього рівня складається з одного елемента: FW 3 (v 3)={v 5 }, v 5 ≡V 3 . З непомічених вершин у образ вершини V 3 входять v 1 та v 2 , відповідно, FW 4 (v 3)={v 1 , v 2 }, v 1 ≡V 4 , v 2 ≡V 4 . Тепер помічені всі вершини, крім v 6 , яка входить у образ вершини
, тобто FW 5 (v 3)={v 6 ≡W), робота алгоритму закінчена. Мінімальний шлях (5 кроків) з вершини v 3 у вершину v 6 виглядає так: v 3 v 4 v 7 v 5 v 1 v 6 .