304
правки
Изменения
м
Из этого определения можно легко понять, если {{Теорема|statement=Если <tex>R</tex> - отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение
→Построение транзитивного замыкания
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <tex>R</tex> как отношение <tex>T</tex> такое, что <tex>aTb</tex> тогда и только тогда, когда существуют <tex>x_1, x_2, ..., x_n</tex> такие, что <tex>aRx_1</tex>, <tex>x_1Rx_2</tex>, <tex>x_2Rx_3</tex>, ..., <tex>x_{n-1}Rx_n</tex>, <tex>x_nRb</tex>, то есть существует путь из вершины <tex>a</tex> в вершину <tex>b</tex> по рёбрам графа отношения.
:<tex>T = \bigcup\limits_{i = 1}^{n} R^i</tex>.
|proof=Действительно, если по рёбрам графа есть путь длины <tex>l > n</tex>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как пока она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <tex>n</tex> можно "выкинуть" из объединения.}}
Для построения транзитивного отношения множества, заданного матрицей смежности, используется [[алгоритм Флойда — Уоршелла]].
