Page 102 - 4496

5,3 1 1 1 1 1

Група операцій пов'язана з операціями над матрицями
суміжності, що описують граф. Позначимо операцію,
зіставлену матричному множенню для графів G і H, як GH.

Розглянемо окремий випадок, коли G=H, тобто
2
операцію GG. Позначимо її як G .
У цьому випадку виходить матриця, (і,j)- я компонента
n
якої обчислюється за формулою   j,i      ,kk,i   j , де n
k 1
=А.
Результуюча матриця може містити значення більші, ніж
1, тобто результатом буде мультиграф. У цьому графі дуга (i,j)
має кратність, рівну числу шляхів довжини 2 між вершинами
а i і a j у графі G. На рис.3.19, а наведено граф G, для якого G 2
представлений на рис.3.19,б. У ньому дуга (2,5) має кратність
2, тому що між вершинами 2 і 5 два шляхи довжини 2– через
вершини 1 і 3.
3
Можна показати, що для графа G результатом буде
мультиграф, у якому між a i і a j буде стільки дуг, скільки
шляхів довжини 3 між цими вершинами у вихідному графі.
Виходить, якщо об'єднати всі ступені графа G
1
(вважаючи, що G =G) від 1 до нескінченності, то результатом
буде граф досяжності, описаний вище.

99