Связное доминирующее множество

Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.

Определения

Связное доминирующее множество графа G — это множество D вершин с двумя свойствами:

1. Из любого узла в D можно перейти в любой другой узел в D по пути, полностью находящемся внутри D. То есть D порождает связный подграф графа G.
2. Любая вершина в G либо принадлежит D, либо смежна с вершиной из D. То есть D является доминирующим множеством графа G.

Наименьшее связное доминирующее множество^[1] графа G — это связное доминирующее множество с наименьшей мощностью среди всех связных доминирующих множеств графа G. Число связного доминирования графа G — это число вершин в наименьшем связном доминирующем множестве^[2].

Любое остовное дерево T графа G имеет по меньшей мере два листа. Остовное дерево с максимальной листвой — это остовное дерево, имеющее максимально возможное число листьев среди всех остовных деревьев графа G. Максимальное число листьев графа G — это число листьев в остовном дереве с максимальной листвой^[3].

Дополнительность

Если d является числом связного доминирования графа G с n вершинами, где n > 2, и l — его максимальное число листьев, то три величины d, l и n связаны простым равенством

${\displaystyle \displaystyle n=d+l.}$^[4].

Если D является связным доминирующим множеством, то существует остовное дерево в G, листья которого включают все вершины, не находящиеся в D — образуем остовное дерево подграфа, порождённого множеством D вместе с рёбрами, соединяющими каждую оставшуюся вершину v, не лежащую в D, с соседней v вершиной, принадлежащей D. Это показывает, что l ≥ n − d.

В обратном направлении, если T — любое остовное дерево в G, то нелистовые вершины в дереве T образуют связное доминирующее множество графа G. Это показывает, что n − l ≥ d. из этих двух полученных неравенств следует равенство n=d + l.

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

Алгоритмы

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

Если рассматривать задачи в терминах аппроксимационных алгоритмов, связное доминирование и максимальная листва остовных деревьев не то же самое — аппроксимация одной задачи с данным аппроксимационным коэффициентом не то же самое, что аппроксимация другой задачи с тем же коэффициентом. Существует аппроксимация для задачи поиска наименьшего связного доминирующего множества с коэффициентом 2 ln Δ + O(1), где Δ означает максимальную степень вершин в графе G^[5]. Задача нахождения остовного дерева с максимальной листвой MAX-SNP^[англ.] трудна, откуда следует, что, по всей видимости, не существует приближенной схемы полиномиального времени^[6]. Однако задачу можно аппроксимировать с коэффициентом 2 за полиномиальное время^[7].

Обе задачи можно решить на графах с n вершинами за время O(1.9ⁿ)^[8]. Задача о максимальной листве фиксированно-параметрически разрешима^[англ.], что означает — её можно решить за время, экспоненциально зависящее от числа листьев, но лишь полиномиально от размера графа. Клам-значение^[англ.] этих алгоритмов (интуитивно, это число листьев, для которого алгоритм работает приемлемое время) постепенно выросло по мере улучшения алгоритмов примерно до 37^[9] и есть предположения, что значение 50 можно достичь^[10].

Приложения

Связные доминирующие множества полезны для вычисления маршрута для беспроводных децентрализованных самоорганизующихся сетей. В этих приложениях малое связное доминирующее множество используется в качестве магистрали передачи данных, а узлы, не принадлежащие этому множеству, передают сообщения через соседей, находящихся на магистрали^[11].

Максимальное число листьев используется для разработки фиксированно-параметрически разрешимых^[англ.] алгоритмов — некоторые NP-трудные задачи оптимизации можно решить за полиномиальное время на графах с ограниченным максимальным числом листьев^[3].

См. также

• Универсальная вершина, вершина, которая (если таковая существует) даёт минимальное связное доминирующее множество размера 1