Алгоритм Тарьяна поиска «мостов» в графе: различия между версиями

[непроверенная версия]

Версия 17:36, 18 ноября 2016

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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

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.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

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

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

1.7 Информационный граф

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

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

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

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

↑ Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.
↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

[1] Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.

[2] Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

[1]

[2]

@@ Строка 3: / Строка 3: @@
 '''Алгоритм Тарьяна''' <ref>Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.</ref> находит [[Связность в графах|мосты]] в неориентированном графе за время <math>O(m)</math>.
+Пусть <math>T</math> – дерево в одной из компонент связности графа <math>G.</math>
+Выберем корневую вершину  и введём обозначения:
+•	<math>v->w</math>, если в дереве  имеется <math>e=(v,w)</math>, и вершина  находится дальше от корня <math>r</math>, чем вершина <math>v</math>. Далее будем считать дерево <math>T</math> направленным графом, содержащим рёбра указанного вида.
+•	<math>v=>w</math>, если в ориентированном дереве <math>T</math> имеется направленный путь от <math>v</math> к <math>w</math>.
+•	<math>v***w</math>, если в графе <math>G</math> существует ребро <math>e=(v,w)</math>, не принадлежащее дереву <math>T</math>.
+•	<math>N(v)</math> – нумерация вершин в обратном порядке обхода вершин (post-order).
+•	<math>D(v)</math> – количество потомков вершины <math>v</math> в ориентированном дереве <math>T</math>, то есть .
+•	<math>S(v)={w | v => w \or \exist u(v => u \and u***w}</math>
+•	<math>L(v) = \min S(v)</math>, <math>H(v) = \max S(v)</math>.
+Алгоритм Тарьяна основан на следующем свойстве: ребро  является мостом тогда и только тогда, когда <math>v->w, H(w) <= N(w), L(w) > N(w) - D(w)</math>
 === Математическое описание алгоритма ===