Сильное расширение возможностей подключения

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

Проблема усиления связности была сформулирована Капали Эсвараном и Робертом Тарджаном ( 1976 ). Они показали, что взвешенная версия задачи является NP-полной, но невзвешенную задачу можно решить за линейное время . ^{[ 1 ]} Последующие исследования учитывали коэффициент аппроксимации и параметризованную сложность взвешенной задачи. ^{[ 2 ]}^{[ 3 ]}

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

В невзвешенной задаче увеличения связности входными данными является ориентированный граф, и цель состоит в том, чтобы добавить к нему как можно меньше ребер, чтобы превратить результат в сильно связный граф. Алгоритм Эсварана и Тарьяна для невзвешенного случая рассматривает конденсацию данного ориентированного графа, ориентированного ациклического графа , который имеет одну вершину на каждый сильно связный компонент данного графа. Сдача в аренду $s$ обозначаем количество исходных вершин в конденсации (сильно связные компоненты с хотя бы одним выходящим ребром, но без входящих ребер), $t$ обозначаем количество стоковых вершин в конденсации (сильно связные компоненты с входящими, но без исходящих ребер), и $q$ обозначают количество изолированных вершин в конденсации (сильно связные компоненты, не имеющие ни входящих, ни исходящих ребер), они отмечают, что количество добавляемых ребер обязательно не менее $\max(s+q,t+q)$ . Это следует из того, что $s+q$ необходимо добавить ребра, чтобы обеспечить входящее ребро для каждой исходной или изолированной вершины, и, по крайней мере, симметрично $t+q$ необходимо добавить ребра, чтобы обеспечить выходящее ребро для каждого приемника или изолированной вершины. Их алгоритм решения проблемы находит набор ровно $\max(s+q,t+q)$ ребра, которые нужно добавить к графу, чтобы сделать его сильно связным. ^{[ 1 ]}

Их алгоритм использует поиск в глубину конденсации, чтобы найти набор пар источников и стоков со следующими свойствами: ^{[ 1 ]}

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

Позже была обнаружена и исправлена незначительная ошибка в той части их алгоритма, которая находит пары источников и стоков. ^{[ 4 ]}

Как только эти пары будут найдены, можно получить сильное увеличение связности, добавив три набора ребер: ^{[ 1 ]}

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

Общее количество ребер в этих трех множествах равно $\max(s+q,t+q)$ . ^{[ 1 ]}

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

Взвешенная версия задачи, в которой каждое ребро, которое может быть добавлено, имеет заданный вес и цель состоит в том, чтобы выбрать набор добавленных ребер минимального веса, который делает данный граф сильно связным, является NP-полной. ^{[ 1 ]} Алгоритм аппроксимации с коэффициентом аппроксимации 2 был предложен Фредериксоном и Джа'Джа' (1981) . ^{[ 2 ]} Параметризованный и взвешенный вариант задачи, в котором нужно добавить не более $k$ ребра минимального общего веса, позволяющие сделать данный граф сильно связным, является управляемым с фиксированным параметром . ^{[ 3 ]}

Двусторонняя версия и применение сеточных связей

Если квадратная сетка состоит из жестких стержней (краев сетки), соединенных друг с другом гибкими соединениями по краям сетки, то вся конструкция может изгибаться разными способами, а не оставаться квадратной. Проблема распорок сетки заключается в том, как стабилизировать такую конструкцию, добавив дополнительные поперечные распорки в некоторые из ее квадратов. Эту проблему можно смоделировать с помощью теории графов, создав двудольный граф с вершиной для каждой строки или столбца квадратов в сетке и ребром между двумя из этих вершин, когда квадрат в данной строке и столбце соединен перекрестными связями. Если перекрестные связи внутри каждого квадрата делают его полностью жестким, то этот граф является неориентированным и представляет собой жесткую структуру тогда и только тогда, когда он является связным графом . ^{[ 5 ]} Однако если квадраты скреплены лишь частично (например, путем соединения двух противоположных углов веревкой или проволокой, которая предотвращает расширяющееся движение, но не предотвращает сжимающее движение), то граф является направленным и представляет собой жесткую структуру тогда и только тогда, когда он сильно связный граф. ^{[ 6 ]}

Связанная с этим проблема усиления связности заключается в том, как добавить дополнительные частичные связи к сетке, в некоторых квадратах которой уже есть частичные связи. Существующую частичную связь можно представить в виде ориентированного графа: и дополнительная частичная связь, которая будет добавлена, должна создать сильное расширение связности этого графа. Чтобы иметь возможность перевести решение проблемы усиления связности обратно к решению исходной проблемы раскосов, требуется дополнительное ограничение: каждое добавленное ребро должно соответствовать двудольному разбиению исходного графа и соединять только вершины строк со столбцами. вершины, а не пытаться соединить строки со строками или столбцы со столбцами. Эта ограниченная версия проблемы усиления связности снова может быть решена за линейное время. ^{[ 7 ]}

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Эсваран, Капали П.; Тарьян, Р. Эндре (1976), «Проблемы расширения», SIAM Journal on Computing , 5 (4): 653–665, doi : 10.1137/0205044 , MR 0449011
^ Jump up to: ^а ^б Фредериксон, Грег Н.; Джа'Джа, Джозеф (1981), «Алгоритмы аппроксимации для нескольких задач пополнения графов», SIAM Journal on Computing , 10 (2): 270–283, doi : 10.1137/0210019 , MR 0615218
^ Jump up to: ^а ^б Клинкби, Кристин Виттинг; Мишра, Пранабенду; Саураб, Сакет (январь 2021 г.), «Надежное расширение связности - это FPT», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Общество промышленной и прикладной математики, стр. 219–234, doi : 10.1137/1.9781611976465.15 , ISBN 978-1-61197-646-5
^ Рагхаван, С. (2005), «Заметка об алгоритме Эсварана и Тарьяна для задачи усиления связности», в Голден, Брюс; Рагхаван, С.; Васил, Эдвард (ред.), « Следующая волна в области вычислений, оптимизации и технологий принятия решений» , серия «Исследования операций/информатические интерфейсы», том. 29, Спрингер, стр. 19–26, номер документа : 10.1007/0-387-23529-9_2 , ISBN. 978-0-387-23528-8
^ Грейвер, Джек Э. (2001), «2.6 Решение проблемы сетки», Расчет на каркасы: математика в помощь проектированию жестких конструкций , Математические экспозиции Дольчиани, том. 25, Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 50–55, ISBN. 0-88385-331-0 , МР 1843781
^ Багливо, Дженни А .; Грейвер, Джек Э. (1983), «3.10 Несущие конструкции», Распространенность и симметрия в дизайне и архитектуре , Кембриджские городские и архитектурные исследования, Cambridge University Press, стр. 76–88, ISBN 9780521297844
^ Габоу, Гарольд Н .; Джордан, Тибор (2000), «Как сделать каркас квадратной сетки с кабелями жестким», SIAM Journal on Computing , 30 (2): 649–680, doi : 10.1137/S0097539798347189 , MR 1769375

[et76-1] Jump up to: ^а ^б ^с ^д ^и ^ж Эсваран, Капали П.; Тарьян, Р. Эндре (1976), «Проблемы расширения», SIAM Journal on Computing , 5 (4): 653–665, doi : 10.1137/0205044 , MR 0449011

[fj81-2] Jump up to: ^а ^б Фредериксон, Грег Н.; Джа'Джа, Джозеф (1981), «Алгоритмы аппроксимации для нескольких задач пополнения графов», SIAM Journal on Computing , 10 (2): 270–283, doi : 10.1137/0210019 , MR 0615218

[kms21-3] Jump up to: ^а ^б Клинкби, Кристин Виттинг; Мишра, Пранабенду; Саураб, Сакет (январь 2021 г.), «Надежное расширение связности - это FPT», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Общество промышленной и прикладной математики, стр. 219–234, doi : 10.1137/1.9781611976465.15 , ISBN 978-1-61197-646-5

[r05-4] Рагхаван, С. (2005), «Заметка об алгоритме Эсварана и Тарьяна для задачи усиления связности», в Голден, Брюс; Рагхаван, С.; Васил, Эдвард (ред.), « Следующая волна в области вычислений, оптимизации и технологий принятия решений» , серия «Исследования операций/информатические интерфейсы», том. 29, Спрингер, стр. 19–26, номер документа : 10.1007/0-387-23529-9_2 , ISBN. 978-0-387-23528-8

[g01-5] Грейвер, Джек Э. (2001), «2.6 Решение проблемы сетки», Расчет на каркасы: математика в помощь проектированию жестких конструкций , Математические экспозиции Дольчиани, том. 25, Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 50–55, ISBN. 0-88385-331-0 , МР 1843781

[bg83-6] Багливо, Дженни А .; Грейвер, Джек Э. (1983), «3.10 Несущие конструкции», Распространенность и симметрия в дизайне и архитектуре , Кембриджские городские и архитектурные исследования, Cambridge University Press, стр. 76–88, ISBN 9780521297844

[gj00-7] Габоу, Гарольд Н .; Джордан, Тибор (2000), «Как сделать каркас квадратной сетки с кабелями жестким», SIAM Journal on Computing , 30 (2): 649–680, doi : 10.1137/S0097539798347189 , MR 1769375

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]