что такое конденсация графа

Алгоритм Kosaraju по полкам

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

Для того, чтобы понять алгоритм Косарайю необходимо владеть некоторыми понятиями теории графов

Основные понятия

Вершины u, v называются сильно связанными, если в графе G существует путь (необязательно прямой) u→v И v→u (Обозначим сильно связанные вершины u↔v), причём для каждой вершины u истинно u↔u

Компоненты сильной связности

Начало нового такта DFS

Прохождение по ребру (при том, не важно, рекурсивный проход или нет)

Пример присвоения времени выхода:

Дан следующий граф:

Обойдём его алгоритмом DFS, помечая вершины, согласно правилам выше:

Непройденные вершины обозначим ‘?’
Будем выбирать стартовую вершину в порядке возрастания непомеченных вершин
Изначально, счётчик 0

Начинаем новый такт, выбрав вершину 0 (как вершину с минимальным индексом). Повышаем счётчик на 1 и присваиваем это число метке вершины 0.
Попутно будем строить деревья тактов DFS справа от исходного графа

У вершины 2 нет соседей. Поэтому нам остаётся лишь рекурсивно вернуться в предыдущую вершину (чтобы понять, какая вершина была предыдущей, мы и строим дерево). Проходя по рекурсивному ребру 2-0, увеличиваем счётчик на 1 и присваиваем вершине 0 новую пометку

У вершины 5 нет непомеченных соседей. Возвращаемся в предыдущую вершину, увеличивая счётчик, и присваивая новую метку

Приведём несколько простых лемм:

Лемма 1: Если истинно u↔v И v↔w, то истинно u↔w

Доказательство:
Поскольку u↔v, то v достижима из u, также имеем v↔w, значит w достижима из v.
Следовательно w достижима из u, аналогично, u достижима из w. Получаем u↔w

цикл А имеет общую вершину u с циклом В

Доказательство:
Заметим, что все вершины одного цикла входят в одну компоненту связности, так как по циклу из любой его вершины можно достичь другую. Если два цикла имеют общую точку, то через неё можно перейти к вершинам другого цикла и достичь любую из них. Таким образом, все вершины, принадлежащие связанным
между собой циклам, входят в одну компоненту связности.
Рассмотрим любое из максимальных объединений циклов C. Докажем, что вершина, не
входящая в C, принадлежит другой компоненте сильной связности. Докажем от противного.
Пусть вершина v не входит в объединение циклов C, но сильно связана с одной из вершин этих
циклов u. Тогда по определению сильной связности есть путь от вершины v до u и путь от
вершины u до v. Склеивая (конкатенацией) эти пути, получаем цикл, связанный с объединением
циклов через вершину u, но не входящий в C, что противоречит предположению.
Заметим, что эта лемма дает идею о том, как на графе увидеть компоненты сильной связности.

Лемма 3: Инвертирование рёбер цикла не влияет на его цикличность

Доказательство:
Если в исходном графе есть путь из u в v, то в инвертированном графе будет путь из v в u.

Алгоритм Косарайю

Алгоритм Косарайю предназначен для поиска компонент сильной связности в ориентированном графе и состоит из трёх шагов:

Выполнить поиск в глубину (DFS), пока не будут «помечены» все вершины. Вершина считается «помеченной», когда ей присвоено время выхода из рекурсии (см. основные понятия).

Инвертировать исходный граф

Выполнить DFS в порядке убывания пометок вершин.

Полученные деревья каждого такта DFS последнего шага являются компонентами сильной связности

Прежде чем доказывать алгоритм, предлагаю разобрать пример работы алгоритма

Пример работы алгоритма Косарайю пошагово

Дан следующий граф:

Шаг 1:
Непомеченные вершины имеют метку ‘?’
Справа от исходного графа находится лес DFS.
Стартовая вершина выбирается в порядке возрастания индексов.
Полный протокол работы не показал, так он имеется в разделе «основные понятия»

Шаг 2:
Инвертируем рёбра

Шаг 3:
Выбираем стартовую вершину в порядке убывания меток.
Так как теперь нам интересен лишь лес тактов DFS, то нет смысла считать время выхода из вершин, поэтому я не показал рекурсивных переходов.
Справа от инвертированного графа
показан лес тактов DFS

После завершения алгоритма имеем 3 компоненты сильной связности

Доказательство корректности алгоритма

Немного уточним, что требуется доказать:

Вершины u и v сильно связаны ⇔ после выполнения алгоритма они принадлежат одному дереву такта DFS

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

Вершина r была рассмотрена на 3 шаге раньше всех, значит время выхода из неё на 1 шаге больше, чем время выхода из вершин u и v. Из этого мы получаем 2 случая:

Обе эти вершины были достижимы из r в исходном графе. Это означает сильную связность вершин u и r и сильную связность вершин v и r (по Лемме 3). Склеивая пути мы получаем связность вершин u и v (по Лемме 1)

Хотя бы одна вершина не достижима из r в исходном графе, например v. Значит и r была не достижима из v в исходном графе, так как время выхода из r — больше (если бы она была достижима, то время выхода из v было бы больше, чем из r, просмотрите ещё раз первый шаг примера). Значит между этими вершинами нет пути (ни в исходном, ни в инвертированном графах), но последнего быть не может, потому что по условию v достижима из r на 3 шаге (в инвертированном графе)

Значит, из случая 1 и не существования случая 2 получаем, что вершины u и v сильно связаны в обоих графах

Сложность алгоритма

Поиск в глубину в исходном графе выполняется за O(V+E)

Для того, чтобы инвертировать все ребра в графе, представленном в виде списка смежности потребуется O(V+E) действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования (индексы столбцов будут использоваться в качестве индексов строк и наоборот)

Количество рёбер в инвертированном равно количеству рёбер в изначальном графе, поэтому поиск в глубину будет работать за O(V+E)

В итоге получаем, что при оценке снизу сложность алгоритма — O(V+E)
Оценка сверху (когда имеем полный граф) будет следующей (напомню, что количество рёбер в полном графе на n вершинах равно n(n-1)/2):

То есть, в худшем случае имеем квадратичную сложность

Где применять алгоритм, полностью зависит от Вашего воображения составлять графы.

Например: проецирование транспортной сети на граф. Алгоритм поможет проверить новоиспечённую транспортную сеть на достижимость каждой вершины из каждой вершины (чтобы убедиться, что есть путь из окраины в центр и обратно).

Можно тестировать алгоритмом систему воздуховода в зданиях; течение тока в полупроводниковых приборах

Можно мыслить шире: проецируем кровеносную систему живого существа, которое Вам поручили создать в рамках проекта генной инженерии, где-нибудь в 2077 году). Алгоритм поможет узнать, доходит ли кровь от сердца до органов и обратно.

Источник

Что такое конденсация графа

Для заданного ориентированного графа найти количество ребер в его конденсации.

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

Конденсация графа не содержит кратных ребер.

Выход. Выведите количество ребер в конденсации графа.

РЕШЕНИЕ

графы – сильная связность

Находим компоненты сильной связности графа. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет. Пусть color[ i] – цвет i-ой вершины. Число цветов окраски равно количеству компонент сильной связности.

Перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра ( a, b), для которого color[ a] ≠ color[ b], занесем во множество s пару (color[ a], color[ b]). Поскольку мы используем множество, а не мультимножество, то кратные пары учитываться не будут. Количество элементов во множестве s будет равняться числу ребер в конденсации графа.

Граф, приведенный в примере, имеет следующий вид:

Конденсация графа состоит из трех вершин и двух ребер.

Входной граф храним в списке смежности g. Обратный граф (граф, в котором изменены все направления ребер) храним списке смежности gr. Ребра конденсированного графа будем сохранять во множестве пар s.

vector int > used, top, color;

Функция dfs1 реализует поиск в глубину на входном графе. В массив top заносим последовательность вершин в порядке, в котором поиск в глубину завершает их обработку.

Функция dfs 2 реализует поиск в глубину на обратном графе. Все вершины, которые будут пройдены в результате рекурсивного вызова функции dfs2, принадлежат одной компоненте сильной связности. Красим все пройденные вершины цветом с.

void dfs2( int v, int c)

Основная часть программы. Читаем входные данные. Строим обратный граф.

Запускаем поиск в глубину на входном графе. Последовательность, в которой завершается обработка вершин графа, сохраняется в массиве top.

Запускаем поиск в глубину на обратном графе. Вершины обратного графа рассматриваем в порядке обхода массива top справа налево (с конца в начало). Вершины, входящие в одну компоненту сильной связности, красим одним и тем же цветом. Текущий цвет раскраски находится в переменной с.

Переменная c содержит количество компонент связности.

Перебираем все ребра графа ( i, to). Проверяем, лежат ли вершины i и to в разных сильно связных компонентах. Это так, если они покрашены разными цветами. Тогда ребро ( i, to) принадлежит конденсации графа, поэтому заносим во множество s пару (color[ i], color[ to]). За счет того что мы используем множество, а не мультимножество, то кратные пары учитываться не будут.

Выводим количество ребер в конденсации графа.

Источник

Поиск компонент сильной связности: алгоритм Косарайю

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

К делу:

Заметим: отношение сильной связности — это отношение эквивалентности.

Компонентой сильной связности называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности. Другими словами компонента сильной связности = сильно связный подграф. Так как сильная связность — это отношение эквивалентности, то граф разбивается на сильно связные компоненты. Наша задача найти все такие классы эквивалентности.

Пусть дан ориентированный граф G = (V, E). Через G’ = (V, E’) обозначим интертирование G.

Будем обходить граф G в глубину, пока не посетим все вершины. Заведем массив out = [0. |V|-1] — время выхода из вершины. Под временем понимаются логические часы: изначально время равно 0, при переходе в вершину или выходе из неё время увеличивается на 1.

Когда обход закончится, заведем массив vertices, куда добавим все вершины в порядке увеличения времени выхода. Теперь запустим обход в глубинку на инвертированном графе G’. Каждый раз для обхода будем выбирать ещё не посещенную вершину с максимальным индексом в массиве vertices. Все вершины, посещенные в ходе одной итерации dfs, образуют компоненту сильной связности.

Заметим: если граф представлен графом смежности, то нам не требуетcя хранить в памяти инвертированный граф. Иначе нам потребуется O(V+E) доп. памяти. Но, в любом случае, нам требуется O(V) памяти для массивов out и vertices.

Алгоритм состоит из двух обходов DFS. Каждый работает пропорционально V+E для разреженных графов и V^2 для насыщенных. Кроме того, нам требуется O(VlogV) для сортировки вершин при построении массива vertices.

Источник

Продвинутый DFS

Время входа и выхода

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

Как их заполнить: давайте заведем таймер, отвечающий за время на текущий момент программы и будем обновлять информацию, когда заходим/выходим из вершины:

Время входа или выхода пригождается во многих алгоритмах, давайте разберем несколько.

Топологическая сортировка

Задача о топологической сортировке графа звучит так:

Дан ориентированный граф, нужно расставить его вершины в массиве так, чтобы все ребра шли вправо по массиву.

Эта же задача очень часто встречается в реальной жизни. Например, у вас есть много зависимостей вида “в библиотеке А используется библиотека B”, и вам нужно загрузить все библиотеки в таком порядке, чтобы никогда не загружать A до B.

Во-вторых, верно обратное! Если цикла нет, то его обязательно можно топологически отсортировать. Попытаемся придумать как, заодно придумаем алгоритм.

Заметим, что вершину, из которой не ведет ни одно ребро, можно всегда поставить последней. И такая вершина всегда есть в графе без циклов (если всегда есть внешнее ребро, то есть цикл). Из этого сразу следует доказательство: просто будем класть в массив вершину, из которой ничего не ведет и убирать ее из графа. Массив потом надо будет развернуть.

Из этого следует, что достаточно просто брать вершины в порядке выхода из DFS, то есть в конце DFS, например, просто класть эту вершину в конец массива с ответом. Ну и этот массив надо удет перевернуть, чтобы все ребра шли вправо, а не влево.

Компоненты сильной связности

Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? Ведь в них тоже хочется найти какую-то структуру.

Для этого обычно вводят такое понятие как “сильная связность”. В ориентированных графах две вершины связаны сильно, если существует путь из одной в другую и наоборот. Проще говоря, они обе лежат на каком-то цикле.

Example

Часто рассматривают граф самих компонент сильной связности. На катинке выше их шесть, и между ними остаются ребра из изначально графа. Очевидно, что такой граф уже удет ациклических: иначе компоненты на цикле нужно было бы объединить в одну.

Конденсация графа

Задача о конденсации графа звучит так:

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

При доказательстве возникают два принципиально различных случая в зависимости от того, в какую из компонент первой зайдёт обход в глубину$:

Сортируем вершины в порядке убывания времени выхода.

Проходимся по массиву вершин в том порядке на равернутом графе и запускаем на нем DFS, выделяя компоненты сильной связности.

Давайте теперь возьмем конъюнкцию дизъюнктов, а именно И от ИЛИ от переменных (или НЕ переменных). Например, такое выражение:

Задача SAT заключается в том, чтобы найти такие значения переменных, при которых это выражение становится истинным, ии сказать, что таких нет. Заметьте, что у нас в каждой скобке в этом примере ровно две переменные, в таком случае задача называется 2-SAT, и именно ее мы и хотим решить. Для примера выше решением является \(a=1, b=0, c=0, d=1\) (убедитесь, что все скобки стали True).

Причем тут графы? А вот часто в разных математических задачах надо внезапно ввести граф и он тут же помогает решить задачу.

Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной \(x_\) вершины \(x_\) и \(!x_\) находились в разных компонентах сильной связности графа импликаций.

Пусть решение существует и нам надо его найти.

Итак, мы построили алгоритм, который находит искомые значения переменных в предположении, что для любой переменной \(x\) вершины \(x\) и \(!x\) находятся в разных компонентах сильной связности. Выше показали корректность этого алгоритма. Следовательно, мы одновременно доказали указанный выше критерий существования решения.

Проверка на двудольность

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

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

Источник

Что такое конденсация графа

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

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

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

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

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

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

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

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

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

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

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

Источник