МОСТЫ
Мост – такое ребро в графе, при удалении которого количество компонент связности в графе увеличивается.
Пример 1
.jpg)
Пример 2
.jpg)
Синим цветом обозначены ребра-мосты, разными цветам – разные компоненты связности, образованные после удаления ребер-мостов.
Мосты в графе можно искать за O(m*(n + m)), а именно: перебирать все ребра, и делать обходы графа, в котором мы не будем ходить по перебираемому ребру и при этом считать количество компонент связности. При их увеличении относительно начального кол-ва, запомним, что перебираемое ребро – мост.
Но есть более эффективный алгоритм, асимптотика которого O(n + m).
P.S. Далее все термины, которые имеют какое-либо отношение к графу-дереву, будут употребляться в значении для дерева обхода имеющегося у нас графа.
Для данного алгоритма введем некоторые определения:
time_in[v] – время захода обхода графа в вершину v.
up[v] – минимальный time_in из вершин, в которые можно прийти из вершины v или из потомков вершины v.
Научимся вычислять значения time_in и up. Мы будем вычислять их значения и искать мосты одновременно. Для этого будем делать обход графа в глубину. Заранее заведем какой-нибудь таймер. Одной единицей времени этого таймера будет один заход обхода в глубину в определенную вершину. При заходе в вершину зададим значение time_in равному значению таймера в текущий момент. Теперь зададим начальное значение up текущей вершины. Логично, что начальное значение будет равно time_in этой вершины. Далее при обходе ребер из текущей вершины мы будем обновлять значение up. По определению up предельно ясно, как это делать. Будем рассматривать 2 варианта:
1) Если вершина, в которую ведет ребро, все еще обрабатывается обходом в глубину (но не является предком текущей вершины), то если up текущей вершины больше, чем time_in вершины в которое ведет ребро, то обновим up.
2) Если вершина, в которую ведет ребро, еще не была посещена обходом в глубину, то запустимся от нее. В конце ее обработки, сравним up текущей вершины и up вершины, которую мы только что обработали. Если второй меньше, то обновим значение up в текущей вершине.
Тогда становится очевидным, когда ребро является мостом:
Пусть v-u – текущее ребро. Тогда v-u – мост, если up[u] > time_in[v] (проверку необходимо делать в пункте № 2). Докажем, что это действительно так. Чем меньше time_in, тем ближе вершина к корню дерева обхода. Следовательно, все потомки конкретной вершины будут иметь больший time_in, чем у этой вершины. Значит, если up[u] строго больше, чем time_in[v], то мы не сможем из поддерева, где корень – v, подняться выше вершины v, следовательно, из вершин, которые выше, чем v, нельзя добраться до потомков v, не используя при этом ребро v-u. А это значит, что без ребра v-u количество компонент связности в графе увеличиться, следовательно, v-u действительно является мостом.
ТОЧКИ СОЧЛЕНЕНИЯ
Точка сочленения – это такая вершина в графе, при удалении которой (а значит и удалении всех ребер, относящихся к этой вершине) количество компонент связности в графе увеличивается.
Пример 1
.jpg)
Синим цветом обозначены точки сочленения, разными цветам – разные компоненты связности, образованные после удаления точек сочленения.
Точки сочленения ищутся в графе аналогично мостам. Необходимо лишь определить условие, когда вершина является точкой сочленения.
Пусть мы рассматриваем ребро v-u. Тогда v – точка сочленения, если выполняется следующее условие: up[u] >= time_in[v] и при этом, если v – корень, то v имеет > 1 ребенка(непосредственного потомка) . Доказательство такое же, что и с мостами. Но здесь мы сравниваем нестрого, т.к. при равенстве up[u] и time_in[v] существует ребро из поддерева, в котором корень - v, которое ведет в v, но оно тоже удалиться при удалении вершины v ( чего не происходило, когда мы удаляли ребра, поэтому и сравнение в мостах было строгое). При этом если v – корень и имеет 1 ребенка, то кол-во компонент связности не увеличиться, поэтому также необходимо выполнять эту проверку.