Алгоритм Тарьяна поиска «мостов» в графе

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

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

Алгоритм Тарьяна находит мосты в неориентированном графе за время [math]\displaystyle{ O(m) }[/math].

Пусть [math]\displaystyle{ T }[/math] – дерево в одной из компонент связности графа [math]\displaystyle{ G. }[/math]

Выберем корневую вершину и введём обозначения:

• [math]\displaystyle{ v-\gt w }[/math], если в дереве имеется [math]\displaystyle{ e=(v,w) }[/math], и вершина находится дальше от корня [math]\displaystyle{ r }[/math], чем вершина [math]\displaystyle{ v }[/math]. Далее будем считать дерево [math]\displaystyle{ T }[/math] направленным графом, содержащим рёбра указанного вида.

• [math]\displaystyle{ v=\gt w }[/math], если в ориентированном дереве [math]\displaystyle{ T }[/math] имеется направленный путь от [math]\displaystyle{ v }[/math] к [math]\displaystyle{ w }[/math].

• [math]\displaystyle{ v***w }[/math], если в графе [math]\displaystyle{ G }[/math] существует ребро [math]\displaystyle{ e=(v,w) }[/math], не принадлежащее дереву [math]\displaystyle{ T }[/math].

• [math]\displaystyle{ N(v) }[/math] – нумерация вершин в обратном порядке обхода вершин (post-order). • [math]\displaystyle{ D(v) }[/math] – количество потомков вершины [math]\displaystyle{ v }[/math] в ориентированном дереве [math]\displaystyle{ T }[/math], то есть . • [math]\displaystyle{ S(v)={w | v =\gt w \or \exist u(v =\gt u \and u***w} }[/math]

• [math]\displaystyle{ L(v) = \min S(v) }[/math], [math]\displaystyle{ H(v) = \max S(v) }[/math].

Алгоритм Тарьяна основан на следующем свойстве: ребро является мостом тогда и только тогда, когда [math]\displaystyle{ v-\gt w, H(w) \lt = N(w), L(w) \gt N(w) - D(w) }[/math]

Математическое описание алгоритма

1. Для каждой компоненты связности графа найти какое-либо остовное дерево [math]\displaystyle{ T }[/math]. 2. Перенумеровать вершины [math]\displaystyle{ T }[/math] в порядке обратного обхода.

3. В порядке возрастания номера вершины выполнить следующие действия:

a. [math]\displaystyle{ D(v) := 1+ \sum_{v \rightarrow w}D(w) }[/math]

b. [math]\displaystyle{ L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} } }[/math]

c. [math]\displaystyle{ H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} } }[/math]

d. Пометить ребро [math]\displaystyle{ v \rightarrow w }[/math] мостом, если [math]\displaystyle{ H(w)\lt =N(w) }[/math] и [math]\displaystyle{ L(w)\gt N(w)-D(w) }[/math].

Последовательная сложность алгоритма

Последовательная сложность алгоритма составляет [math]\displaystyle{ O(m) }[/math].

Ресурс параллелизма алгоритма

Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый поиск в ширину. Последующие вычисления также могут быть параллелизованы.

Параллельный алгоритм Тарьяна-Вишкина основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.