-
Определение путей в графе. Пример.
a
b
g
c
f
e
d
Требуемые результаты получаются путем перемножения матриц смежности графа.
M
a b c
d
e f
g a 0 0 1 1 0 0 1 b 0 0 0 0 0 0 0 c 0 0 0 0 0 0 0 d 0 1 0 0 0 0 0 e 0 1 0 0 0 0 1 f 0 1 1 1 0 0 0 g 0 0 0 0 0 0 0
М2
a b c d e f g a 0 0 1 1 0 0 1 b 0 0 0 0 0 0 0 c 0 0 0 0 0 0 0 d 0 1 0 0 0 0 0 e 0 1 0 0 0 0 1 f 0 1 1 1 0 0 0 g 0 0 0 0 0 0 0 М2
|
|
a |
b |
c |
d |
e |
f |
g |
|
a |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
b |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
c |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
d |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
e |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
f |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
g |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
М
|
|
a |
b |
c |
d |
e |
f |
g |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
a |
0 |
1 |
0 |
0 |
0 |
0 |
1
a b c
d
e f
g a 0 1 0 0 0 0 0 b 0 0 0 0 0 0 0 c 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 f 0 1 0 0 0 0 0 g 0 0 0 0 0 0 0
М4 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
b |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
c |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
d |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
e |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
f |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
g |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
М3
Матрица M2 дает все пути длиной в 2
Матрица Мn - пути длиной в n.
Если Мi - нулевая матрица, то наибольший путь в графе имеет длину i - 1.
Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц
M* = M1 M2 M3 ...
Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.