Мост в графе
Мост — это ребро графа, удаление которого увеличивает число компонент связности. Иными словами, после удаления моста некоторые вершины перестают быть соединены путём.
Чтобы рассуждать о мостах, полезно понимать цикл в графе. Ребро, входящее хотя бы в один цикл, мостом быть не может: между его концами останется обходной путь по остальным рёбрам цикла. Поэтому в неориентированном графе верно обратное правило: ребро является мостом тогда и только тогда, когда оно не входит ни в один цикл.
Пусть граф состоит из треугольника \(A-B-C-A\) и отдельной вершины \(D\), соединённой с \(C\) ребром \(CD\). Рёбра треугольника не являются мостами: для каждого есть обходной путь по двум другим рёбрам. Ребро \(CD\) — мост, потому что после его удаления вершина \(D\) оказывается в отдельной компоненте.
Самый простой способ распознавания в небольшой задаче — временно удалять каждое ребро и пересчитывать связность графа: если число компонент увеличилось, найден мост. Для больших графов применяют поиск в глубину (DFS). Для каждой вершины запоминают время входа \(tin[v]\) и значение \(low[v]\) — минимальное время входа, достижимое из её поддерева по рёбрам дерева DFS и не более чем одному обратному ребру. Ребро из вершины \(v\) в её сына \(u\) является мостом, если \(low[u]>tin[v]\).
Мост — это ребро, а вершина сочленения — вершина, удаление которой увеличивает число компонент связности. Удаление обычного ребра также может не разорвать граф, даже если оно кажется важным.
В графе есть цикл \(A-B-C-A\) и ребро \(AC\). Является ли ребро \(AC\) мостом?
Главное
- Мост — ребро, удаление которого увеличивает число компонент связности.
- В неориентированном графе мост не принадлежит ни одному циклу.
- В DFS ребро \((v,u)\) является мостом, если \(low[u]>tin[v]\).