Перевірка зв"язності графів (реферат)

Реферат на тему:

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

Зв’язність заданого графа 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 m Розглянемо елемент aij (m) матриці Am. Оскільки Am = Am-1 A, то.

aij (m) = $$\underset{t=1}{\overset{n}{}}$$ ait (m-1) atj = $$\underset{t=1}{\overset{n}{}}$$ ait (m-1)atj (1).

Розглянемо окремий доданок ait (m-1)atj (1) останньої суми. За припущенням індукції aij (m-1) дорівнює кількості шляхів довжини.

mякі ведуть з вершини 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-го стовпчика матриці A+A2+A3+…+An -1 не дорівнює нулю.

Це випливає з доведеної теореми та тієї простої властивості, що коли в графі G з n вершинами існує шлях між вершинами vi i vj (i, тоді між цими вершинами обов’язково існує шлях довжини не більшої ніж n /p>

Крім того, щоб вилучити умову i для встановлення зв’язності між будь-якими вершинами графа G можна використовувати матрицю M (n)=In+A+A2+A3+…+An-1, де In динична матриця порядку n (нагадаємо, що будь-яка вершина є зв’язаною сама з собою шляхом довжини 0).

Наслідок 3.9.2. Граф G буде зв’язним тоді і тільки тоді, коли в матриці M (n) немає нульових елементів.

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

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

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

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

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

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

Позначимо через A (1) бульову матрицю, елементи якої повністю збігаються з елементами матриці A, але розглядаються не як числа 0 і 1, а як символи бульового алфавіту 0 і 1. Введемо операцію бульового множення С матриць С і D, які складаються з бульових елементів 0 і 1, таким чином: елемент fij матриці С дорівнює f ij = $$\underset{t=1}{\overset{n}{}}$$ (cit j), де сit і dtj лементи матриць С і D, а операції е операції диз’юнкції та кон’юнкції.

Позначимо через A (m) матрицю A (1))) (m разів).

Аналогічно теоремі 3.9 може бути доведена така теорема.

Теорема 3.10. Нехай A (1) ульова матриця, яка відповідає матриці суміжності A графа G =(V, E). Елемент bij (m) (iматриці A (m) дорівнює 1 тоді і тільки тоді, коли в графі G існує принаймні один шлях довжини m, що веде з вершини vi у vj.

Наслідок 3.10.1. Матриця досяжності Aрафа G з n вершинами може бути обчислена за формулою A (1)))-1). (Операція диз’юнкції виконується для матриць поелементно).

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

Список літератури.

1. Харари Т. Теория графов.- М., 1973.

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

3. Зыков А. А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М., 1978.

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М., 1980.