Изменения

Перейти к: навигация, поиск

Транзитивное замыкание

222 байта добавлено, 22:30, 28 сентября 2010
м
Нет описания правки
Действительно, если по рёбрам графа есть путь длины <math>l > n</math>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <math>n</math> можно "выкинуть" из объединения.
 
Для построения транзитивного отношения множества, заданного матрицей смежности, используется алгоритм Флойда-Уоршала.
304
правки

Навигация