Page 35 - 4336

Оскілььки будьь-яка верршина гррафа, якка досяжжна з v , пповиннаа
i
бутти досяжжна з виккористаннням шляяху (абоо шляхів)) довжинни 0 абоо

1, аабо 2, ... , або k,, то мноожина веершин, ддосяжниих з вершшини v ,,
i
можжна подаати у виггляді

+2
+1
+k
R(v )=={v }ГГ (v )ГГ (v )Г (v ). (3.1))
i
i
i
i
ii
Як баачимо, ммножинаа досяжних верршин R((v ) преддставляєє
i
+
пряяме траннзитивнее замиккання вершини v , тоббто R(v )=Т (v )..
i
i
i i
Отжже, дляя побуддови маатриці ддосяжноості неообхідно знайтии
доссяжні мнножини R(v ) длля всіх ввершин v V, ввважаючии, r =1,,
i,j
i
i
якщщо v R(v ) та r ==0 у іншшому виппадку.
i
i,j
j
Прикллад 3.1. Для граафа, навведеногоо на рисс. 3.1, а,, знайтии
маттрицю доосяжноссті R.
Маатриця сусуміжноссті
v 1 v 2 vv v v v 6 v 7
5 5
3
4
v 1 01 00 0 1 00
v 2 00 00 1 0 00
v 3 00 00 1 0 00
A= v 4 00 00 0 1 00

v 5 00 00 0 0 00
v 6 00 11 0 0 01
v 7 00 00 1 0 10

а бб
Матрииця досяяжності Матрииця конттрдосяжжності
v v 2 v v v 5 vv 6 v 7 v 1 v 2 vv v v v 6 v 7
4
3
1
3
4
5 5
v 1 10 1 1 00 0 v 1 10 00 0 0 00
1
v 0 10 1 1 00 0 v 2 11 00 0 0 00
2
v 0 01 1 1 00 0 v 3 00 1 0 0 11
3
R== v 0 00 1 1 00 0 Q= v 4 11 1 1 0 11
4
v 0 00 0 1 00 0 v 5 11 1 1 1 11
5
v 0 01 1 1 11 1 v 6 00 00 0 0 11
6
v 0 01 1 1 11 1 v 7 00 00 0 0 11
7
в гг
Рисунокк 3.1.

35