Алгоритм Тарьяна поиска «мостов» в графе: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Teplov (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показано 7 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
{{level-a}} | |||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Тарьяна''' <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 \lor \exists u(v => u \land 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> | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
1. Для каждой компоненты связности графа найти какое-либо остовное дерево <math>T</math>. | |||
2. Перенумеровать вершины <math>T</math> в порядке обратного обхода. | |||
3. В порядке возрастания номера вершины выполнить следующие действия: | |||
a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math> | |||
b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }</math> | |||
c. <math> H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }</math> | |||
d. Пометить ребро <math>v \rightarrow w</math> мостом, если <math>H(w)<=N(w)</math> и <math>L(w)>N(w)-D(w)</math>. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| Строка 11: | Строка 46: | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Последовательная сложность алгоритма составляет <math>O( | Последовательная сложность алгоритма составляет <math>O(|E|)</math>. | ||
=== Информационный граф === | === Информационный граф === | ||
| Строка 25: | Строка 60: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== | === Результаты прогонов === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
| Строка 41: | Строка 68: | ||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
[[en:Tarjan's algorithm for finding the bridges of a graph]] | |||
Текущая версия от 14:52, 6 июля 2022
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Тарьяна [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 \lor \exists u(v =\gt u \land 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(|E|) }[/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.