Page 19 - 4387

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

n
2
j , .
A i, j = ∑ a ( i, k ⋅a ) (2.3)
k
k =1
Права частина формули рівна 1 тоді і тільки тоді, коли

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

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

2 =a ·a +a ·a +a ·a +a ·a +a ·a +a ·a =0·1+
4,6
3,6
6,6
3,5
5,6
3,4
3,6
3,3
3,1
1,6
3,2
2,6
3,6
+1·1+0·1+0·0+1·1+1·0=2.
2
Проаналізуємо детальніше матрицю А .
Так 1, що стоїть на перетині другого рядка і четвертого
2
стовпця матриці А (елемент 2 ), вказує на існування одного
2,4
шляху завдовжки 2 з вершини v до вершини v . Дійсно, як
2
4
18