![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
По матрице смежности можно определить, сколько различных путей существует между i -той и j - той вершинами длиной в к единиц. Для этого необходимо определить матрицу , где
- матрица смежности.
Если элемент матрицы
:
- между i -той и j - той вершины не существует пути длиной в к единиц;
- между i -той и j - той вершины существуют
различных путей длиной в к единиц;
Если - нулевая матрица, это означает, что графе нет путей в к единиц, а максимальный путь – это путь длиной в (к -1) единиц.
Дата публикования: 2014-11-03; Прочитано: 433 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!