UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПеревірка зв’язності графів (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1377
Скачало198
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Зв’язність заданого графа 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 може бути доведена така теорема.

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ