Алгоритм Тарьяна поиска «мостов» в графе: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) (Общее описание алгоритма) |
ASA (обсуждение | вклад) |
||
| (не показано 11 промежуточных версий 4 участников) | |||
| Строка 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>. | ||
| + | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| − | Последовательная сложность алгоритма составляет <math>O( | + | Последовательная сложность алгоритма составляет <math>O(|E|)</math>. |
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый [[Поиск в ширину (BFS)|поиск в ширину]]. Последующие вычисления также могут быть параллелизованы. | Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый [[Поиск в ширину (BFS)|поиск в ширину]]. Последующие вычисления также могут быть параллелизованы. | ||
| − | Параллельный [[Алгоритм Тарьяна поиска компонент двусвязности|алгоритм Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на аналогичных вычислениях и может быть адаптирован для поиска мостов. | + | Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритм Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на аналогичных вычислениях и может быть адаптирован для поиска мостов. |
| − | === | + | === Входные и выходные данные алгоритма === |
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
| − | === Возможные способы и особенности реализации | + | === Результаты прогонов === |
| − | === | ||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | + | ||
== Литература == | == Литература == | ||
| + | <references /> | ||
| − | + | [[Категория:Начатые статьи]] | |
| + | |||
| + | [[en:Tarjan's algorithm for finding the bridges of a graph]] | ||
Текущая версия на 17:52, 6 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 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 \lor \exists u(v =\gt u \land 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. Для каждой компоненты связности графа найти какое-либо остовное дерево [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)\lt =N(w)[/math] и [math]L(w)\gt N(w)-D(w)[/math].
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма составляет [math]O(|E|)[/math].
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый поиск в ширину. Последующие вычисления также могут быть параллелизованы.
Параллельный алгоритм Тарьяна-Вишкина[2] основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
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.
