Page 17 - 4387

є множиною вершин, які досяжні з вершини v за допомогою
i
шляхів довжини k.

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

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

+1
+k
+2
R(v )={v }∪Г (v )∪Г (v )∪... ∪Г (v ). (2.1)
i
i
i
i
i
Як бачимо, множина досяжних вершин R(v ) представляє
i
+
пряме транзитивне замикання вершини v , тобто R(v )=Т (v ).
i
i
i
Отже, для побудови матриці досяжності необхідно знайти
досяжні множини R(v ) для всіх вершин v ∈V, вважаючи, r =1,
i,j
i
i
якщо v ∈R(v ) та r =0 у іншому випадку.
j
i,j
i
Приклад 2.1. Для графа, наведеного на рис. 2.1 а, знайти
матрицю досяжності R.

Матриця досяжності
v v v v v v v
2
6
7
3
4
1
5
v 1 1 0 1 1 0 0
1
v 0 1 0 1 1 0 0
2
v 0 0 1 1 1 0 0
3
R= v 0 0 0 1 1 0 0
4
v 0 0 0 0 1 0 0
5
v 0 0 1 1 1 1 1
6
v 0 0 1 1 1 1 1
7
а б
Рисунок 2.1.

Розв'язок.

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

R(v )={v }∪{v , v }∪{v }∪{v }={v , v , v , v };
5
5
4
2
1
1
5
2
1
4
R(v )={v }∪{v }∪{v }={v , v , v };
2
2
2
4
5
4
5
16