Алгоритм Пурдома

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Пурдома находит транзитивное замыкание ориентированного графа за время [math]O(\mu n)[/math], где [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности этого графа.

1.2 Математическое описание

Алгоритм основан на следующих свойствах:

1. Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то его транзитивное замыкание [math]G^+[/math] содержит рёбра [math](v, w)[/math] и [math](w, v)[/math].
2. Если вершины [math]x[/math] и [math]y[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], а вершины [math]z[/math] и [math]t[/math] – другой, то рёбра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math](y, t)[/math] принадлежат или не принадлежат транзитивному замыканию [math]G^+[/math] одновременно.

Таким образом, поиск транзитивного замыкания графа [math]G[/math] сводится к поиску транзитивного замыкания ациклического графа [math]\tilde G[/math], полученного из [math]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину. Транзитивное замыкание ациклического графа вычисляется с использованием топологической сортировки вершин графа.