152
правки
Изменения
м
{{Теорема|statement=Ребро <tex>uv</tex> ведет из одной компоненты реберной двусвязности Воспользуемся ранее доказанной [[Использование обхода в другую, если оно является частью дерева <tex>dfs</tex>, и либо <tex>u</tex> - предок <tex>v</tex> и <tex>return(v) = enter(v)</tex>, либо <tex>v</tex> - предок <tex>u</tex> и <tex>return(u) = enter(u)</tex>.глубину для поиска мостов#Лемма |proof=Если ребро <tex>uv</tex> - обратное, образуется цикл, содержащий <tex>uv</tex>, поэтому <tex>uv</tex> не может являться мостом.Последнее равенство означает, что из <tex>v</tex> и ее потомков нельзя подняться выше <tex>v</tex> по дереву обхода, в том числе, и в <tex>u</tex>. Таким образом, между <tex>u</tex> и <tex>v</tex> существует лишь один путь - ребро <tex>uv</tex>, - и они принадлежат разным компонентам реберной двусвязностилеммой]].}}
Нет описания правки
Определим критерий перехода к новой компоненте.
Основываясь на этом, определим алгоритм окраски вершин графа. Путь Перешли по графу будет точно таким жемосту, как и в первом проходе, что гарантирует постоянность дерева <tex>dfs</tex> и определенных параметров вершин: <tex>enter</tex> и <tex>return</tex>следовательно началась новая компонента.
Псевдокод второго прохода:
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * <tex> O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.
== Однопроходный алгоритм ==
