Установка дуги обратной связи
-
Определение и свойства задачи о наборе дуг обратной связи
- Задача о наборе дуг обратной связи заключается в поиске минимального набора ребер, удаление которых приводит к ациклическому графу.
- Задача является NP-полной и имеет множество приложений в информатике и теории графов.
-
Сложность задачи
- Задача о задании дуги обратной связи является NP-полной для всех графов, включая плоские и турнирные.
- Для турниров задача остается NP-полной даже при ограничении на количество удаляемых ребер.
-
Аппроксимация и сложность
- Задача является APX-сложной и не имеет полиномиальных аппроксимаций с постоянным коэффициентом.
- Существуют гипотезы, которые предполагают, что задача трудно аппроксимируется за полиномиальное время или даже за экспоненциальное время.
-
Теоретические аспекты
- В плоских ориентированных графах задача подчиняется теореме min-max, которая связывает минимальный размер набора дуг обратной связи с максимальным числом направленных циклов.
- Гамильтоновы пути в турнирах соответствуют минимальным наборам дуг обратной связи и могут быть использованы для их определения.
- Ориентированные ациклические графы могут быть встроены в турнирные графики как уникальные наборы минимальных дуг обратной связи.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.