Перевірка зв"язності графів (реферат)
Наслідок 3.9.1. Нехай A атриця суміжності графа G =(V, E) з n вершинами. В графі G вершини vi i vj (i є зв’язаними тоді і тільки тоді, коли елемент і-го рядка і j-го стовпчика матриці A+A2+A3+…+An -1 не дорівнює нулю. Побудуємо для графа G матрицю A, а таким правилом: (i, j)-тий елемент матриці A орівнює 1 тоді і тільки тоді, коли відповідний елемент матриці M (n) не дорівнює 0, всі інші елементи… Читати ще >
Перевірка зв"язності графів (реферат) (реферат, курсова, диплом, контрольна)
Реферат на тему:
Перевірка зв’язності графів
Зв’язність заданого графа 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) = ait (m-1) atj = 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 = (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.