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

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

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

Содержание

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

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

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

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

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

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

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

• [math]v=\gt 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 =\gt w \or \exist u(v =\gt u \and u***w}[/math]

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

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

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

1.3 Вычислительное ядро алгоритма

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

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

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

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

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>
 === Математическое описание алгоритма ===