Дробный доминирующий набор ⇐ Васина Википедия

[wiki_en]

В теории графов «дробное доминирующее множество» — это обобщение концепции доминирующего множества, которое позволяет вершинам присваивать дробные веса от 0 до 1, а не двоичное членство. Эта релаксация превращает проблему доминирования в задачу линейного программирования, часто давая более точные границы и позволяя выполнять вычисления за полиномиальное время.

== Определение ==

Пусть G = (V, E) — граф. '''Дробная доминирующая функция''' — это функция f: V \to [0, 1] такая, что для каждой вершины v \in V сумма f по окрестности (теория графов)|замкнутой окрестности N[v] равна как минимум 1:
:\sum_{u \in N[v]} f(u) \geq 1

'''Дробное доминантное число''' \gamma_f(G) — это минимальный общий вес дробной доминантной функции:

:\gamma_f(G) = \min\left\{\sum_{v \in V} f(v)\right\}

== Свойства ==

Для любого графа G дробное число доминирования удовлетворяет:

:\gamma_f(G) \leq \gamma(G) \leq \Gamma(G) \leq \Gamma_f(G)

где \gamma(G) — число доминирования, \Gamma(G) — верхнее число доминирования, а \Gamma_f(G) — верхнее дробное число доминирования.

Дробное число доминирования можно вычислить как решение линейной программы, используя сильную двойственность.

Для любого графа G с n вершинами минимальная степень \delta и максимальная степень \Delta:

:\frac{n}{\Delta + 1} \leq \gamma_f(G) \leq \frac{n}{\delta + 1

== Формулы для конкретных семейств графов ==

Для регулярного графа|
:\gamma_f(G) = \frac{n}{k+1}

Для полного двудольного графа K_{r,s}:

:\gamma_f(K_{r,s}) = \frac{r(s-1) + s(r-1)}{rs - 1

Некоторые классы графов имеют \gamma_f(G) = \gamma(G):

* Дерево (теория графов)|Деревья
* Блочные графы (графы, в которых каждый блок завершен)
* Сильно хордальные графы

Для сильного произведения графов G \boxtimes H:

:\gamma_f(G \boxtimes H) = \gamma_f(G) \cdot \gamma_f(H)

Для декартова произведения графов G \square H (гипотеза Визинга, дробная версия):

:\gamma_f(G \square H) \geq \gamma_f(G) \cdot \gamma_f(H)

== Вычислительная сложность ==

Поскольку дробное число доминирования можно сформулировать в виде линейной программы, его можно вычислить за полиномиальное время, в отличие от стандартного числа доминирования, вычислить которое NP-трудно.

== Варианты ==

«Функция, доминирующая по дробному расстоянию» обобщает концепцию, требуя, чтобы для каждой вершины v сумма по ее окрестностям расстояния k N_k[v] (вершины на расстоянии не более k от v) была не менее единицы. Соответствующее '''число доминирования k-го дробного расстояния''' обозначается \gamma_{kf}(G).

Для k-регулярных графов и конкретных значений k существуют точные формулы. Например, для циклов C_n:

:\gamma_{kf}(C_n) = \frac{n}{2k+1}

«Эффективная дробная доминирующая функция» удовлетворяет

:\sum_{u \in N[v]} f(u) = 1

для всех вершин v. Не все графики допускают эффективные дробные доминирующие функции.

«Дробная общая доминирующая функция» требует, чтобы для каждой вершины v сумма по ее открытой окрестности N(v) (исключая сам v) была не менее единицы. '''Дробное общее число доминирования''' обозначается \gamma_{ft}(G).

'''Верхнее дробное доминантное число''' \Gamma_f(G) — это максимальный вес среди всех минимальных дробных доминантных функций.

== См. также ==

* Доминирующий набор
* Линейное программирование
* Раскраска дробного графика

Теория графов
Инварианты графа
Вычислительные задачи в теории графов

Подробнее: https://en.wikipedia.org/wiki/Fractional_dominating_set