69
правок
Изменения
Новая страница: «== Постановка задачи == Дан неориентированный граф <tex> G </tex>. Найти все мосты в <tex> G </tex> за вр…»
== Постановка задачи ==
Дан неориентированный граф <tex> G </tex>. Найти все мосты в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>
== Алгоритм ==
{{Теорема
|statement=
Пусть <tex> T </tex> - дерево обхода в глубину графа <tex> G</tex>. Ребро <tex> (u, v) </tex> является мостом тогда и только тогда, когда <tex> (u, v) \in T</tex> и из вершины <tex> v</tex> и любого ее потомка нет обратного ребра в вершину <tex> u</tex> или предка <tex> u </tex>
|proof=
}}
Дан неориентированный граф <tex> G </tex>. Найти все мосты в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>
== Алгоритм ==
{{Теорема
|statement=
Пусть <tex> T </tex> - дерево обхода в глубину графа <tex> G</tex>. Ребро <tex> (u, v) </tex> является мостом тогда и только тогда, когда <tex> (u, v) \in T</tex> и из вершины <tex> v</tex> и любого ее потомка нет обратного ребра в вершину <tex> u</tex> или предка <tex> u </tex>
|proof=
}}
