AlgoList

[Igor Tuphanov]

Везде пишется, что мосты, точки сочленения и проч. можно найти за O(E) с помощью поиска в глубину (DFS), но нигде толком не написано как их искать, даже у Кристофидеса!

К стати, задачка из той же серии: дан связанный граф, необходимо указать порядок, в котором надо удалять его вершины так, чтобы он оставался все время связным. Ее можно решить за O(VE), но это медленно.

[Alexey Ilyichev]

Это делается с помощью динамического программирования на глубинном остовном дереве. Глубинное остовное дерево обладает одним интересным свойством - всё рёбра, которые в него не вошли, соединяют две вершины, одна из которых является предком другой. Поэтому работает следующий алгоритм (на примере мостов):
Обходим это дерево в глубину, поднимаясь вверх из определённой вершины пытаемся предположить, является ли ребро, соединяющее эту вершину с её отцом мостом. Для вершины вычисляем число, равное высоте (высота - удалёность вершины от корня, если смотреть по остовному дереву), на которую можно подняться из этой вершины не проходя по ребру, которое непосредственно над ней, но использовав ровно одно ребро, не вошедшее в остовное дерево. Эта высота вычисляется как минимум из таких высот для сыновей (у них уже всё посчитано, т.к. мы это делаем на обратном пути), а потом перебираем рёбра, не вошедшие в дерево, выходящие из данной вершины. Если результат можно улучшить с помощью такого ребра - улучшаем.

После чего, если эта высота оказывается меньше высоты рассматриваемой вершины, то ребро, ведущее к предку мостом не является, если равна - является (больше она быть не может в силу определения).

Рёбра, не вошедшие в глубинное остовное дерево мостами не являются заведомо :)

Всё работает в сумме за O(E). Задача про точки сочленения решается абсолютно аналогично, только там для вершины нужно смотреть не её данные, а данные её сыновей.

[az]

Расскажите пожалуйста, как пишется DFS?

[Igor Tuphanov]

Пишется рекурсивная процедура.

На входе : номер вершины (v)
На выходе: -
Procedure DFS(v : вершина)
Пометить v, как посещенную.
Для всех u смежных с v делать
Если u не посещена тогда DFS(u)

Такая рекурсия обойдет все вершины в порядке обхода в глубину. То, что я написал - болванка, она просто обходит веришины. На эту болванку можно что-нибудь навесить.



К стати, за мосты большой respect. Приятно читать то, что понимаешь.

[az]

Спасибо!

[Sarah]

а можно ли быстро найти мосты или точки сочленения в двудольном графе?

[Alexey Ilyichev]

Так они в произвольном за O(N+M) ищутся - куда ж быстрее-то? :)

[Sarah]

Что то я ничего не поняла...
Если мост- это ребро, при удалении которого граф становится не связным

Вы пишете про поиск моста в дереве... Если дерево- это граф без циклов, то удаление любого ребра делает его не связным...
Тогда зачем искать мосты в дереве? Вообще ничего не поняла

[Igor Tuphanov]

Мосты ищутся в графе. Но если мы запустим на графе поиск в глубину, то несложно доказать, что ребра, по которым он пройдется включают в себя мосты графа (ведь если это мост мы не можем иначе добраться за тем, что за ним). Ребра, по которым пройдется поиск в глубину (DFS) образуют на графе дерево (подграф включающий все вершины, попросту - остовное дерево). Вот про него и идет речь.