Реферат на тему:
Перевірка зв’язності графів
Зв’язність заданого графа G зручно перевіряти за допомогою його матриці
суміжності A.
Теорема 3.9. Нехай A ( матриця суміжності графа G =(V,E ) з n вершинами
(|V |=n). Тоді елемент aij(k) i-го рядка і j-го стовпчика матриці Ak
дорівнює кількості шляхів довжини k, які ведуть в графі G з вершини vi у
вершину vj.
Доведення проведемо індукцією за k.
Для k=1 aij(1)=aij . За означенням матриці A aij дорівнює 1 тоді і
тільки тоді, коли в графі G з вершини vi веде ребро у вершину vj. Але
єдиний можливий шлях довжини 1 з vi у vj ( це ребро (vi,vj). Отже,
aij(1) дорівнює кількості шляхів довжини 1 з vi у vj.
Припустімо, що твердження теореми справджується для
k=m (1, m ( 2. Розглянемо елемент aij(m) матриці Am. Оскільки
Am = Am-1 A, то
ait(m-1)atj(1).
Розглянемо окремий доданок ait(m-1)atj(1) останньої суми. За припущенням
індукції aij(m-1) дорівнює кількості шляхів довжини
m(1, які ведуть з вершини vi у вершину vt; тоді добуток ait(m-1)atj(1)
дорівнює кількості шляхів довжини m, що ведуть з вершини vi у вершину vj
і передостанньою вершиною яких є vt. Отже, сума таких доданків для всіх
t від 1 до n дає шукану кількість шляхів довжини m з vi у vj. Теорему
доведено.
Наслідок 3.9.1. Нехай A ( матриця суміжності графа G =(V,E ) з n
вершинами. В графі 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).
Наслідок 3.9.2. Граф 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.
Побудуємо для графа G ( n(n-матрицю A (за таким правилом: (i,j)-тий
елемент матриці A ( дорівнює 1 тоді і тільки тоді, коли відповідний
елемент матриці M (n) не дорівнює 0, всі інші елементи матриці A (
дорівнюють 0.
Матрицю A ( називають матрицею досяжності графа G (інші назви: матриця
зв’язності, матриця зв’язку).
Обчислення матриці досяжності A ( графа G ( можна здійснити й іншим
методом.
(cit ( dtj ), де сit і dtj ( елементи матриць С і D, а операції ( і ( (
це операції диз’юнкції та кон’юнкції.
Позначимо через A(m) матрицю A(1)(A(1)(…(A(1) (m разів).
Аналогічно теоремі 3.9 може бути доведена така теорема.
Теорема 3.10. Нехай A(1) ( бульова матриця, яка відповідає матриці
суміжності A графа G =(V,E ). Елемент bij(m) (i(j) матриці A(m) дорівнює
1 тоді і тільки тоді, коли в графі G існує принаймні один шлях довжини
m, що веде з вершини vi у vj.
Наслідок 3.10.1. Матриця досяжності A( графа G з n вершинами може бути
обчислена за формулою A(=In(1)(A(1)(A(2)(…(A(n-1). (Операція
диз’юнкції виконується для матриць поелементно).
Наслідок 3.10.2. Граф G є зв’язний тоді і тільки тоді, коли всі елементи
його матриці досяжності A( дорівнюють 1.
Список літератури
1. Харари Т. Теория графов.- М.,1973.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов
В.И., Тышкевич Р.И.- М., 1990.
3. Зыков А.А. Основы теории графов.- М., 1987.
4. Оре О. Теория графов.- М., 1980.
5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.
6. Уилсон Р. Введение в теорию графов.- М., 1977
7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978
8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980
Нашли опечатку? Выделите и нажмите CTRL+Enter
