В теории графов , край доминирует набор для графа G = ( V , E ) представляет собой подмножество D ⊆ E таким образом, что каждое ребро не в D примыкает , по меньшей мере , одного края в D . Набор с преобладанием ребер также известен как набор с преобладанием линии . Рисунки (a) - (d) представляют собой примеры множеств с преобладанием ребер (толстые красные линии).
Набор с минимальным преобладанием ребер - это набор с наименьшим преобладанием ребер. Рисунки (a) и (b) представляют собой примеры минимальных множеств с преобладанием ребер (можно проверить, что для этого графа нет множества с преобладанием ребер размера 2).
Свойства [ править ]
Множество с преобладанием ребер для G является доминирующим множеством для его линейного графа L ( G ), и наоборот.
Любое максимальное совпадение всегда является множеством с преобладанием ребер. Рисунки (b) и (d) являются примерами максимального соответствия.
Кроме того, размер минимального набора с преобладанием ребер равен размеру минимального максимального соответствия . Минимальное максимальное соответствие - это минимальный набор с преобладанием ребер; Рисунок (b) представляет собой пример минимального максимального соответствия. Минимальный набор с преобладанием ребер не обязательно является минимальным максимальным соответствием, как показано на рисунке (а); однако, учитывая минимальное множество D с преобладанием ребер , легко найти минимальное максимальное соответствие с | D | края (см., например, Yannakakis & Gavril 1980 ).
Алгоритмы и вычислительная сложность [ править ]
Определение того, существует ли множество с преобладанием ребер заданного размера для данного графа, является NP-полной проблемой (и, следовательно, поиск минимального набора с преобладанием ребер является NP-трудной задачей). Яннакакис и Гаврил (1980) показывают, что проблема NP-полная даже в случае двудольного графа с максимальной степенью 3, а также в случае плоского графа с максимальной степенью 3.
Существует простой алгоритм полиномиальной аппроксимации с коэффициентом аппроксимации 2: найти любое максимальное совпадение. Максимальное соответствие - это множество с преобладанием ребер; кроме того, максимальное соответствие M может быть в худшем случае в 2 раза больше, чем наименьшее максимальное соответствие, а наименьшее максимальное соответствие имеет тот же размер, что и наименьшее множество с преобладанием ребер.
Также взвешенная по краям версия задачи может быть аппроксимирована с точностью до фактора 2, но алгоритм значительно сложнее ( Fujito & Nagamochi 2002 ; Parekh 2002 ).
Хлебик и Хлебикова (2006) показывают, что найти приближение лучше, чем (7/6), NP-сложно. Schmied & Viehmann доказали, что эту проблему сложно аппроксимировать с точностью до константы лучше 3/2.
Ссылки [ править ]
- Аузиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и приближение: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer.
- Набор минимального преобладающего ребра (оптимизационная версия) - это задача GT3 в Приложении B (стр. 370).
- Минимальное максимальное соответствие (оптимизационная версия) - это проблема GT10 в Приложении B (стр. 374).
- Хлебик, Мирослав; Chlebíková, Янка (2006), " О приближении твердость края доминирующие поставленных задач" , журнал комбинаторной оптимизации , 11 (3): 279-290, DOI : 10.1007 / s10878-006-7908-0.
- Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 CS1 maint: обескураженный параметр ( ссылка ).
- Множество с преобладанием ребер (вариант решения) обсуждается в рамках задачи о доминирующем множестве, которой является проблема GT2 в Приложении A1.1.
- Минимальное максимальное соответствие (вариант решения) - это проблема GT10 в Приложении A1.1.
- Яннакакис, Михалис ; Гаврила, Fanica (1980), "Край доминирующие множества в графах", SIAM журнал по прикладной математике , 38 (3): 364-372, CiteSeerX 10.1.1.477.4278 , DOI : 10,1137 / 0138030 , JSTOR 2100648 CS1 maint: обескураженный параметр ( ссылка ).
- Фудзито, Тошихиро; Нагамочи, Хироши (2002), «2-аппроксимационный алгоритм для задачи о множестве доминирования ребер с минимальным весом», Дискретная прикладная математика , 118 (3): 199–207, DOI : 10.1016 / S0166-218X (00) 00383-8.
- Парех, Оджас (2002), "Наборы с преобладанием ребер и гипоматрицы" , Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 287–291.
- Ричард Шмид и Клаус Виманн (2012), "Аппроксимирующее множество доминирующих ребер в плотных графах", Теор. Comput. Sci. 414 (1), стр. 92-99.
Внешние ссылки [ править ]
- Пьерлуиджи Крещенци, Вигго Канн, Магнус Халльдорссон, Марек Карпински, Герхард Вегингер (2000), «Сборник задач оптимизации NP» :
- Минимальный набор доминирования края ,
- Минимальное максимальное соответствие .
