Множество путей в графе

По матрице смежности можно определить, сколько различных путей существует между i -той и j - той вершинами длиной в к единиц. Для этого необходимо определить матрицу , где - матрица смежности.

Если элемент матрицы :

- между i -той и j - той вершины не существует пути длиной в к единиц;

- между i -той и j - той вершины существуют различных путей длиной в к единиц;

Если - нулевая матрица, это означает, что графе нет путей в к единиц, а максимальный путь – это путь длиной в (к -1) единиц.

Дата добавления: 2014-01-04