304
правки
Изменения
м
→Построение транзитивного замыкания
Действительно, если по рёбрам графа есть путь длины <math>l > n</math>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <math>n</math> можно "выкинуть" из объединения.
Для построения транзитивного отношения множества, заданного матрицей смежности, используется [[алгоритм Флойда-Уоршала— Уоршелла]].
== Свойства транзитивного замыкания ==
