WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Перевірка зв’язності графів - Реферат

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


Реферат на тему:
Перевірка зв'язності графів
Зв'язність заданого графа 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, то
aij(m) = ait(m-1) atj = 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 можна здійснити й іншим методом.
Позначимо через A(1) бульову матрицю, елементи якої повністю збігаються з елементами матриці A, але розглядаються не як числа 0 і 1, а як символи бульового алфавіту 0 і 1. Введемо операцію бульового множення С D матриць С і D, які складаються з бульових елементів 0 і 1, таким чином: елемент fij матриці С D дорівнює f ij = (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
Loading...

 
 

Цікаве