Использование обхода в глубину для поиска точек сочленения — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показана 21 промежуточная версия 10 участников) | |||
Строка 1: | Строка 1: | ||
− | Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|)</tex> | + | {{Задача |
+ | |definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|).</tex> | ||
+ | }} | ||
== Алгоритм == | == Алгоритм == | ||
− | + | === Описание алгоритма === | |
− | + | Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины графа; обозначим её через <tex>root</tex>. Заметим следующий факт: | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | <tex> | + | * Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины <tex>v</tex>. Тогда, если текущее ребро (<tex>v</tex>,<tex>to</tex>) таково, что из вершины <tex>to</tex> и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину <tex>v</tex> или какого-либо её предка, то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из <tex>v</tex> в <tex>to</tex>, кроме как спуск по ребру (<tex>v</tex>,<tex>to</tex>) дерева обхода в глубину.) |
− | |||
− | |||
− | |||
+ | Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину. | ||
− | [[Файл: | + | [[Файл:Joint_point_2_rsz.png|280px|thumb|left| <font color=red>Красным</font> цветом обозначены точки сочленения<br><font color=blue>Синим</font> — ребра по которым идет DFS]] |
Пусть <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>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] | + | Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < tin[u]</tex>. |
− | Таким образом, если для текущей вершины <tex> | + | Таким образом, если для текущей вершины <tex>u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \geqslant tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является. |
<br clear="all"> | <br clear="all"> | ||
− | == | + | === Псевдокод === |
− | '''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения | + | '''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе </font> |
visited = array[n, ''false''] | visited = array[n, ''false''] | ||
Строка 36: | Строка 29: | ||
time = time + 1 | time = time + 1 | ||
up[v] = tin[v] = time | up[v] = tin[v] = time | ||
− | visited[v] = ''true'' | + | visited[v] = ''true'' |
+ | count = 0 | ||
'''for''' u: (v, u) '''in''' G | '''for''' u: (v, u) '''in''' G | ||
'''if''' u == p | '''if''' u == p | ||
− | continue | + | '''continue''' |
− | '''if''' visited[u] | + | '''if''' visited[u] |
up[v] = min(up[v], tin[u]) | up[v] = min(up[v], tin[u]) | ||
'''else''' | '''else''' | ||
dfs(u, v) | dfs(u, v) | ||
− | up[v] = min(up[v], | + | count = count + 1 |
− | '''if''' up[ | + | up[v] = min(up[v], up[u]) |
+ | '''if''' p != -1 '''and''' up[u] >= tin[v] | ||
v — cutpoint | v — cutpoint | ||
− | '''if''' | + | '''if''' p == -1 '''and''' count >= 2 |
v — cutpoint | v — cutpoint | ||
'''for''' i = 1 '''to''' n | '''for''' i = 1 '''to''' n | ||
− | '''if''' visited[i] | + | '''if''' '''not''' visited[i] |
dfs(i, -1) | dfs(i, -1) | ||
+ | |||
+ | === Доказательство корректности === | ||
+ | {{Теорема | ||
+ | |statement= | ||
+ | Пусть <tex>T</tex> — дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> — корень <tex>T</tex>. | ||
+ | * Вершина <tex>u \ne root</tex> — точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> — сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>. | ||
+ | * <tex>root</tex> — точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину. | ||
+ | |proof= | ||
+ | [[Файл:Joint_point_1.png|48px |thumb| | Рисунок к <tex>\Leftarrow</tex>]] | ||
+ | <tex>\Leftarrow</tex> | ||
+ | |||
+ | #Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что не существует пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> — предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> — предпоследняя вершина на этом пути, <tex>w</tex> — потомок <tex>v</tex>. <tex>(w, x)</tex> — не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию. | ||
+ | #Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения. | ||
+ | |||
+ | <tex>\Rightarrow</tex> | ||
+ | #Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> — связный <tex>\Rightarrow u</tex> — не точка сочленения. | ||
+ | #Пусть <tex>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочленения. | ||
+ | }} | ||
+ | |||
+ | <br clear="all"> | ||
+ | |||
+ | === Асимптотика === | ||
+ | Оценим время работы алгоритма. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>. Такое же, как у [[Обход в глубину, цвета вершин|обхода в глубину]]. | ||
== См. также == | == См. также == |
Текущая версия на 19:28, 4 сентября 2022
Задача: |
Дан связный неориентированный граф . Найти все точки сочленения в за время |
Алгоритм
Описание алгоритма
Запустим обход в глубину из произвольной вершины графа; обозначим её через . Заметим следующий факт:
- Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины . Тогда, если текущее ребро ( , ) таково, что из вершины и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину или какого-либо её предка, то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из в , кроме как спуск по ребру ( , ) дерева обхода в глубину.)
Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.
Пусть
— время входа поиска в глубину в вершину . Через обозначим минимум из времени захода в саму вершину , времен захода в каждую из вершин , являющуюся концом некоторого обратного ребра , а также из всех значений для каждой вершины , являющейся непосредственным сыном в дереве поиска.Тогда из вершины
или её потомка есть обратное ребро в её предка такой сын , что .Таким образом, если для текущей вершины
существует непосредственный сын : , то вершина является точкой сочленения, в противном случае она точкой сочленения не является.
Псевдокод
function findCutPoints(G[n]: Graph): // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе visited = array[n, false] function dfs(v: int, p: int): time = time + 1 up[v] = tin[v] = time visited[v] = true count = 0 for u: (v, u) in G if u == p continue if visited[u] up[v] = min(up[v], tin[u]) else dfs(u, v) count = count + 1 up[v] = min(up[v], up[u]) if p != -1 and up[u] >= tin[v] v — cutpoint if p == -1 and count >= 2 v — cutpoint for i = 1 to n if not visited[i] dfs(i, -1)
Доказательство корректности
Теорема: |
Пусть обхода в глубину, — корень .
— дерево
|
Доказательство: |
|
Асимптотика
Оценим время работы алгоритма. Процедура ребра . Всего таких ребер для всех вершин в графе , следовательно, время работы алгоритма оценивается как . Такое же, как у обхода в глубину.
вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такиеСм. также
Источники информации
- Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Лань, 2010. — 368 с. — ISBN 978-5-8114-1068-2
- MAXimal :: algo :: Поиск точек сочленения