1313
правок
Связность графа: различия между версиями
Материал из WEGA
→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 6: | Строка 6: | ||
Неориентированный граф G называется k-связным (точнее, k-вершинно-связным), если удаление любых k-1 или меньшего числа вершин (с инцидентными им ребрами) не приводит к нарушению связности G. Аналогичным образом, граф называется k-реберно-связным, если удаление любых k-1 ребер не приводит к нарушению связности G. Согласно теореме Менгера, k-вершинно-связный граф содержит по меньшей мере k открытых вершинно-непересекающихся путей, соединяющих любую пару вершин. В k-вершинно-связных графах любую пару вершин соединяют k вершинно-непересекающихся путей. Связность графа равна наибольшему значению k, при котором он является k-связным. Задача вычисления связности графа и задача поиска k непересекающихся путей между заданной парой вершин могут быть решены при помощи алгоритмов нахождения максимального потока. Ребро называется [[критическое ребро|критическим]] в k-связном графе, если после его удаления граф уже не будет k-связным. | Неориентированный граф G называется k-связным (точнее, k-вершинно-связным), если удаление любых k-1 или меньшего числа вершин (с инцидентными им ребрами) не приводит к нарушению связности G. Аналогичным образом, граф называется k-реберно-связным, если удаление любых k-1 ребер не приводит к нарушению связности G. Согласно теореме Менгера, k-вершинно-связный граф содержит по меньшей мере k открытых вершинно-непересекающихся путей, соединяющих любую пару вершин. В k-вершинно-связных графах любую пару вершин соединяют k вершинно-непересекающихся путей. Связность графа равна наибольшему значению k, при котором он является k-связным. Задача вычисления связности графа и задача поиска k непересекающихся путей между заданной парой вершин могут быть решены при помощи алгоритмов нахождения максимального потока. Ребро называется [[критическое ребро|критическим]] в k-связном графе, если после его удаления граф уже не будет k-связным. | ||
Задача нахождения k-вершинно-связного (k-реберно-связного) подграфа минимальной мощности, содержащего все вершины данного графа, носит название k-VCSS (соответственно, k-ECSS) и для <math>k \ge 2 \; </math> имеет недетерминированную полиномиальную временную сложность. Рассмотрим некоторые результаты поиска приближенных минимальных решений задач k-VCSS и k-ECSS. Основное внимание будет уделяться простым графам. Простой алгоритм | Задача нахождения k-вершинно-связного (k-реберно-связного) подграфа минимальной мощности, содержащего все вершины данного графа, носит название k-VCSS (соответственно, k-ECSS) и для <math>k \ge 2 \; </math> имеет недетерминированную полиномиальную временную сложность. Рассмотрим некоторые результаты поиска приближенных минимальных решений задач k-VCSS и k-ECSS. Основное внимание будет уделяться простым графам. Простой аппроксимационный алгоритм рассматривает ребра согласно некоторому порядку и удаляет ребра, не являющиеся критическими. В результате работы создается k-связный подграф, в котором все ребра являются критическими; можно показать, что этот алгоритм является алгоритмом 2-аппроксимации (он выдает решение с не более чем kn ребрами в графе с n вершинами, и поскольку каждая вершина имеет степень не менее k, можно утверждать, что в графе должно быть kn/2 ребер). | ||
Аппроксимационные алгоритмы, более эффективные относительно этого простого алгоритма, принадлежат к одной из двух категорий: алгоритмы на базе обхода в глубину (DFS) и на базе паросочетания. | |||
== Основные результаты == | == Основные результаты == | ||
| Строка 29: | Строка 29: | ||
Подходы на базе паросочетания | Подходы на базе паросочетания | ||
Некоторые алгоритмы | Некоторые аппроксимационные алгоритмы для вычисления k-ECSS и k-VCSS используют подграф минимальной мощности <math>D_k \;</math> в качестве отправной точки, дополняя его добавочными ребрами таким образом, чтобы удовлетворять ограничениям связности. При использовании этого подхода получаются лучшие коэффициенты, чем при использовании подхода на базе DFS. | ||
| Строка 35: | Строка 35: | ||
'''Алгоритм вычисления k-ECSS с коэффициентом <math>1 + \frac{2}{k+1}</math>'''. Теорема Мадера о циклах, порожденных критическими ребрами, действует только для вершинной связности, но не для реберной. В силу этого был предложен отдельный алгоритм для вычисления k-ECSS в графах, являющихся k-реберно-связными, но не являющихся k-связными. Этот алгоритм находит подграф <math>D_k \;</math> минимальной мощности и дополняет его минимальным количеством добавочных ребер, делая подграф k-реберно-связным. Количество ребер, добавленных на последнем этапе, не превышает | '''Алгоритм вычисления k-ECSS с коэффициентом <math>1 + \frac{2}{k+1}</math>'''. Теорема Мадера о циклах, порожденных критическими ребрами, действует только для вершинной связности, но не для реберной. В силу этого был предложен отдельный алгоритм для вычисления k-ECSS в графах, являющихся k-реберно-связными, но не являющихся k-связными. Этот алгоритм находит подграф <math>D_k \;</math> минимальной мощности и дополняет его минимальным количеством добавочных ребер, делая подграф k-реберно-связным. Количество ребер, добавленных на последнем этапе, не превышает <math>\frac{k}{k+1} (n-1)</math>. Поскольку количество добавленных на первом этапе ребер не превышает Opt, общее число ребер в итоге не превышает <math>(1 + \frac{2}{k+1}) Opt</math>. | ||
Улучшенные алгоритмы для малых значений k. Для k 2 | '''Улучшенные алгоритмы для малых значений k'''. Для <math>k \in \{ 2, 3 \}</math> алгоритмы были улучшены за счет более аккуратного применения вышеизложенных действий, удаления не являющихся необходимыми ребер и получения улучшенных нижних границ. Для k = 2 может быть получена аппроксимация с коэффициентом 4/3 при помощи формирования покрытия путями и циклами с минимальной мощностью <math>D_2 \; </math> и 2-связывания их с «основным» компонентом, по одному на каждом шагу. Небольшие циклы и пути позволяют удалять ребро, когда они 2-связаны с ядром, что обеспечивает возможность применения простого амортизационного анализа. Можно обобщить этот метод на задачу 3-ECSS и получить аппроксимацию с коэффициентом 4/3. | ||
Были предложены гибридные подходы, использующие покрытие путями и циклами для создания специфического DFS-дерева исходного графа и затем организации 2- | Были предложены гибридные подходы, использующие покрытие путями и циклами для создания специфического DFS-дерева исходного графа и затем организации 2-связывания дерева в стремлении к удалению ребер везде, где это возможно. Использование таких подходов позволяет получить следующие коэффициенты аппроксимации в лучшем случае: 5/4 для задачи 2-ECSS, 9/7 для 2-VCSS и 5/4 для 2-VCSS в 3-связных графах. | ||
== Применение == | == Применение == | ||
| Строка 48: | Строка 48: | ||
== Литература == | == Литература == | ||
Дополнительную информацию о DFS, паросочетаниях и покрытии путями и циклами можно найти в [ ]. Быстрые алгоритмы 2-аппроксимации для задач k-ECSS и k-VCSS изучали Нагамочи и Ибараки [13]. Алгоритмы на базе DFS для задачи 2-связности были предложены Хуллером и Вишкином [11]. Они получили следующие коэффициенты аппроксимации: 3/2 для задачи 2-ECSS, 5/3 для 2-VCSS и 2 для взвешенной k-ECSS. Значение коэффициента для 2-VCSS было улучшено в следующих работах: до 3/2 – Гарг и коллеги [6], до 4/3 – Вемпала и Ветта [14], до 9/7 – Губбала и Рагавачари [ ]. Хуллер и Рагавачари [10] предложили алгоритм для задачи k-ECSS, который впоследствии был улучшен Габовым [4], показавшим, что алгоритм достигает соотношения 1.61. Чериян и коллеги [ ] изучали задачу k-VCSS для взвешенных ребер и разработали алгоритм | Дополнительную информацию о DFS, паросочетаниях и покрытии путями и циклами можно найти в [3]. Быстрые алгоритмы 2-аппроксимации для задач k-ECSS и k-VCSS изучали Нагамочи и Ибараки [13]. Алгоритмы на базе DFS для задачи 2-связности были предложены Хуллером и Вишкином [11]. Они получили следующие коэффициенты аппроксимации: 3/2 для задачи 2-ECSS, 5/3 для 2-VCSS и 2 для взвешенной k-ECSS. Значение коэффициента для 2-VCSS было улучшено в следующих работах: до 3/2 – Гарг и коллеги [6], до 4/3 – Вемпала и Ветта [14], до 9/7 – Губбала и Рагавачари [7]. Хуллер и Рагавачари [10] предложили алгоритм для задачи k-ECSS, который впоследствии был улучшен Габовым [4], показавшим, что алгоритм достигает соотношения 1.61. Чериян и коллеги [2] изучали задачу k-VCSS для взвешенных ребер и разработали аппроксимационный алгоритм со сложностью O(log k) для графов, содержащих не менее <math>6k^2 \;</math> вершин. | ||
Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [ ]. Они предложили алгоритмы с коэффициентами 1 + \ для k-VCSS, 1 + | |||
Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [1]. Они предложили алгоритмы с коэффициентами <math>1 + \frac{1}{k}</math> для k-VCSS, <math>1 + \frac{2}{k+1}</math> для k-ECSS, <math>1 + \frac{1}{k}</math> для k-VCSS в ориентированных графах и <math>1 + \frac{4}{ \sqrt{k} }</math> для k-ECSS в ориентированных графах. Вемпала и Ветта [14] сумели получить коэффициент 4/3 для задачи 2-VCSS. Далее результат улучшили Криста и Кумар [12], предложившие гибридный подход, при помощи которого Джоти и коллеги разработали алгоритм с коэффициентом 5/4 [9]. Алгоритм 3/2-аппроксимации для задачи 3-ECSS, предложенный Габовым [5], работает на мультиграфах, тогда как более ранний алгоритм Черияна и Туримеллы позволяет получить такое же значение коэффициента только на простых графах. Губбала и Рагавачари улучшили это значение до 4/3 [8]. | |||
| Строка 79: | Строка 80: | ||
14. Vempala, S., Vetta, A.: Factor 4/3 approximations for minimum 2-connected subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX. Lecture Notes in Computer Science, vol. 1913, pp. 262-273. Springer, Berlin (2000) | 14. Vempala, S., Vetta, A.: Factor 4/3 approximations for minimum 2-connected subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX. Lecture Notes in Computer Science, vol. 1913, pp. 262-273. Springer, Berlin (2000) | ||
[[Категория: Совместное определение связанных терминов]] | |||
