Римское доминирующее множество

Римское доминирующее множество

В теории графов римское доминирующее множество (РДМ) — это особый тип доминирующего множества, вдохновлённый историческими военными стратегиями обороны Римской империи. Концепция моделирует сценарий, в котором города (вершины) могут быть защищены легионами, размещёнными либо в самом городе, либо в соседних городах. Город считается защищённым, если в нём размещён по крайней мере один легион, или если в нём нет легионов, но он соседствует с городом, в котором есть по крайней мере два легиона, что позволяет отправить один легион для обороны, оставляя исходный город всё ещё защищённым.

Число римского доминирования графа измеряет минимальное общее количество легионов, необходимое для защиты всех городов согласно этой стратегии.

Определение[править | править код]

Пусть $G = (V, E)$ — граф. Функция римского доминирования (ФРД) — это функция $f : V \to {0, 1, 2}$ , такая что для каждой вершины $v$ с $f (v) = 0$ существует вершина $u$ , смежная с $v$ , с $f (u) = 2$ .

Вес функции римского доминирования $f$ равен $w (f) = \sum_{v \in V} f (v)$ . Число римского доминирования $γ_{R} (G)$ — это минимальный вес среди всех функций римского доминирования для $G$ .

Эквивалентно, пусть $(V_{0}, V_{1}, V_{2})$ — упорядоченное разбиение $V$ , где $V_{i} = {v \in V : f (v) = i}$ . Тогда $f$ является функцией римского доминирования тогда и только тогда, когда каждая вершина в $V_{0}$ смежна по крайней мере с одной вершиной в $V_{2}$ . Это выполняется тогда и только тогда, когда $G$ имеет функцию римского доминирования минимального веса с $V_{1} = \emptyset$ .

Значение римского доминирования[править | править код]

Значение римского доминирования вершины расширяет концепцию римского доминирования, учитывая, сколько минимальных функций римского доминирования присваивают положительные значения этой вершине.

Для графа $G$ пусть $F$ — множество всех $γ_{R} (G)$ -функций (функций римского доминирования минимального веса). Для вершины $v \in V$ значение римского доминирования $R_{G} (v)$ определяется как:

R_{G} (v) = \sum_{f \in F} f (v)

Известны некоторые основные свойства значения римского доминирования: равенство выполняется тогда и только тогда, когда $G$ является $C_{5}$ или получен из $n / 5$ копий $P_{5}$ путём добавления связного подграфа на множестве центров.

Для любого графа $G$ с $n$ вершинами и $n \geq 3$ выполняется $5 \leq γ_{R} (G) + γ_{R} (\overline{G}) \leq n + 3$ .

Для любого графа $G$ с $n$ вершинами и $n \geq 160$ выполняется $γ_{R} (G) γ_{R} (\overline{G}) \leq 16 n / 5$ .

Если $G$ — связный граф с $n$ вершинами, $δ (G) \geq 2$ и $n \geq 9$ , то $γ_{R} (G) \leq 8 n / 11$ .

Алгоритмы и сложность[править | править код]

Задача принятия решения для римского доминирования является NP-полной, даже при ограничении на двудольные графы, хордальные графы или планарные графы. Однако существуют полиномиальные по времени алгоритмы для вычисления числа римского доминирования на интервальных графах, кографах и сильно хордальных графах.

См. также[править | править код]

Доминирующее множество
Разметка графа

Ссылки[править | править код]