коли відповідний елемент матриці M (n) не дорівнює 0; усі інші елементи матриці A* дорівнюють 0.
Матрицю A* називають матрицею досяжності графа G (інші назви: матриця зв'язності, матриця зв'язку).
Матрицю досяжності A* можна обчислити також в інший спосіб. Позначимо через A(1) булеву матрицю, елементи якої повністю збігаються з елементами матриці A, але їх розглядають не як числа 0 і 1, а як символи булевого (логічного) алфавіту 0 і 1 (див. п. 1.1). Уведемо операцію булевого множення С D матриць С і D, які складаються з булевих елементів 0 і 1, так:
(i, j)-й елемент матриці С D
fij = n (cit dtj), t=1
де сit і dtj − відповідні елементи матриць С і D, а операції і − це операції диз'юнкції та кон'юнкції (див. п. 1.1).
Позначимо через A(m) матрицю A(1) A(1) … A(1) (m разів). Якщо A(1) − булева матриця, що відповідає матриці суміжності A графа G = (V, E), то елемент bij(m) (i ≠ j) матриці A(m) дорів-
нює 1 тоді й тільки тоді, коли в графі G існує принаймні один шлях довжиною m, що веде sз вершини vi у вершину vj.
Отже, матрицю досяжності A* графа G із n вершинами можна обчислити за формулою
A* = In(1) A(1) A(2) … A(n – 1)
(операція диз'юнкції виконується для матриць поелементно). Таким чином, граф G зв'язний тоді й тільки тоді, коли всі
елементи його булевої матриці досяжності A* дорівнюють 1. Приклад 4.12. Нехай A − матриця суміжності графа G. Довести,
що діагональний елемент aii(3) матриці A3 дорівнює подвоєній кількості трикутників графа G, які містять вершину з номером i.
Елемент aii(3) дорівнює кількості шляхів довжиною 3 у графі
G, що починаються й закінчуються у вершині i (отже, кожен такий шлях є трикутником). Ця кількість удвічі більша від кількості трикутників з вершиною i, тому що існують два способи обійти кожен із цих трикутників, починаючи й завершуючи обхід у вершині i. ◄
177
Завдання для самостійної роботи
1.Користуючись наведеними алгоритмами, з'ясувати, чи є зв'язними графи, задані матрицями суміжності в завданні для самостійної роботи 4.1.2.
2.Нехай A − матриця суміжності графа G. Довести, що сума
всіх діагональних елементів aii(3) матриці A3 у шість разів перевищує кількість трикутників у графі G.
3. Нехай A − матриця суміжності зв'язного графа G. Довести, що відстань d(vi, vj) між вершинами vi і vj (i ≠ j) дорівнює най-
меншому натуральному числу k, для якого елемент aij(k ) i-го рядка та j-го стовпчика матриці Ak відмінний від 0.
4.7.Деякі важливі класи графів. Дерева та двочасткові графи
Граф без циклів називають ациклічним, ациклічний зв'язний граф – деревом, довільний ациклічний граф – лісом.
Очевидно, що зв'язними компонентами лісу є дерева, тому кожен ліс можна зобразити у вигляді прямої суми дерев.
Дерева − це особливий і дуже важливий клас графів. Особлива роль дерев визначається як широким їх застосуванням у різних галузях науки і практики, так і тим особливим положенням, яке дерева займають у самій теорії графів. Останнє випливає з граничної простоти будови дерев. Часто при розв'язуванні різних задач теорії графів їх дослідження починають із дерев.
Існують також інші, рівносильні наведеному, означення дерева, які можна розглядати як його характеристичні властивості (або критерії).
Для графа G = (V, E), |V | = n, |E| = m, такі твердження рівносильні:
1)G − дерево (ациклічний зв'язний граф);
2)G − зв'язний граф і m = n − 1;
3)G − ациклічний граф і m = n − 1;
4)для будь-яких вершин v і w графа G існує лише один простий ланцюг, що їх з'єднує;
178
5) G − такий ациклічний граф, що якщо будь-які його несуміжні вершини v i w з'єднати ребром (v, w), то одержаний граф міститиме рівно один цикл.
Приклад 4.13.
1. Для довільного дерева T = (V, E) з n вершинами виконується
∑δ(v) = 2(n −1).
v V
Із вищенаведених тверджень маємо, що дерево T із n вершинами має n − 1 ребро, тому дана рівність випливає з (4.1).
2. Будь-яке нетривіальне дерево T = (V, E) має принаймні дві кінцеві вершини.
Припустимо, що дерево T має менше двох кінцевих вершин. Тоді степінь лише однієї вершини може дорівнювати 1, а степені всіх інших – не менші 2. Отже,
∑δ(v) ≥ 2(n −1) +1= 2n −1,
v V
що суперечить результату попередньої задачі.
3. Ліс F, який має n вершин і складається з k дерев, містить n − k ребер.
Дійсно, якщо дерево Ti лісу F має ni вершин, то воно містить ni − 1 ребро, i = 1, 2, …, k. Додаючи кількості ребер кожного з дерев Ti, дістанемо кількість n − k ребер у F.
4. У графі G із n вершинами, який має більше ніж n − 1 ребро, є принаймні один цикл.
Розглянемо довільний граф G із n вершинами та кількістю ребер, яка перевищує n − 1. Припустимо, що G – ациклічний граф. Тоді G − ліс, що складається з k дерев (k ≥ 1). За попередньою задачею кількість ребер у такому графі дорівнює n − k; тоді n − k > n − 1, тобто k < 1, що неможливо. ◄
5.Чи може зв'язний граф із n вершинами та n − 1 ребром мати цикл? Відповідь обґрунтувати.
Ні. За наведеними вище твердженнями зв'язний граф з n вершинами і n – 1 ребром є деревом, тобто є ациклічним графом.
6.Описати всі дерева, доповнення яких також є деревами.
Рівність n(n–1)/2 – (n – 1) = n – 1 (див. приклад 4.9 (2)) вико-
нується для n = 1 або n = 4, що відповідає тривіальному графу або графу з прикладу 4.9 (1). ◄
179
Кістяковим (каркасним) деревом зв'язного графа G = (V, E)
називають дерево T = (V, ET) таке, що ET E.
Кістяковим (каркасним) лісом незв'язного графа G = (V, E)
називають сукупність кістякових (каркасних) дерев зв'язних компонент графа G.
Приклад 4.14.
1. Для отримання кістякового дерева зв'язного графа G = (V, E) слід вилучити |E| − |V | + 1 ребро.
Кількість ребер, що залишаться в кістяковому дереві графа G, дорівнюватиме |V | − 1, отже, має бути вилучено
|E| − (|V | − 1) = |E| − |V | + 1 ребро.
2. Нехай граф G = (V, E) має k компонент зв'язності. Для отримання його кістякового лісу з графа G потрібно вилучити
|E| − |V | + k ребер.
Для доведення цього твердження потрібно застосувати результат попередньої задачі до кожної компоненти зв'язності графа G, відтак підсумувати результати. ◄
Число |E| − |V | + k називають цикломатичним числом графа G і позначають ν(G).
Граф G = (V, E) називають двочастковим, якщо існує таке розбиття {V1, V2} множини його вершин V на дві підмножини (частки), що для довільного ребра (v,w) E або v V1 i w V2,
або v V2 i w V1.
Двочастковий граф G = (V, E) називають повним двочастко вим, якщо для будь-якої пари вершин його часток v V1 i w V2 маємо (v, w) E. Якщо |V1| = m i |V2| = n, то повний двочастковий граф G позначають Km,n.
Відомо таке твердження (теорема Кеніга): граф є двочастковим тоді й тільки тоді, коли всі його цикли мають парну довжину.
Завдання для самостійної роботи
1. Довести властивості цикломатичного числа ν(G) графа G: (а) Для довільного графа G виконується ν(G) ≥ 0.
(б) Граф G є лісом тоді й тільки тоді, коли ν(G) = 0.
(в) Граф G має рівно один простий цикл тоді й тільки тоді,
коли ν(G) = 1.
180
(г) Кількість циклів у графі G не менша ніж ν(G).
2.Описати всі дерева, які є самодоповнювальними графами.
3.Довести, що граф G зв'язний тоді й тільки тоді, коли він має кістякове дерево.
4.Довести, що граф (простий цикл парної довжини C2k) є
двочастковим графом.
5.Скільки ребер містить повний двочастковий граф Kn,m?
6.Довести, що будь-яке дерево є двочастковим графом. Які дерева є повними двочастковими графами?
7.Який вигляд має доповнення графа Kn,m?
8.Чи для кожного натурального числа k існує повний двочас-
тковий граф, кількість ребер якого дорівнює k (k ≥ 2)?
9. Чому дорівнюють діаметр і радіус повного двочасткового графа Kn,m?
4.8. Плоскі та планарні графи
Часто не має особливого значення, як зобразити граф у вигляді рисунка на площині (діаграми), оскільки ізоморфні графи подібні за структурою й містять ту саму інформацію. Однак існують ситуації, коли потрібно, щоб зображення графа на площині задовольняло певні умови. Наприклад, якщо граф є моделлю якоїсь електронної схеми чи транспортної мережі, де вершини позначають окремі елементи схеми чи станції, а ребра – відповідно електричні проводи і шляхи, то бажано таким чином розташувати ці ребра на площині, щоб уникнути перетинів. Так виникає поняття плоского графа.
Граф називають плоским, якщо його діаграму можна зобразити на площині таким чином, щоб лінії, які відповідають ребрам графа, не перетиналися (тобто мали спільні точки тільки у вершинах графа). Таке зображення називають плоскоюкартою графа.
Граф називають планарним, якщо він ізоморфний деякому плоскому графу.
Наприклад, граф на рис. 4.7 а – планарний, оскільки він ізоморфний графу, що зображений поруч (рис. 4.7 б). Простий цикл, дерево та ліс − також планарні графи.
181