Алгоритм Тарьяна поиска «мостов» в графе: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Teplov (обсуждение | вклад) |
Teplov (обсуждение | вклад) |
||
| Строка 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>. | '''Алгоритм Тарьяна''' <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> | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Версия от 14:36, 18 ноября 2016
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Тарьяна [1] находит мосты в неориентированном графе за время [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]
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма составляет [math]\displaystyle{ O(m) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый поиск в ширину. Последующие вычисления также могут быть параллелизованы.
Параллельный алгоритм Тарьяна-Вишкина[2] основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ 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.