Зв'язність заданого графу G зручно перевіряти за допомогою його матриці суміжності A.
Теорема I
Нехай A — матриця суміжності графу G =(V, E) з n вершинами (|V |=n). Тоді елемент aij(k) i-го рядка і j-го стовпчика матриці Ak дорівнює кількості шляхів довжини k, які ведуть в графі G з вершини vi у вершину vj.
Доведення I
Проведемо індукцією за 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) останньої суми. За припущенням індукції aij(m-1) дорівнює кількості шляхів довжини m-1 , які ведуть з вершини vi у вершину vt; тоді добуток ait(m-1)atj(1) дорівнює кількості шляхів довжини m, що ведуть з вершини vi у вершину vj і передостанньою вершиною яких є vt. Отже, сума таких доданків для всіх t від 1 до n дає шукану кількість шляхів довжини m з vi у vj. Теорему доведено.
Наслідок I
Нехай 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).
Наслідок II
Граф 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 дорівнює , де сit і dtj — елементи матриць С і D, а операції ∧ і ∨ — це операції диз'юнкції та кон'юнкції.
Позначимо через A(m) матрицю A(1)∧A(1)∧…∧A(1) (m разів).
Теорема II
Аналогічно теоремі 1 може бути доведена така теорема. Нехай A(1) — булева матриця, яка відповідає матриці суміжності A графу G =(V, E). Елемент bij(m) (i≠j) матриці A(m) дорівнює 1 тоді і тільки тоді, коли в графі G існує принаймні один шлях довжини m, що веде з вершини vi у vj.
Наслідок I.
Матриця досяжності A* графу G з n вершинами може бути обчислена за формулою A*=In(1)∨A(1)∨A(2)∨…∨A(n-1). (Операція диз'юнкції виконується для матриць поелементно).
Наслідок II.
Граф G є зв'язний тоді і тільки тоді, коли всі елементи його матриці досяжності A* дорівнюють 1.
Джерело
- Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.- М., 1990.
- Зыков А. А. Основы теории графов.- М., 1987.
- Оре О. Теория графов.- М., 1980.
На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до . |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zv yaznist zadanogo grafu G zruchno pereviryati za dopomogoyu jogo matrici sumizhnosti A Teorema INehaj A matricya sumizhnosti grafu G V E z n vershinami V n Todi element aij k i go ryadka i j go stovpchika matrici Ak dorivnyuye kilkosti shlyahiv dovzhini k yaki vedut v grafi G z vershini vi u vershinu vj Dovedennya I Provedemo indukciyeyu za k Dlya k 1 aij 1 aij Za oznachennyam matrici A aij dorivnyuye 1 todi i tilki todi koli v grafi G z vershini vi vede rebro u vershinu vj Ale yedinij mozhlivij shlyah dovzhini 1 z vi u vj ce rebro vi vj Otzhe aij 1 dorivnyuye kilkosti shlyahiv dovzhini 1 z vi u vj Pripustimo sho tverdzhennya teoremi spravdzhuyetsya dlya k m 1 m 2 Rozglyanemo element aij m matrici Am Oskilki Am Am 1 A to a i j m t 1 n a i t m 1 a t j t 1 n a i t m 1 a t j 1 displaystyle a ij m sum t 1 n a it m 1 a tj sum t 1 n a it m 1 a tj 1 Rozglyanemo okremij dodanok ait m 1 atj 1 ostannoyi sumi Za pripushennyam indukciyi aij m 1 dorivnyuye kilkosti shlyahiv dovzhini m 1 yaki vedut z vershini vi u vershinu vt todi dobutok ait m 1 atj 1 dorivnyuye kilkosti shlyahiv dovzhini m sho vedut z vershini vi u vershinu vj i peredostannoyu vershinoyu yakih ye vt Otzhe suma takih dodankiv dlya vsih t vid 1 do n daye shukanu kilkist shlyahiv dovzhini m z vi u vj Teoremu dovedeno Naslidok I Nehaj A matricya sumizhnosti grafu G V E z n vershinami V grafi G vershini vi i vj i j ye zv yazanimi todi i tilki todi koli element i go ryadka i j go stovpchika matrici A A2 A3 An 1 ne dorivnyuye nulyu Ce viplivaye z dovedenoyi teoremi ta tiyeyi prostoyi vlastivosti sho koli v grafi G z n vershinami isnuye shlyah mizh vershinami vi i vj i j todi mizh cimi vershinami obov yazkovo isnuye shlyah dovzhini ne bilshoyi nizh n 1 Krim togo shob viluchiti umovu i j dlya vstanovlennya zv yaznosti mizh bud yakimi vershinami grafu G mozhna vikoristovuvati matricyu M n In A A2 A3 An 1 de In odinichna matricya poryadku n nagadayemo sho bud yaka vershina ye zv yazanoyu sama z soboyu shlyahom dovzhini 0 Naslidok II Graf G bude zv yaznim todi i tilki todi koli v matrici M n nemaye nulovih elementiv Graf G V E nazivayetsya tranzitivnim zamikannyam danogo grafu G V E yaksho v w E todi i tilki todi koli vershini v i w ye zv yazani v grafi G Takim chinom tranzitivne zamikannya grafu G ye povnim grafom todi i tilki todi koli graf G zv yaznij Yaksho grafu G V E vidpovidaye vidnoshennya R na V to grafu G vidpovidatime tranzitivne zamikannya R vidnoshennya R Pobuduyemo dlya grafu G n n matricyu A za takim pravilom i j tij element matrici A dorivnyuye 1 todi i tilki todi koli vidpovidnij element matrici M n ne dorivnyuye 0 vsi inshi elementi matrici A dorivnyuyut 0 Matricyu A nazivayut matriceyu dosyazhnosti grafu G inshi nazvi matricya zv yaznosti matricya zv yazku Obchislennya matrici dosyazhnosti A grafu G mozhna zdijsniti j inshim metodom Poznachimo cherez A 1 bulevu matricyu elementi yakoyi povnistyu zbigayutsya z elementami matrici A ale rozglyadayutsya ne yak chisla 0 i 1 a yak simvoli bulevogo alfavitu 0 i 1 Vvedemo operaciyu bulevogo mnozhennya S D matric S i D yaki skladayutsya z bulevih elementiv 0 i 1 takim chinom element fij matrici S D dorivnyuye f i j t 1 n c i t d t j displaystyle f ij bigvee t 1 n c it wedge d tj de sit i dtj elementi matric S i D a operaciyi i ce operaciyi diz yunkciyi ta kon yunkciyi Poznachimo cherez A m matricyu A 1 A 1 A 1 m raziv Teorema IIAnalogichno teoremi 1 mozhe buti dovedena taka teorema Nehaj A 1 buleva matricya yaka vidpovidaye matrici sumizhnosti A grafu G V E Element bij m i j matrici A m dorivnyuye 1 todi i tilki todi koli v grafi G isnuye prinajmni odin shlyah dovzhini m sho vede z vershini vi u vj Naslidok I Matricya dosyazhnosti A grafu G z n vershinami mozhe buti obchislena za formuloyu A In 1 A 1 A 2 A n 1 Operaciya diz yunkciyi vikonuyetsya dlya matric poelementno Naslidok II Graf G ye zv yaznij todi i tilki todi koli vsi elementi jogo matrici dosyazhnosti A dorivnyuyut 1 DzhereloLekcii po teorii grafov Emelichev V A Melnikov O I Sarvanov V I Tyshkevich R I M 1990 Zykov A A Osnovy teorii grafov M 1987 Ore O Teoriya grafov M 1980 Na cyu stattyu ne posilayutsya inshi statti Vikipediyi Bud laska rozstavte posilannya vidpovidno do prijnyatih rekomendacij