Как найти мост в графе
Перейти к содержимому

Как найти мост в графе

  • автор:

Мосты и точки сочленения

Пусть дан неориентированный граф. Мостом называется такое ребро, удаление которого делает граф несвязным (или, точнее, увеличивает число компонент связности). Требуется найти все мосты в заданном графе.

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

Суть алгоритма

Идея

Мы можем заметить тот факт, что ребро между точками v и u является мостом тогда и только тогда, когда из вершины u и её потомков нельзя вернуться в вершину v или подняться выше нее. Осталось лишь понять, как нам это выяснить.

Алгоритм

Разобьём ребра на ориентированные и будем хранить их в отдельной структуре. Пусть мы будем запоминать номер вершины, в которую направлено ребро, номер данного ребра (номер ребра равен номеру обратного ребра) и ссылку на его обратное ребро.

Заведём граф ссылок на рёбра и заполним его.

Запустим обход графа в глубину (DFS).

Будем для каждой вершины v хранить два значения:

  • dp[v] — минимально возможная вершина в которую мы можем опуститься из этой вершины в процессе обхода в глубину (по умолчанию текущая глубина)
  • d[v] — глубина текущей вершины

В процессе обхода:

  • Если встречаем вершину u, в которой еще не были, то спускаемся в неё и тогда dp[v] = min(dp[v], dp[u]). Тем самым проверяем опустились ли мы из вершины u и её потомков выше v.
  • Если встречаем вершину v, в которой уже были, то dp[v] = min(dp[v], d[u]). Тем самым проверяем не встретили ли мы вершину выше по обходу графа, чем вершина v.

По завершении обхода вершины v и её потомков:

Если из вершины v нельзя опуститься выше нее самой и мы знаем проверяемое ребро (dp[v] == d[v] && p != nullptr(текущее ребро)), то ребро из этой вершины — есть мост.

p->is_bridge = true — вершина v

p->bck->is_bridge = true — вершина другого конца ребра

Реализация

#include using namespace std; typedef long long ll; #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) struct Edge < ll v,num; bool is_bridge; Edge* bck; Edge()<>Edge(ll v, ll num):v(v),num(num)<> >; vector> gr; vector dp,d,bridges; vector used; void dfs(ll v, ll depth = 0, Edge* p = nullptr)< used[v] = true; dp[v] = d[v] = depth; for(auto u : gr[v])< if(!used[u->v])< dfs(u->v,depth+1,u); dp[v] = min(dp[v],dp[u->v]); > else if (p && p->num != u->num)< dp[v] = min(dp[v],d[u->v]); > > if(p != nullptr && dp[v] == d[v])< p->is_bridge = true; p->bck->is_bridge = true; bridges.push_back(p->num+1); > > int main()< fast_cin(); ll n,m; cin >> n >> m; gr.resize(n); dp.resize(n); d.resize(n); used.resize(n); ll v,u; for(ll i = 0;i < m;i++)< cin >> v >> u; v--; u--; Edge* a = new Edge(u,i); Edge* b = new Edge(v,i); a->bck = b; b->bck = a; gr[v].push_back(a); gr[u].push_back(b); > for(ll i = 0;i < n;i++) if(!used[i]) dfs(i); sort(bridges.begin(),bridges.end()); cout >

Задачи по теме

Точки сочленения

Определение

Точкой сочленения называется вершина, удаление которой делает граф несвязным.

Суть алгоритма

Идея

Мы можем заметить два факта:

  • Рассмотрим ребро между вершинами v и u. Тогда если из вершины u и ее потомков нельзя попасть в какого-либо предка вершины v и притом вершина v не является корнем дерева, то данная вершина и есть точка сочленения
  • Если вершина v — корень дерева, то она является точкой сочленения тогда и только тогда, когда эта точка имеет более одного сына в обходе графа в глубину
Алгоритм

Заведем общий счетчик времени входа timer и два массива:

  • tin[v] — время входа в вершину v
  • fup[v] — минимально достижимая вершина из вершины v

Запустим обход графа в глубину (DFS).

В процессе обхода:

  • Если встречаем уже посещенную вершину u, то fup[v] = min(fup[v], tin[u]). Проверяем не спустились ли мы выше v.
  • Если встречаем не посещенную вершину v, то спускаемся в неё. Затем fup[v] = min(fup[v], fup[u]). Тем самым проверим не спустились ли мы выше v из вершины u и ее потомков. И наконец если из вершины u нельзя спуститься ниже вершины v и вершины v — не корень дерева обхода графа (v fup[u] >= tin[v] && p != -1), то вершина v и есть искомая точка сочленения. Добавляем 1 к количеству сыновей вершины v (children++)

По завершении обхода:

Если вершина v является корнем обхода графа в глубину и имеет более одного сына, то она также является точкой сочленения (p == -1 && children > 1)

Реализация

#include using namespace std; typedef long long ll; #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ll timer = 0; vector> gr; vector tin,fup; set points_of_connectebility; vector used; void dfs(ll v,ll p = -1) < used[v] = true; tin[v] = fup[v] = timer++; ll children = 0; for(auto u : gr[v])< if(u == p)< continue; >if(used[u]) < fup[v] = min(fup[v],tin[u]); >else< dfs(u,v); fup[v] = min(fup[v],fup[u]); if(fup[u] >= tin[v] && p != -1) < points_of_connectebility.insert(v+1); >children++; > > if(p == -1 && children > 1) < points_of_connectebility.insert(v+1); >> int main() < fast_cin(); ll n, m; cin >> n >> m; gr.resize(n); tin.resize(n); fup.resize(n); used.resize(n); ll v, u; for (ll i = 0; i < m; i++) < cin >> v >> u; v--; u--; gr[v].push_back(u); gr[u].push_back(v); > for (ll i = 0; i < n; i++) if (!used[i]) dfs(i); cout >

Использование обхода в глубину для поиска мостов

Пусть [math] T [/math] — дерево обхода в глубину графа [math] G[/math] . Ребро [math] (u, v) [/math] является мостом тогда и только тогда, когда [math] (u, v) \in T[/math] и из вершины [math] v[/math] и любого ее потомка нет обратного ребра в вершину [math] u[/math] или предка [math] u [/math]

[math] \Leftarrow[/math]
Удалим [math] (u, v)[/math] из [math] G[/math] . Докажем, что мы не сможем достичь ни одного из предков [math] v [/math] (в частности [math] u [/math] ). Докажем этот факт от противного. Пусть это не так, и [math] w[/math] — предпоследняя вершина на пути от [math] v[/math] до ее предка [math]x [/math] . Очевидно, [math] (w, x)[/math] не ребро дерева (в силу единственности пути в дереве). Если [math] (w, x)[/math] — обратное ребро, то это противоречит условию теоремы, так как [math] x[/math] — предок [math] u[/math] . Следовательно мы не достигнем предков [math]v[/math] , а значит количество компонент связности увеличилось, поэтому ребро [math](u, v)[/math] является мостом.
[math] \Rightarrow[/math]

Функция [math]ret(v)[/math]

Определим функцию [math]ret(v)[/math] , где [math]v \in V[/math] , как минимум из следущих величин

  • [math]enter(v)[/math] время входа в вершину [math]v [/math]
  • [math]enter(x)[/math] , где [math]x[/math] — потомок [math]v[/math]
  • [math]enter(w)[/math] , где [math](w, x)[/math] — обратное ребро, а [math]w[/math] — потомок [math]v[/math] (в нестрогом смысле)

Лемма

Ребро [math](u, v)[/math] является мостом тогда и только тогда, когда [math](u, v)[/math] принадлежит дереву обхода в глубину и [math]ret(v) \gt enter(u)[/math]

Рассмотрим вершину [math]v[/math] или её потомка. Из нее есть обратное ребро в предка [math]v[/math] тогда и только тогда, когда найдется такой сын [math]t[/math] , что [math]ret[t] \le enter[v][/math] . Если [math]ret[t] = enter[v][/math] , то найдется обратное ребро, приходящее точно в [math]v[/math] . Если же [math]ret[t] \lt enter[v][/math] , то это означает наличие обратного ребра в какого-либо предка вершины [math]v[/math] .

[math]ret(v)[/math] = [math]\min([/math] [math]enter(v) [/math] , [math]enter(p)[/math] , [math]ret(u)[/math] [math]) [/math] , где
[math](v, p)[/math] — обратное ребро,
[math](v, u)[/math] — ребро дерева

В скобах у вершины [math]u[/math] указаны [math]enter[u][/math] и [math]ret[u][/math] . Мостами будут красные ребра

Псевдокод

function dfs(v): time = time + 1 enter[v] = time ret[v] = time for всех u смежных с v if (v, u) — обратное ребро ret[v] = min(ret[v], enter[u]) if вершина u — белая dfs(u) ret[v] = min(ret[v], ret[u]) if ret[u] > enter[v] ребро (v, u) — мост

См. также

  • Обход в глубину, цвета вершин
  • Лемма о белых путях

Источники информации

  • MAXimal :: algo :: Поиск мостов
  • Wikipedia — Bridge
  • Визуализация поиска мостов
  • Седжвик Р. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128
  • Алгоритмы и структуры данных
  • Обход в глубину

Мост, эквивалентные определения

[math](1) \Rightarrow (2)[/math] Пусть ребро [math]x[/math] соединяет вершины [math]a[/math] и [math]b[/math] . Пусть граф [math] G — [/math] — связный. Тогда между вершинами [math]a[/math] и [math]b[/math] существует еще один путь, т.е. между вершинами [math]a[/math] и [math]b[/math] существуют два реберно-непересекающихся пути. Но тогда ребро [math]x[/math] не является мостом графа [math]G[/math] . Противоречие.

[math](2) \Rightarrow (4)[/math] В условиях определения (4) пусть существуют такие вершины [math]u[/math] и [math]w[/math] , что между ними существует простой путь [math]P: x \notin P[/math] . Но тогда граф [math]G — [/math] — связный. Противоречие.

[math](4) \Rightarrow (3)[/math] Возьмем [math]\forall u \in U[/math] и [math]\forall w \in W [/math] . Тогда [math]\forall[/math] простой путь [math]u \rightsquigarrow w[/math] содержит ребро [math]x[/math] . Утверждение доказано

[math](3) \Rightarrow (1)[/math] Пусть [math](a, b) = x[/math] . Пусть ребро [math]x[/math] не является мостом по определению (1).

См.также

  • Точка сочленения, эквивалентные определения
  • Использование обхода в глубину для поиска мостов

Источники информации

  • Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)

Поиск мостов

Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.

Пример задачи, где их интересно искать: дана топология сети (компьютеры и физические соединения между ними) и требуется установить все единые точки отказа — узлы и связи, без которых будут существовать два узла, между которыми не будет пути.

Наивный алгоритм поочередного удаления каждого ребра \((u, v)\) и проверки наличия пути \(u \leadsto v\) потребует \(O(m^2)\) операций. Чтобы научиться находить мосты быстрее, сначала сформулируем несколько утверждений, связанных с обходом в глубину.

Запустим DFS из произвольной вершины. Введем новые виды рёбер:

  • Прямые рёбра — те, по которым были переходы в dfs.
  • Обратные рёбра — то, по которым не было переходов в dfs.

Заметим, что никакое обратное ребро \((u, v)\) не может являться мостом: если его удалить, то всё равно будет существовать какой-то путь от \(u\) до \(v\), потому что подграф из прямых рёбер является связным деревом.

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

Сооптимизировать его до линейного времени (до одного прохода dfs) поможет замечание о том, что обратные рёбра могут вести только «вверх» — к какому-то предку в дереве обхода графа, но не в другие «ветки» — иначе бы dfs увидел это ребро раньше, и оно было бы прямым, а не обратным.

Http---codeforces.com-predownloaded-e4-11-e4112103b65ad2cb3287cf9df022ac858ff15554.png

Тогда, чтобы определить, является ли прямое ребро \(v \to u\) мостом, мы можем воспользоваться следующим критерием: глубина \(h_v\) вершины \(v\) меньше, чем минимальная глубина всех вершин, соединенных обратным ребром с какой-либо вершиной из поддерева \(u\).

Для ясности, обозначим эту величину как \(d_u\), которую можно считать во время обхода по следующей формуле\[ d_v = \min \begin h_v, &\\ d_u, &\text (v \to u) \text < прямое>\\ h_u, &\text (v \to u) \text < обратное>\end \]

const int maxn = 1e5; bool used[maxn]; int h[maxn], d[maxn]; void dfs(int v, int p = -1)  used[u] = true; d[v] = h[v] = (p == -1 ? 0 : h[p] + 1); for (int u : g[v])  if (u != p)  if (used[u]) // если ребро обратное d[v] = min(d[v], h[u]); else  // если ребро прямое dfs(u, v); d[v] = min(d[v], d[u]); if (h[v]  d[u])  // ребро (v, u) -- мост > > > > > 

Примечание. Более известен алгоритм, вместо глубин вершин использующий их \(tin\), но автор считает его чуть более сложным для понимания.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *