4.6. Перевірка зв'язності графів
Зв'язність заданого графа G зручно перевіряти за допомогою його матриці суміжності A.
Нехай A − матриця суміжності графа G = (V, E) з n вершинами (|V | = n). Тоді елемент aij(k ) i-го рядка та j-го стовпчика мат-
риці Ak дорівнює кількості шляхів довжиною k, які ведуть у графі G із вершини vi у вершину vj.
Звідси отримаємо такий метод перевірки зв'язності графа G. У графі G вершини vi i vj (i ≠ j) зв'язані тоді й тільки тоді, коли
елемент і-го рядка та j-го стовпчика матриці
A + A2 + A3 + … + An – 1
не дорівнює нулю.
Це випливає із тієї простої властивості, що коли в графі G із n вершинами існує шлях між вершинами vi i vj (i ≠ j), тоді між цими вершинами обов'язково існує шлях довжиною не більше n − 1.
Крім того, щоб вилучити умову i ≠ j для встановлення зв'язності між будь-якими вершинами графа G, можна використову-
вати матрицю
M (n) = In + A + A2 + A3 + … + An – 1,
де In − одинична матриця порядку n (нагадаємо, що будь-яка вершина зв'язана сама із собою шляхом довжиною 0).
Таким чином, граф G зв'язний тоді й тільки тоді, коли в матриці M (n) немає нульових елементів.
Граф G* = (V, E*) називають транзитивним замиканням
графа G = (V, E), якщо (v, w) E*, тоді й тільки тоді, коли вершини v і w зв'язані в графі G.
Отже, транзитивне замикання графа G є повним графом тоді й тільки тоді, коли граф G зв'язний.
Якщо графу G = (V, E) відповідає відношення R на V, то графу G* відповідатиме рефлексивне транзитивне замикання R* відношення R (див. п. 2.6).
Побудуємо для графа G* n × n-матрицю A* за таким правилом: (i, j)-й елемент матриці A* дорівнює 1 тоді й тільки тоді,
176
коли відповідний елемент матриці 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