Двусвязность: сеть, которая переживает одну поломку

Если ты различаешь рёберную и вершинную двусвязность, знаешь про дерево блоков и помнишь, что отсутствие мостов не означает отсутствия точек сочленения, листай до «Теперь сам».

Как думаешь, хватает ли отсутствия мостов

Сеть спроектировали так, что мостов в ней нет: обрыв любого канала не разделит систему. Прежде чем читать дальше, ответь: гарантирует ли это, что систему не разделит отказ любого одного УЗЛА? Попробуй придумать граф без мостов, в котором есть точка сочленения.

На что это похоже

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

Механизм: два вида двусвязности

рёберная двусвязность : в графе нет МОСТОВ
                        ⇔ между любыми двумя вершинами есть 2 пути без общих РЁБЕР

вершинная двусвязность: в графе нет ТОЧЕК СОЧЛЕНЕНИЯ (и вершин больше двух)
                        ⇔ между любыми двумя вершинами есть 2 пути без общих
                          внутренних ВЕРШИН

вершинная ⇒ рёберная, обратное НЕВЕРНО

Равносильности - это теорема Менгера; доказывать её здесь не будем, но запомнить стоит именно в такой форме: «нет узкого места» и «есть запасной маршрут» - две стороны одного факта.

Разбиения:

рёберно-двусвязные компоненты : убрать все мосты → куски, на которые распался граф
блоки (вершинно-двусвязные)   : максимальные куски без точек сочленения внутри;
                                соседние блоки имеют ровно одну общую вершину -
                                точку сочленения
дерево блоков                 : блоки и точки сочленения как вершины,
                                ребро - «точка принадлежит блоку». Это всегда ДЕРЕВО

Правило

СВЯЗНЫЙ граф рёберно двусвязен, если в нём нет мостов, и вершинно двусвязен, если нет точек сочленения; вершинная двусвязность строго сильнее. По теореме Менгера это равносильно существованию двух путей без общих рёбер (соответственно без общих внутренних вершин) между любой парой вершин. Убрав мосты, получаем рёберно-двусвязные компоненты; вершинно-двусвязные блоки пересекаются по точкам сочленения и образуют дерево блоков (у несвязного графа - лес). Мосты и точки сочленения находит знакомый обход с low; выделение самих блоков требует ещё и стека рёбер и в курсе не разбирается.

Разбор: раскладываем граф на компоненты

Граф из урока про мосты: два треугольника a-b-c и d-e-f, соединённые ребром c-d. Мостов один - c-d; точки сочленения - c и d.

Рёберно-двусвязные компоненты. Убираем мост c-d - граф распадается на два куска: {a, b, c} и {d, e, f}. Внутри каждого мостов нет: любое ребро треугольника обходится по двум другим. Значит компонент две.

Блоки. Точки сочленения c и d «режут» граф на максимальные куски без внутренних точек сочленения: первый треугольник {a,b,c}, второй {d,e,f} и САМО РЕБРО c-d - оно тоже блок, из двух вершин. Блоков три. Дерево блоков: {a,b,c} — c — {c,d} — d — {d,e,f}, и это действительно дерево, а не цикл.

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

Разбор: почему одно не влечёт другое

Вернёмся к вопросу из начала. Возьмём два треугольника a-b-c и c-d-e, склеенных вершиной c (схема выше). Мостов нет: у каждого ребра есть обходной путь внутри своего треугольника. Но c - точка сочленения: убери её вместе с четырьмя рёбрами, и {a,b} окажутся отрезаны от {d,e}.

Значит рёберная двусвязность вершинной не гарантирует. Обратное направление верно, но только для СВЯЗНОГО графа: если он связен, вершин больше двух и точек сочленения нет, то нет и мостов. Доказывается так: пусть ребро u-v - мост. В связном графе с более чем двумя вершинами хотя бы у одного конца моста есть ещё сосед - пусть это u. Убрав u, мы отрезаем всё, что было за мостом, от остальных соседей u, значит u - точка сочленения.

Без связности утверждение ломается, и контрпример стоит увидеть: треугольник a-b-c плюс отдельное ребро u-v. Точек сочленения нет ни одной - убери u, и компонент как было две (треугольник и пара u-v), так и осталось две (треугольник и одинокая v). А мост есть: ребро u-v. Поэтому и определения двусвязности, и теорема Менгера формулируются для связного графа.

Практический вывод для проектирования сети: резервировать надо не только каналы, но и узлы, и проверять оба свойства отдельно. Формулировка «у нас нет единой точки отказа» должна означать вершинную двусвязность, а не только отсутствие мостов.

Что ломается без этого

Первое: считать, что «нет мостов» значит «нет единой точки отказа» - контрпример выше. Второе: искать блоки как «компоненты после удаления точек сочленения» - так получится неверно: блоки ПЕРЕСЕКАЮТСЯ по точкам сочленения, а удаление их выбросило бы эти вершины вовсе. Третье: считать граф из двух вершин и ребра вершинно двусвязным - по определению требуется больше двух вершин, иначе «два пути без общих внутренних вершин» вырождается. Четвёртое: применять понятия к ориентированному графу - там аналог другой (сильная связность и её усиления). Пятое: думать, что двусвязность спасает от ДВУХ отказов - нет, она гарантирует выживание ровно одного; для двух нужна трёхсвязность, и это отдельная, куда более сложная теория.

Зачем это в работе

Это язык, на котором говорят про отказоустойчивость. «Сеть переживает отказ любого одного элемента» - это и есть двусвязность, и её проверяют одним обходом, а не рассуждениями на словах. В проектировании дата-центров и магистральных сетей закладывают два независимых пути между площадками - ровно формулировка Менгера. В анализе инфраструктуры городов ищут точки сочленения дорожной сети, чтобы понять, где строить объезд. В управлении рисками поставок тот же граф показывает поставщика, через которого идёт всё. А дерево блоков - рабочая структура для задач, где нужно понять, как граф устроен «крупными кусками»: оно сводит запутанный граф к дереву, а с деревьями работать намного проще - этим займётся глава о запросах к дереву.

Теперь сам

Граф: 1-2, 2-3, 3-1, 3-4, 4-5, 5-3. Есть ли в нём мосты? Есть ли точки сочленения? Сколько в нём блоков?