42
правки
Изменения
пункты 1, 3, 4
== Алгоритм ==
В случае <b>ориентированного графа</b>. Произведём произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе {{---}} в чёрный. И , если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли циклнайден.
В случае <b>неориентированного графа</b> любое ребро представляется как два ребра {{, используя указанный алгоритм, мы перейдем по какому---}} прямое либо ребру в обратном направлении и обратноепопадем в серую вершину, что будет означать наличие цикла. Тогда мы посчитаемПроблема в том, что эти два ребра составляют циклпо определению [[Основные определения теории графов|цикла]] в неориентированном графе, что неверноодно и то же ребро не может содержаться в цикле дважды. Чтобы избежать этого, будем необходимо передавать еще один параметр поиска в глубину {{---}} вершину, из которой мы пришли. Теперь мы считаемможно считать, что нашли циклнайден, если вершина, в которую мы хотим пойти серая и не является вершиной, из которой мы пришли.
Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в стек. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.
== Доказательство ==
Пусть дан граф <tex>G</tex>. Запустим <tex>\mathrm{dfs}(G)</tex>. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <tex> v </tex>. Так как все серые вершины лежат в стеке рекурсии, то для них вершина <tex> v </tex> достижима, так как между соседними вершинами в стеке есть ребро. Тогда , если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины <tex> v </tex> существует путь в <tex> u </tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.
Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>\mathrm{dfs}(G)</tex> его всегда найдет. Пусть <tex> v </tex> {{---}} первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину <tex> u </tex> существует белый путь (они лежат на одном цикле), то по [[Лемма о белых путях|лемме о белых путях]] во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </tex>, то это ребро в серую вершину. Следовательно <tex>\mathrm{dfs}(G)</tex> нашел цикл.
Заметим, что, если в графе есть вершины с петлями, то алгоритм будет работать корректно, так как при запуске поиска в глубину из такой вершины, найдется ребро, ведущее в нее же, а значит эта петля и будет являться циклом.
== Реализация для случая ориентированного графа ==
print() <font color=darkgreen> // вывод ответа </font>
color[v] = <i>black</i>
== См. также ==
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Использование обхода в глубину для поиска мостов]]
== Источники информации ==
