.

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

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 1457
Скачать документ

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

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

Зв’язність заданого графа 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

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020