Определение путей в графе

a b

g

c

f

e d

Требуемые результаты получаются путем перемножения матриц смежности графа.

M - матрица смежностей, показывает пути длиной в 1 в данном графе.

	a	b	c	d	e	f	g
a
b
c
d
e
f
g

	a	b	c	d	e	f	g
a
b
c
d
e
f
g

M M

Матрица M² дает все пути длиной в 2

	a	b	c	d	e	f	g
a
b
c
d
e
f
g

Матрица Мⁿ - пути длиной в n.

Если Мⁱ - нулевая матрица, то наибольший путь в графе имеет длину i - 1.

Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц

M^* = M¹ È M² È M³ ...

Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.