Перевірка зв'язності графів

Зв'язність заданого графу G зручно перевіряти за допомогою його матриці суміжності A.

Теорема I

Нехай A — матриця суміжності графу G =(V, E) з n вершинами (|V |=n). Тоді елемент a_ij(k) i-го рядка і j-го стовпчика матриці A_k дорівнює кількості шляхів довжини k, які ведуть в графі G з вершини v_i у вершину v_j.

Доведення I

Проведемо індукцією за k.

Для k=1 a_ij⁽¹⁾=a_ij. За означенням матриці A a_ij дорівнює 1 тоді і тільки тоді, коли в графі G з вершини v_i веде ребро у вершину v_j. Але єдиний можливий шлях довжини 1 з v_i у v_j — це ребро (v_i,v_j). Отже, a_ij⁽¹⁾ дорівнює кількості шляхів довжини 1 з v_i у v_j.

Припустімо, що твердження теореми справджується для k=m-1, m ≥ 2. Розглянемо елемент a_ij^(m) матриці A^m. Оскільки A^m = A^m-1 A, то

Розглянемо окремий доданок a_it^(m-1)a_tj⁽¹⁾ останньої суми. За припущенням індукції a_ij^(m-1) дорівнює кількості шляхів довжини m-1 , які ведуть з вершини v_i у вершину v_t; тоді добуток a_it^(m-1)a_tj⁽¹⁾ дорівнює кількості шляхів довжини m, що ведуть з вершини v_i у вершину v_j і передостанньою вершиною яких є v_t. Отже, сума таких доданків для всіх t від 1 до n дає шукану кількість шляхів довжини m з v_i у v_j. Теорему доведено.

Наслідок I

Нехай A — матриця суміжності графу G =(V, E) з n вершинами. В графі G вершини v_i i v_j (i ≠ j) є зв'язаними тоді і тільки тоді, коли елемент і-го рядка і j-го стовпчика матриці A+A²+A³+…+A^n-1 не дорівнює нулю.

Це випливає з доведеної теореми та тієї простої властивості, що коли в графі G з n вершинами існує шлях між вершинами v_i i v_j (i ≠ j), тоді між цими вершинами обов'язково існує шлях довжини не більшої ніж n-1.

Крім того, щоб вилучити умову i ≠ j для встановлення зв'язності між будь-якими вершинами графу G можна використовувати матрицю M⁽ⁿ⁾=Iⁿ+A+A²+A³+…+A^n-1, де Iⁿ — одинична матриця порядку n (нагадаємо, що будь-яка вершина є зв'язаною сама з собою шляхом довжини 0).

Наслідок II

Граф G буде зв'язним тоді і тільки тоді, коли в матриці M⁽ⁿ⁾ немає нульових елементів.

Граф G^*=(V, E^*) називається транзитивним замиканням даного графу G =(V, E), якщо (v, w)∈E^* тоді і тільки тоді, коли вершини v і w є зв'язані в графі G.

Таким чином, транзитивне замикання графу G є повним графом тоді і тільки тоді, коли граф G зв'язний.

Якщо графу G =(V, E) відповідає відношення R на V, то графу G^* відповідатиме транзитивне замикання R^* відношення R.

Побудуємо для графу G^* n×n-матрицю A^*за таким правилом: (i, j)-тий елемент матриці A^* дорівнює 1 тоді і тільки тоді, коли відповідний елемент матриці M⁽ⁿ⁾ не дорівнює 0, всі інші елементи матриці A^* дорівнюють 0.

Матрицю A^* називають матрицею досяжності графу G (інші назви: матриця зв'язності, матриця зв'язку).

Обчислення матриці досяжності A^* графу G^* можна здійснити й іншим методом.

Позначимо через A⁽¹⁾ булеву матрицю, елементи якої повністю збігаються з елементами матриці A, але розглядаються не як числа 0 і 1, а як символи булевого алфавіту 0 і 1. Введемо операцію булевого множення С∧D матриць С і D, які складаються з булевих елементів 0 і 1, таким чином: елемент f_ij матриці С∧D дорівнює , де с_it і d_tj — елементи матриць С і D, а операції ∧ і ∨ — це операції диз'юнкції та кон'юнкції.

Позначимо через A^(m) матрицю A⁽¹⁾∧A⁽¹⁾∧…∧A⁽¹⁾ (m разів).

Теорема II

Аналогічно теоремі 1 може бути доведена така теорема. Нехай A⁽¹⁾ — булева матриця, яка відповідає матриці суміжності A графу G =(V, E). Елемент b_ij^(m) (i≠j) матриці A^(m) дорівнює 1 тоді і тільки тоді, коли в графі G існує принаймні один шлях довжини m, що веде з вершини v_i у v_j.

Наслідок I.

Матриця досяжності A^* графу G з n вершинами може бути обчислена за формулою A^*=I_n⁽¹⁾∨A⁽¹⁾∨A⁽²⁾∨…∨A^(n-1). (Операція диз'юнкції виконується для матриць поелементно).

Наслідок II.

Граф G є зв'язний тоді і тільки тоді, коли всі елементи його матриці досяжності A^* дорівнюють 1.

Джерело

• Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.- М., 1990.
• Зыков А. А. Основы теории графов.- М., 1987.
• Оре О. Теория графов.- М., 1980.