Дополнение графа до сильно связного ― вычислительная задача теории графов , входными данными для которой является ориентированный граф . Цель задачи ― добавить минимальное число дуг (или множество дуг с минимальным суммарным весом) так, чтобы исходный граф стал сильно связным .

Задача о дополнении графа до сильно связного была сформулирована и Робертом Тарьяном в 1976 году. Они доказали, что взвешенная версия задачи является NP-полной , а невзвешенная версия может быть решена за линейное время . Дальнейшее исследование задачи позволило найти и для взвешенной версии .

Невзвешенная версия

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

Пусть ${\displaystyle s}$ ― количество вершин-источников в конденсации (компонент сильной связности с как минимум одной исходящей дугой, но без входящих), ${\displaystyle t}$ ― количество вершин-стоков (компонент сильной связности с как минимум одной входящей дугой, но без исходящих) и ${\displaystyle q}$ ― количество изолированных вершин в конденсации. Тогда число дуг, которые необходимо добавить, как минимум ${\displaystyle \max(s+q,t+q)}$ . Это следует из того, что ${\displaystyle s+q}$ дуг необходимо добавить, чтобы у каждого источника или изолированной вершины появилась хотя бы одна входящая дуга. Аналогично, ${\displaystyle t+q}$ дуг необходимо добавить, чтобы у каждого стока или изолированной вершины появилась хотя бы одна исходящая дуга. Алгоритм для решения задачи находит в точности ${\displaystyle \max(s+q,t+q)}$ необходимых для добавления дуг .

Алгоритм Эсварана и Тарьяна использует поиск в глубину по конденсации графа, чтобы найти все пары источников и стоков, обладающие следующими свойствами:

• Из источника в каждой паре можно достичь стока в этой паре по пути, существующем в исходном графе.
• Из каждого источника, у которого нет пары, можно достичь некоторого стока, у которого пара есть.
• Каждый сток, у которого нет пары, достижим из некоторого источника, у которого пара есть.

Неточность их алгоритма поиска пар источников и стоков была позднее найдена и исправлена .

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

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

Общее число дуг в данных трёх наборах равно ${\displaystyle \max(s+q,t+q)}$ .

Взвешенная и параметризованная версия

Во взвешенной версии задачи каждая добавляемая дуга имеет заданный вес. Цель задачи ― выбрать множество добавляемых дуг с минимальным суммарным весом так, чтобы исходный граф стал сильно связным. Данная задача является NP-полной. 2-приближённый алгоритм был предложен . Параметризованная и взвешенная версия задачи, в которой необходимо добавить не более чем ${\displaystyle k}$ дуг с минимальным суммарным весом, сделав граф сильно связным, является .

Ссылки