Лекция: Определение путей в графе

a b

g

c

f

e d

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

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

M M

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

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

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

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

M* = M1 È M2 È M3 ...

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