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

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

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

Алгоритм Тарьяна находит мосты в неориентированном графе за время $O(m)$.

Пусть $T$ – дерево в одной из компонент связности графа $G.$

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

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

• $v=\gt w$, если в ориентированном дереве $T$ имеется направленный путь от $v$ к $w$.

• $v***w$, если в графе $G$ существует ребро $e=(v,w)$, не принадлежащее дереву $T$.

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

• $L(v) = \min S(v)$, $H(v) = \max S(v)$.

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

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

1. Для каждой компоненты связности графа найти какое-либо остовное дерево $T$. 2. Перенумеровать вершины $T$ в порядке обратного обхода.

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

a. $D(v) := 1+ \sum_{v \rightarrow w}D(w)$

b. $L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }$

c. $H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }$

d. Пометить ребро $v \rightarrow w$ мостом, если $H(w)\lt =N(w)$ и $L(w)\gt N(w)-D(w)$.

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

Последовательная сложность алгоритма составляет $O(|E|)$.

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

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

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