Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 8 промежуточных версий 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>
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
−
В задаче поиска компонент сильной связности требуется разбить вершины ориентированного графа на непересекающиеся группы (компоненты), так что в каждой компоненты все вершины достижимы друг из друга по рёбрам графа (с учётом направления).
 
  
−
Пусть задан ориентированный граф <math>G=(V,E)</math> с вершинами <math>V= (v_1,v_2,...,v_n)</math> и рёбрами <math>E=(e_1,e_2,...,e_m)</math>.
+
1. Для каждой компоненты связности графа найти какое-либо остовное дерево <math>T</math>.
 +
2. Перенумеровать вершины <math>T</math> в порядке обратного обхода.
 +
 
 +
3. В порядке возрастания номера вершины выполнить следующие действия:
  
−
Путём между вершинами <math>u</math> и <math>v</math> называется последовательность рёбер <math>\pi_{uv}=(e_1,...,e_k)</math>, начинающаяся в вершине <math>u</math> и заканчивающаяся в вершине <math>v</math>, так что началом каждого следующего ребра служит конец предыдущего.
+
a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>
  
−
Если существует такой путь <math>\pi_{uv}</math>, то вершина <math>v</math> достижима из вершины <math>u</math>. Считается, что от вершины <math>u</math> к самой себе ведёт пустой путь <math>\pi_{uu}</math>, то есть каждая вершина достижима из самой себя. Непустой путь <math>\pi_{uu}</math> называется циклом (замкнутым обходом).
+
b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} }</math>
  
−
Ориентированный граф называется сильно связным, если всякая его вершина <math>v</math> достижима из любой другой его вершины <math>u</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>.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 20: Строка 46:
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
−
Последовательная сложность алгоритма составляет <math>O(m)</math>.
+
Последовательная сложность алгоритма составляет <math>O(|E|)</math>.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
Строка 34: Строка 60:
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
−
=== Локальность данных и вычислений ===
 
−
==== Локальность реализации алгоритма ====
 
−
===== Структура обращений в память и качественная оценка локальности =====
 
−
===== Количественная оценка локальности =====
 
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
−
=== Масштабируемость алгоритма и его реализации ===
+
=== Результаты прогонов ===
−
==== Масштабируемость алгоритма ====
 
−
==== Масштабируемость реализации алгоритма ====
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
−
=== Существующие реализации алгоритма ===
 
  
 
== Литература ==
 
== Литература ==
Строка 50: Строка 68:
  
 
[[Категория:Начатые статьи]]
 
[[Категория:Начатые статьи]]
 +
 +
[[en:Tarjan's algorithm for finding the bridges of a graph]]

Текущая версия на 17:52, 6 июля 2022


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 Литература

  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.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_Тарьяна_поиска_«мостов»_в_графе&oldid=29002