Алгоритм Тарьяна поиска «мостов» в графе - История изменений

ASA в 14:52, 6 июля 2022

2022-07-06T14:52:14Z

← Предыдущая версия		Версия от 14:52, 6 июля 2022
Строка 60:		Строка 60:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	== Литература ==		== Литература ==

ASA: /* Свойства и структура алгоритма */

2022-07-06T14:50:08Z

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

← Предыдущая версия		Версия от 14:50, 6 июля 2022
Строка 20:		Строка 20:
	• <math>D(v)</math> – количество потомков вершины <math>v</math> в ориентированном дереве <math>T</math>, то есть.		• <math>D(v)</math> – количество потомков вершины <math>v</math> в ориентированном дереве <math>T</math>, то есть.

	• <math>S(v)={w \| v => w \or \~~exist~~ u(v => u \~~and~~ u***w}</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>L(v) = \min S(v)</math>, <math>H(v) = \max S(v)</math>.

ASA: /* Общее описание алгоритма */

2022-07-06T12:59:31Z

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

← Предыдущая версия		Версия от 12:59, 6 июля 2022
Строка 17:		Строка 17:

	• <math>N(v)</math> – нумерация вершин в обратном порядке обхода вершин (post-order).		• <math>N(v)</math> – нумерация вершин в обратном порядке обхода вершин (post-order).
	• <math>D(v)</math> – количество потомков вершины <math>v</math> в ориентированном дереве <math>T</math>, то есть .
			• <math>D(v)</math> – количество потомков вершины <math>v</math> в ориентированном дереве <math>T</math>, то есть.

	• <math>S(v)={w \| v => w \or \exist u(v => u \and u***w}</math>		• <math>S(v)={w \| v => w \or \exist u(v => u \and u***w}</math>

ASA в 13:58, 14 марта 2018

2018-03-14T13:58:41Z

← Предыдущая версия		Версия от 13:58, 14 марта 2018
Строка 74:		Строка 74:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Tarjan's algorithm for finding the bridges of a graph]]

ASA в 14:18, 6 марта 2018

2018-03-06T14:18:55Z

← Предыдущая версия		Версия от 14:18, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Elijah: /* Последовательная сложность алгоритма */

2017-08-15T11:19:11Z

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

← Предыдущая версия		Версия от 11:19, 15 августа 2017
Строка 42:		Строка 42:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	Последовательная сложность алгоритма составляет <math>O(m)</math>.		Последовательная сложность алгоритма составляет <math>O(\|E\|)</math>.

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

Teplov: /* Математическое описание алгоритма */

2016-11-18T15:05:21Z

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

← Предыдущая версия		Версия от 15:05, 18 ноября 2016
Строка 23:		Строка 23:

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

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

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

Teplov: /* Общее описание алгоритма */

2016-11-18T14:36:59Z

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

← Предыдущая версия		Версия от 14:36, 18 ноября 2016
Строка 3:		Строка 3:

	'''Алгоритм Тарьяна''' <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 \or \exist u(v => u \and 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>

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

Teplov: /* Математическое описание алгоритма */

2016-11-18T14:12:23Z

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

← Предыдущая версия		Версия от 14:12, 18 ноября 2016
Строка 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>. Компонентой сильной связности ориентированного графа называется любой максимальный по включению сильно связный подграф.

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

Teplov: /* Математическое описание алгоритма */

2016-11-18T14:11:35Z

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

@@ Строка 5: / Строка 5: @@
 === Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===