4551
правка
Связность графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 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. | ||
| Строка 48: | Строка 48: | ||
== Литература == | == Литература == | ||
Дополнительную информацию о 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. Чериян и коллеги [ ] изучали задачу 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. Чериян и коллеги [ ] изучали задачу k-VCSS для взвешенных ребер и разработали аппроксимационный алгоритм со сложностью O(log k) для графов, содержащих не менее <math>6k^2 \;</math> вершин. | ||
Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [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]. | Алгоритмы на основе паросочетания впервые ввели Чериян и Туримелла [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]. | ||