4551
правка
Связность графа: различия между версиями
Материал из WEGA
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Неориентированный граф 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) и для k > 2 имеет недетерминированную полиномиальную временную сложность. Рассмотрим некоторые результаты поиска приближенных минимальных решений k-VCSS и k-ECSS. Основное внимание будет уделяться простым графам. Простой алгоритм аппроксимации рассматривает ребра согласно некоторому порядку и удаляет ребра, не являющиеся критическими. В результате работы создается k-связный подграф, в котором все ребра являются критическими; можно показать, что этот алгоритм является алгоритмом 2-аппроксимации (он выдает решение с не более чем kn ребрами в графе с n вершинами, и поскольку каждая вершина имеет степень не менее k, можно утверждать, что в графе должно быть kn/2 ребер). | Задача нахождения k-вершинно-связного (k-реберно-связного) подграфа минимальной мощности, содержащего все вершины данного графа, носит название k-VCSS (соответственно, k-ECSS) и для k > 2 имеет недетерминированную полиномиальную временную сложность. Рассмотрим некоторые результаты поиска приближенных минимальных решений k-VCSS и k-ECSS. Основное внимание будет уделяться простым графам. Простой алгоритм аппроксимации рассматривает ребра согласно некоторому порядку и удаляет ребра, не являющиеся критическими. В результате работы создается k-связный подграф, в котором все ребра являются критическими; можно показать, что этот алгоритм является алгоритмом 2-аппроксимации (он выдает решение с не более чем kn ребрами в графе с n вершинами, и поскольку каждая вершина имеет степень не менее k, можно утверждать, что в графе должно быть kn/2 ребер). | ||
Алгоритмы аппроксимации, более эффективные относительно этого простого алгоритма, принадлежат к одной из двух категорий: алгоритмы на базе обхода в глубину (DFS) и на базе паросочетания. | Алгоритмы аппроксимации, более эффективные относительно этого простого алгоритма, принадлежат к одной из двух категорий: алгоритмы на базе обхода в глубину (DFS) и на базе паросочетания. | ||
== Основные результаты == | == Основные результаты == | ||
