Изменения
Новая страница: «== Задача == Дан связный [[Основные определения…»
== Задача ==
Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]]. Требуется найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в нем.
== Алгоритм ==
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины <tex>root</tex> графа <tex>G(V, E)</tex>. Рассмотрим <tex>u \in V</tex>:
#<tex>u \ne root</tex>. Тогда, если найдётся такой потомок <tex>v</tex> вершины <tex>u</tex> в дереве поиска, что ни из него, ни из какого-либо его потомка нет ребра в предка вершины <tex>u</tex>, то вершина <tex>u</tex> будет являться точкой сочленения. В противном случае, вершина <tex>u</tex> не является точкой сочленения.
#<tex>u = root</tex>. <tex>u</tex> - точка сочленения <tex>\Leftrightarrow u</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.
Пусть <tex>tin[u]</tex> - время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.
Тогда, из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < tin[u]</tex>.
Таким образом, если для текущей вершины <tex>v \ne root \, \exists</tex> непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения; в противном случае она точкой сочленения не является.
== Реализация ==
bool used[];
int tin[];
int up[];
bool answer[]; //для каждой вершины содержится булево значение - является она точкой сочленения или нет. изначально все значения false
int time;
void dfs(int u, int prev)
{
used[u] = true;
tin[u] = up[u] = time++; //задание времени входа tin и начального значения up для вершины u
int count = 0; //счетчик количества детей вершины u в дереве обхода
for (v : uv из E)
{
if (v == prev)
continue;
if (used[v]) //v - предок вершины u, uv - обратное ребро
up[u] = min(up[u], tin[v]);
else //v - ребенок вершины u
{
++count;
dfs(v, u);
up[u] = min(up[u], up[v]);
if (up[v] >= tin[u])
answer[u] = true; //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения
}
}
if (p == -1) //является ли u корнем дерева обхода
answer[u] = (count > 1); //проверка количества детей у корня дерева
}
int main()
{
... //инициализация графа, выбор корня дерева обхода root
time = 0;
dfs(root, -1);
return 0;
}
Для поиска точек сочленения в несвязном графе, необходимо модифицировать функцию main следующим образом:
int main()
{
...
for (root из V)
if (!used[root])
{
time = 0;
dfs(root, -1);
}
return 0;
}
== Источники ==
[http://e-maxx.ru/algo/ MAXimal::algo]
Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]]. Требуется найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в нем.
== Алгоритм ==
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины <tex>root</tex> графа <tex>G(V, E)</tex>. Рассмотрим <tex>u \in V</tex>:
#<tex>u \ne root</tex>. Тогда, если найдётся такой потомок <tex>v</tex> вершины <tex>u</tex> в дереве поиска, что ни из него, ни из какого-либо его потомка нет ребра в предка вершины <tex>u</tex>, то вершина <tex>u</tex> будет являться точкой сочленения. В противном случае, вершина <tex>u</tex> не является точкой сочленения.
#<tex>u = root</tex>. <tex>u</tex> - точка сочленения <tex>\Leftrightarrow u</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.
Пусть <tex>tin[u]</tex> - время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.
Тогда, из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < tin[u]</tex>.
Таким образом, если для текущей вершины <tex>v \ne root \, \exists</tex> непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения; в противном случае она точкой сочленения не является.
== Реализация ==
bool used[];
int tin[];
int up[];
bool answer[]; //для каждой вершины содержится булево значение - является она точкой сочленения или нет. изначально все значения false
int time;
void dfs(int u, int prev)
{
used[u] = true;
tin[u] = up[u] = time++; //задание времени входа tin и начального значения up для вершины u
int count = 0; //счетчик количества детей вершины u в дереве обхода
for (v : uv из E)
{
if (v == prev)
continue;
if (used[v]) //v - предок вершины u, uv - обратное ребро
up[u] = min(up[u], tin[v]);
else //v - ребенок вершины u
{
++count;
dfs(v, u);
up[u] = min(up[u], up[v]);
if (up[v] >= tin[u])
answer[u] = true; //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения
}
}
if (p == -1) //является ли u корнем дерева обхода
answer[u] = (count > 1); //проверка количества детей у корня дерева
}
int main()
{
... //инициализация графа, выбор корня дерева обхода root
time = 0;
dfs(root, -1);
return 0;
}
Для поиска точек сочленения в несвязном графе, необходимо модифицировать функцию main следующим образом:
int main()
{
...
for (root из V)
if (!used[root])
{
time = 0;
dfs(root, -1);
}
return 0;
}
== Источники ==
[http://e-maxx.ru/algo/ MAXimal::algo]
