Задача 6. Лекция. Графы. Компоненты сильной связности

Условие

Связность для ориентированных графов

Что означает связность для ориентированного графа? Тут надо быть аккуратным. Несвязный неориентированный граф можно разбить на связные компоненты, не соединенные друг с другом. С ориентированными графами ситуация сложнее. Граф на рис. 1 нельзя разбить на две части, не соединенные друг с другом. Но мы не будем называть этот граф связным, поскольку в нем нет пути из G в B или из F в A. Дадим такое определение:

Вершины u и v ориентированного графа называются связанными (connected), если в нем есть путь из u в v, а также путь из v в u.

Такое отношение на вершинах разбивает все множество вершин на непересекающиеся подмножества связанных вершин, называемые компонентами сильной связности (strongly connected components). Граф на рис. 1 имеет пять таких компонент.

а.
б.
Рис 1. (а) Ориентированный граф и его компоненты сильной связности. (б) Конденсация ориентированного графа.

Стянем теперь каждую компоненту сильной связности в отдельную вершину (метавершину) и оставим только ребра между метавершинами (см. рис. 1), удалив дубликаты. Полученный граф называется метаграфом (meta-graph) (также графом компонент или конденсацией) исходного. Он не содержит циклов: если бы несколько компонент образовывали цикл, то вершины этих компонент были бы в исходном графе достижимы друг из друга и вошли бы в одну компоненту.

Свойство 0. Граф конденсации любого ориентированного графа является ациклическим (и может быть топологически упорядочен).

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

Свойство 1. Процедура Explore, вызванная для вершины u, заканчивает работу, когда посещены все вершины, достижимые из u.

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

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

Для начала ответим на первый вопрос. Сначала покажем, как решать симметричную задачу: найти вершину в компоненте-истоке

Свойство 2. Вершина, которой поиск в глубину присваивает максимальное tout-значение, лежит в компоненте-истоке.

Свойство 3. Пусть C и C — компоненты сильной связности графа и в графе есть ориентированное ребро из C в C. Тогда максимальное tout-значение вершин в C больше, чем максимальное tout-значение вершин в C.

Доказательство. Дождемся момента, когда при поиске в глубину впервые появится вершина v из C или C. Если v ∈ C, то вызов Explore(v) не завершится, пока не будут обработаны все вершины обеих компонент (по свойству 1). Поэтому tout[v] будет больше, чем у всех вершин из C. Если же v ∈ C, то вызов Explore(v) обойдет все вершины C, но до C дело еще не дойдет — и максимальное tout-значение в C тоже будет больше.

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

Таким образом, мы научились находить компоненту-исток и вершину в ней. Как найти все вершины только данной компоненты? Рассмотрим обращенный граф GR, получаемый из G изменением направлений всех ребер (см. рис. 2). В GR будут те же компоненты сильной связности, как и у G (покажите). Также, найденная вершина компоненты-истока G будет вершиной компоненты-стока графа GR. Тогда вызов Explore из найденной вершины на графе GR обойдет только вершины компоненты истока графа G.

Теперь нам необходимо удалить все пройденные вершины из графа и найти следующую вершину с максимальным значением tout, после чего запустить Explore в обращенном графе из нее. Повторяя эту процедуру, найдем все компоненты сильной связности в порядке их топологической сортировки.

Заметим, что явно удалять вершины не нужно. Достаточно просто обойти вершины в порядке убывания tout и вызвать Explore из каждой непосещённой.

Итак, мы построили следующий алгоритм выделения компонент сильной связности:

  1. Запустить обход в глубину графа G, который вернет вершины в порядке убывания tout. Заметим, что для этого достаточно добавлять вершину в массив при выходе Explore из этой вершины.
  2. Построить обращенный граф GR. Запустить процедуру Explore из каждой непосещённой вершины в порядке убывания tout-значений. Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Данный алгоритм не просто находит все компоненты связности, но и строит ациклический граф конденсации в порядке топологической сортировки компонент.


0.043s 0.008s 19