Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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





Дата публикования: 2014-11-03; Прочитано: 404 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...