Page 37 - 4336

T
T
R(v ), тобто Q(v )=R(v ) , де R(v ) – матриця, транспонована до
i
i
i
i
матриці досяжності R(v ).
i
Матриця контрдосяжності для графа, наведеного на рис. 3.1,
а, показана на рис. 3.1, г. Слід зазначити, що оскільки всі
елементи матриць R(v ) і Q(v ) рівні 1 або 0, то кожен рядок можна
i
i
зберігати в двійковій формі.

3.3 Матричний метод знаходження шляхів у графах

Матриця суміжності повністю визначає структуру графа.

Зведемо матрицю суміжності в квадрат за правилами математики.

2
Кожен елемент матриці А визначається за формулою:
n
2
A i, j   a( i, k a k j , ) . (3.3)
k 1

Права частина формули рівна 1 тоді і тільки тоді, коли

обидва числа a та a рівні 1, інакше він рівний 0. Оскільки з
i,k
k,j
рівності a =a =1 слідує існування шляху довжини 2 з вершини v
k,j
i
i,k
2
у вершину v , що проходить через вершину v , то елементи a
i,j
k
j
2
матриці А рівні числу шляхів довжини 2, що ведуть з вершини v
i
в v .
j
На рис. 3.2, б представлена матриця суміжності графа,
зображеного на рис. 3.2, а. Результат зведення матриці
2
суміжності в квадрат А показаний на рис. 3.2, в.

Для прикладу, запишемо формулу для знаходження елемент
2
a 2 3,6 матриці А :

a 2 3,6 =a ·a +a ·a +a ·a +a ·a +a ·a +a ·a =0·1+
3,5
3,1
6,6
3,6
5,6
4,6
3,2
2,6
3,3
3,6
3,4
1,6
+1·1+0·1+0·0+1·1+1·0=2.
2
Проаналізуємо детальніше матрицю А .
37