Алгоритм Тарьяна поиска «мостов» в графе: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
ASA (обсуждение | вклад) Нет описания правки |
Teplov (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
В задаче поиска компонент сильной связности требуется разбить вершины ориентированного графа на непересекающиеся группы (компоненты), так что в каждой компоненты все вершины достижимы друг из друга по рёбрам графа (с учётом направления). | |||
Пусть задан ориентированный граф <math>G=(V,E)</math> с вершинами <math>V= (v_1,v_2,...,v_n)</math> и рёбрами <math>E=(e_1,e_2,...,e_m)</math>. | |||
Путём между вершинами <math>u</math> и <math>v</math> называется последовательность рёбер <math>\pi_{uv}=(e_1,...,e_k)</math>, начинающаяся в вершине <math>u</math> и заканчивающаяся в вершине <math>v</math>, так что началом каждого следующего ребра служит конец предыдущего. | |||
Если существует такой путь <math>\pi_{uv}</math>, то вершина <math>v</math> достижима из вершины <math>u</math>. Считается, что от вершины <math>u</math> к самой себе ведёт пустой путь <math>\pi_{uu}</math>, то есть каждая вершина достижима из самой себя. Непустой путь <math>\pi_{uu}</math> называется циклом (замкнутым обходом). | |||
Ориентированный граф называется сильно связным, если всякая его вершина <math>v</math> достижима из любой другой его вершины <math>u</math>. Компонентой сильной связности ориентированного графа называется любой максимальный по включению сильно связный подграф. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Версия от 14:11, 18 ноября 2016
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Тарьяна [1] находит мосты в неориентированном графе за время [math]\displaystyle{ O(m) }[/math].
Математическое описание алгоритма
В задаче поиска компонент сильной связности требуется разбить вершины ориентированного графа на непересекающиеся группы (компоненты), так что в каждой компоненты все вершины достижимы друг из друга по рёбрам графа (с учётом направления).
Пусть задан ориентированный граф [math]\displaystyle{ G=(V,E) }[/math] с вершинами [math]\displaystyle{ V= (v_1,v_2,...,v_n) }[/math] и рёбрами [math]\displaystyle{ E=(e_1,e_2,...,e_m) }[/math].
Путём между вершинами [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] называется последовательность рёбер [math]\displaystyle{ \pi_{uv}=(e_1,...,e_k) }[/math], начинающаяся в вершине [math]\displaystyle{ u }[/math] и заканчивающаяся в вершине [math]\displaystyle{ v }[/math], так что началом каждого следующего ребра служит конец предыдущего.
Если существует такой путь [math]\displaystyle{ \pi_{uv} }[/math], то вершина [math]\displaystyle{ v }[/math] достижима из вершины [math]\displaystyle{ u }[/math]. Считается, что от вершины [math]\displaystyle{ u }[/math] к самой себе ведёт пустой путь [math]\displaystyle{ \pi_{uu} }[/math], то есть каждая вершина достижима из самой себя. Непустой путь [math]\displaystyle{ \pi_{uu} }[/math] называется циклом (замкнутым обходом).
Ориентированный граф называется сильно связным, если всякая его вершина [math]\displaystyle{ v }[/math] достижима из любой другой его вершины [math]\displaystyle{ u }[/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.