Page 36 - 4336

Розв'язок.

Множини досяжностей знаходимо наступним чином:

R(v )={v }{v , v }{v }{v }={v , v , v , v };
4
1
2
5
2
1
5
4
1
5
R(v )={v }{v }{v }={v , v , v };
5
2
5
2
4
2
4
R(v )={v }{v }{v }={v , v , v };
5
4
4
3
3
3
5
R(v )={v }{v }={v , v };
4
4
5
4
5
R(v )={v }{v }={v };
5
5
5
5
R(v )={v }{v , v }{v , v }{v , v , v }={v , v , v , v , v };
3
4
6
3
6
5
7
4
7
3
6
5
6
7
R(v )={v }{v , v }{v , v , v }{v , v }={v , v , v , v , v }.
4
5
3
4
7
3
6
5
4
6
7
6
7
7
Матриця досяжності R має вигляд, як показано на рис. 3.1, в.
Матрицю досяжності можна побудувати по матриці суміжності А
+
(рис. 3.1, б,), формуючи множини Т (v ) для кожної вершини v .
i
i
3.2 Контрдосяжність на графах
Матриця контрдосяжності Q=[q ], i, j=1, 2, ..., n, де n –
i,j
кількість вершин графа, а кожний елемент визначається
наступним чином:
1) q =1, якщо з вершина v можна досягти вершину v ;
i,j
j
i
2) q =0 у іншому випадку.
i,j
Контрдосяжною множиною Q(v ) є множина таких вершин,
i
що з будь-якої вершини цієї множини можна досягти вершину v .
i
Аналогічно побудові досяжної множини R(v ) можна записати
i
вираз для Q(v ):
i
-k
-1
-2
Q(v )={v }Г (v )Г (v )Г (v ). (3.2)
i
i
i
i
i
Таким чином, Q(v ) – це є не що інше, як зворотне
i
-
транзитивне замикання вершини v , тобто Q(v )=Т (v ). З визначень
i
i
i
очевидно, що стовпець v матриці Q(v ) (в якому q =1, якщо
i
i,j
i
v Q(v ), і q =0 в іншому випадку) співпадає з рядком v матриці
i,j
j
i
i
36