Изменения

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