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

Определения Связное доминирующее множество графа G — это множество D вершин с двумя свойствами: Из любого узла в D можно перейти в любой другой узел в D по пути, полностью находящемся внутри D. То есть D порождает связный подграф графа G. Любая вершина в G либо принадлежит D, либо смежна с вершиной из D. То есть D является доминирующим множеством графа G. Наименьшее связное доминирующее множествоЧасто встречается Минимальное связное доминирующее множество. В русскоязычной литературе наблюдается большая путаница слов максимальный и наибольший (соответственно, минимальный и наименьший). Обычно под максимальным понимается элемент, который нельзя расширить, а под наибольшим понимается элемент с максимальной числовой характеристикой (сравните, например, максимальное паросочетание и наибольшее паросочетание) графа G — это связное доминирующее множество с наименьшей мощностью среди всех связных доминирующих множеств графа G. Число связного доминирования графа G — это число вершин в наименьшем связном доминирующем множестве.

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

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

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

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

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

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

Если рассматривать задачи в терминах аппроксимационных алгоритмов, связное доминирование и максимальная листва остовных деревьев не то же самое — аппроксимация одной задачи с данным аппроксимационным коэффициентом не то же самое, что аппроксимация другой задачи с тем же коэффициентом. Существует аппроксимация для задачи поиска наименьшего связного доминирующего множества с коэффициентом , где Δ означает максимальную степень вершин в графе G. Задача нахождения остовного дерева с максимальной листвой трудна, откуда следует, что, по всей видимости, не существует приближенной схемы полиномиального времени. Однако задачу можно аппроксимировать с коэффициентом 2 за полиномиальное время.

Обе задачи можно решить на графах с n вершинами за время . Задача о максимальной листве , что означает — её можно решить за время, экспоненциально зависящее от числа листьев, но лишь полиномиально от размера графа. этих алгоритмов (интуитивно, это число листьев, для которого алгоритм работает приемлемое время) постепенно выросло по мере улучшения алгоритмов примерно до 37 и есть предположения, что значение 50 можно достичь.

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

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

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

Литература

Категория:Вычислительные задачи теории графов Категория:Связность графа