Набор Edge Dominating - Википедия - Edge dominating set

Примеры множеств с преобладанием ребер.

В теория графов, набор с доминирующим краем для графика г = (VE) является подмножеством D ⊆ E так что каждый край не в D примыкает хотя бы к одному ребру в D. Набор с преобладанием ребер также известен как набор доминирующих линий. Рисунки (a) - (d) представляют собой примеры множеств с преобладанием ребер (толстые красные линии).

А минимальный набор доминирующих краев - множество с преобладанием наименьшего ребра. Рисунки (a) и (b) являются примерами минимальных множеств с преобладанием ребер (можно проверить, что для этого графа нет множества с преобладанием ребер размера 2).

Свойства

Набор с доминирующим краем для г это доминирующий набор для своего линейный график L(г) и наоборот.

Любые максимальное соответствие всегда является множеством с преобладанием ребра. Рисунки (b) и (d) являются примерами максимального соответствия.

Кроме того, размер минимального набора с преобладанием ребер равен размеру минимальное максимальное соответствие. Минимальное максимальное соответствие - это минимальное множество с преобладанием ребер; Рисунок (b) представляет собой пример минимального максимального соответствия. Минимальный набор с преобладанием ребер не обязательно является минимальным максимальным соответствием, как показано на рисунке (а); однако, учитывая минимальный набор доминирующих ребер D, легко найти минимальное максимальное соответствие с |D| ребра (см., например, Яннакакис и Гаврил 1980 ).

Алгоритмы и вычислительная сложность

Определение того, существует ли множество с преобладанием ребер заданного размера для данного графа, является НП-полный проблема (и, следовательно, нахождение минимального набора с преобладанием ребер является NP-жесткий проблема). Яннакакис и Гаврил (1980) показать, что задача NP-полна даже в случае двудольный граф с максимальной степенью 3, а также в случае планарный граф с максимальной степенью 3.

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

Также взвешенная по краям версия задачи может быть аппроксимирована с точностью до множителя 2, но алгоритм значительно сложнее (Фудзито и Нагамочи 2002; Парех 2002 ).

Хлебик и Хлебикова (2006) показать, что найти приближение лучше, чем (7/6), NP-сложно.

использованная литература

  • Аузиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости, Springer.
Набор минимальных доминирующих ребер (оптимизационная версия) - это задача GT3 в Приложении B (стр. 370).
Минимальное максимальное соответствие (оптимизационная версия) - это проблема GT10 в Приложении B (стр. 374).
Множество с преобладанием ребер (вариант решения) обсуждается в рамках задачи о доминирующем множестве, которой является проблема GT2 в Приложении A1.1.
Минимальное максимальное соответствие (вариант решения) - это проблема GT10 в Приложении A1.1.

внешние ссылки

Минимальный набор доминирования края,
Минимальное максимальное соответствие.