Математична модель. Метричні характеристики неорієнтованого графа

Твердження. Якщо для двох вершин існує маршрут, що їх пов'язує, то обов'язково знайдеться мінімальний маршрут, що з'єднує ці вершини. Позначимо довжину цього маршруту через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 матриця відстаней має наступний вигляд:

. (12.2)

Обчислимо ексцентриситет кожної вершини. Цю величину можна визначити як максимальний елемент відповідного стовпця матриці відстаней (або рядки – оскільки матриця 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. Помножуватимемо матрицю суміжності саму на себе доти, доки в матриці не з'явиться ненульовий елемент . Тоді відповідний елемент матриці відстаней дорівнює ступенюматриці суміжності: . На наступному кроці отримуємо

У минулому параграфі ми підкреслили, що введена там матриця суміжності $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(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. Завдання на деревах

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

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

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

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

Неважко переконатися, що введене таким чином поняття відстані задовольняє аксіомам метрики:

2. тоді і тільки тоді, коли;

3. ;

4. справедлива нерівність трикутника:

Для фіксованої вершини графа відстань до найвіддаленішої від неї вершини: , називають ексцентриситетом (максимальним видаленням) вершини.

Діаметромграфа називають число , рівну відстаніміж найбільш віддаленими один від одного вершинами графа:

.

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

Мінімальний з ексцентриситетів вершин зв'язкового графа називають його радіусомі позначають:

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

Для ілюстрації звернемося до графа на рис. 4.29. Тут

Тому

Вершина 2 є центром графа, проте інші його вершини - периферійні. Ланцюг 1, 2, 3 - один з діаметральних ланцюгів.

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

Завдання знаходження центральних вершин графа постійно зустрічається в практичної діяльності. Нехай, наприклад, вершини графа відповідають невеликим селищам, а його ребра – дорогам між ними. Потрібно оптимально розмістити за цим населеним пунктам, Скажімо, магазини. У подібних ситуаціяхКритерій оптимальності зазвичай полягає в оптимізації «найгіршого» випадку, тобто мінімізації відстані від магазину до найбільш віддаленого селища. Такий підхід до оптимізації передбачає розміщення магазинів у селищах, які є центральними вершинами графа.

Обходи графів

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

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

Цикл у графі називається ейлеровимякщо він містить всі ребра графа. Зв'язковий граф, в якому є ейлерів цикл, називається ейлеровимграфом. Такий граф можна намалювати, не відриваючи олівця від паперу та не повторюючи ліній.

Наприклад, граф, зображений на рис. 4.31 є ейлеровим, оскільки він містить ейлерів цикл 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. У цьому графі є й інші ейлерові цикли. Зрозуміло, що будь-які два таких цикли відрізняються один від одного лише порядком обходу ребер.

Теорема 4.7.(Л. Ейлер, 1736 р .) Зв'язковий граф є ейлеровим тоді і лише тоді, коли ступеня всіх його вершин парні.

Ланцюг називається ейлеровоїякщо вона містить всі ребра графа.

Теорема 4.8(Л. Ейлер, 1736 р .) Мультиграф володіє ейлеровим ланцюгом тоді і тільки тоді, коли він зв'язаний і число вершин непарного ступеня дорівнює 0 або 2.

Незважаючи на «схожість» у визначеннях для ейлерових та гамільтонових циклів, відповідні теорії, що встановлюють критерії існування та алгоритми пошуку таких циклів, мають мало спільного. Терема Ейлера (теорема 4.7)дозволяє легко встановити, чи є граф ейлеровим. Розроблено алгоритми, що дозволяють досить просто знайти ейлерові цикли ейлерового графа. Що стосується гамільтонових графів, то тут стан справ суттєво інший. Відповісти на питання, чи є граф гамільтоновим, як правило, дуже важко. Загального критерію, Подібного критерію Ейлера, тут немає. Але, як виявилося, серед багатьох графів ейлерових графів мізерно мало, а ось гамільтонових графів досить багато.