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

[непроверенная версия]

Версия 17:12, 18 ноября 2016

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Тарьяна ^[1] находит мосты в неориентированном графе за время $O(m)$ .

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

Последовательная сложность алгоритма составляет $O(m)$ .

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый поиск в ширину. Последующие вычисления также могут быть параллелизованы.

Параллельный алгоритм Тарьяна-Вишкина^[2] основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

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.

[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.

[1]

[2]

@@ Строка 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>. Компонентой сильной связности ориентированного графа называется любой максимальный по включению сильно связный подграф.
 === Вычислительное ядро алгоритма ===