2014-02-09
1309
По матрице смежности можно определить, сколько различных путей существует между i -той и j - той вершинами длиной в к единиц. Для этого необходимо определить матрицу 
, где 
- матрица смежности.
Если элемент 
матрицы :
- между i -той и j - той вершины не существует пути длиной в к единиц;
- между i -той и j - той вершины существуют 
различных путей длиной в к единиц;
Если - нулевая матрица, это означает, что графе нет путей в к единиц, а максимальный путь – это путь длиной в (к -1) единиц.
