Изменения
→Доказательство корректности алгоритма
# Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>;
# В <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>.<br>
Значит все дуги <tex> V' </tex> будут будут добавлены в стеке стек после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденный найденные до него (если таковые имеетсяимеются) будет извлечен уже извлечены из стека и помечены покрашены в свой цвет.<br>
'''Псевдокод:
dfs(<tex>v, parent</tex>)
dfs(<tex>v</tex>, -1)
<br>
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(V + E)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(E)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно Общее , общее время работы алгоритма <tex>O(V + E) + O(E) = O(V + E)</tex>
==Литература==
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
