Русская Википедия:Связное доминирующее множество
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
Определения
Связное доминирующее множество графа G — это множество D вершин с двумя свойствами:
- Из любого узла в D можно перейти в любой другой узел в D по пути, полностью находящемся внутри D. То есть D порождает связный подграф графа G.
- Любая вершина в G либо принадлежит D, либо смежна с вершиной из D. То есть D является доминирующим множеством графа G.
Наименьшее связное доминирующее множество[1] графа G — это связное доминирующее множество с наименьшей мощностью среди всех связных доминирующих множеств графа G. Число связного доминирования графа G — это число вершин в наименьшем связном доминирующем множествеШаблон:Sfn.
Любое остовное дерево T графа G имеет по меньшей мере два листа. Остовное дерево с максимальной листвой — это остовное дерево, имеющее максимально возможное число листьев среди всех остовных деревьев графа G. Максимальное число листьев графа G — это число листьев в остовном дереве с максимальной листвойШаблон:Sfn.
Дополнительность
Если d является числом связного доминирования графа G с n вершинами, где n > 2, и l — его максимальное число листьев, то три величины d, l и n связаны простым равенством
- <math>\displaystyle n=d + l.</math>Шаблон:Sfn.
Если D является связным доминирующим множеством, то существует остовное дерево в G, листья которого включают все вершины, не находящиеся в D — образуем остовное дерево подграфа, порождённого множеством D вместе с рёбрами, соединяющими каждую оставшуюся вершину v, не лежащую в D, с соседней v вершиной, принадлежащей D. Это показывает, что Шаблон:Nowrap
В обратном направлении, если T — любое остовное дерево в G, то нелистовые вершины в дереве T образуют связное доминирующее множество графа G. Это показывает, что Шаблон:Nowrap из этих двух полученных неравенств следует равенство Шаблон:Nowrap
Таким образом, в любом графе сумма числа связного доминирования и максимального числа листьев равна числу вершин графа. С вычислительной точки зрения это означает, что вычисление числа связного доминирования имеет ту же трудность, что и вычисление максимального числа листьев.
Алгоритмы
Задача проверки, существует ли связное доминирующее множество с размером, меньшим заданного порога, NP-полна, а такая задача эквивалентна проверке, существует ли остовное дерево, имеющее число листьев не меньше заданного. Таким образом можно полагать, что задачу нахождения минимального связного доминирующего множества и задачу поиска остовного дерева с максимальным числом листьев нельзя решить за полиномиальное время.
Если рассматривать задачи в терминах аппроксимационных алгоритмов, связное доминирование и максимальная листва остовных деревьев не то же самое — аппроксимация одной задачи с данным аппроксимационным коэффициентом не то же самое, что аппроксимация другой задачи с тем же коэффициентом. Существует аппроксимация для задачи поиска наименьшего связного доминирующего множества с коэффициентом Шаблон:Nowrap, где Δ означает максимальную степень вершин в графе GШаблон:Sfn. Задача нахождения остовного дерева с максимальной листвой Шаблон:Не переведено 5 трудна, откуда следует, что, по всей видимости, не существует приближенной схемы полиномиального времениШаблон:Sfn. Однако задачу можно аппроксимировать с коэффициентом 2 за полиномиальное времяШаблон:Sfn.
Обе задачи можно решить на графах с n вершинами за время Шаблон:MathШаблон:Sfn. Задача о максимальной листве Шаблон:Не переведено 5, что означает — её можно решить за время, экспоненциально зависящее от числа листьев, но лишь полиномиально от размера графа. Шаблон:Не переведено 5 этих алгоритмов (интуитивно, это число листьев, для которого алгоритм работает приемлемое время) постепенно выросло по мере улучшения алгоритмов примерно до 37Шаблон:Sfn и есть предположения, что значение 50 можно достичьШаблон:Sfn.
Приложения
Связные доминирующие множества полезны для вычисления маршрута для беспроводных децентрализованных самоорганизующихся сетей. В этих приложениях малое связное доминирующее множество используется в качестве магистрали передачи данных, а узлы, не принадлежащие этому множеству, передают сообщения через соседей, находящихся на магистралиШаблон:Sfn.
Максимальное число листьев используется для разработки Шаблон:Не переведено 5 алгоритмов — некоторые NP-трудные задачи оптимизации можно решить за полиномиальное время на графах с ограниченным максимальным числом листьевШаблон:Sfn.
См. также
- Универсальная вершина, вершина, которая (если таковая существует) даёт минимальное связное доминирующее множество размера 1
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- ↑ Часто встречается Минимальное связное доминирующее множество. В русскоязычной литературе наблюдается большая путаница слов максимальный и наибольший (соответственно, минимальный и наименьший). Обычно под максимальным понимается элемент, который нельзя расширить, а под наибольшим понимается элемент с максимальной числовой характеристикой (сравните, например, максимальное паросочетание и наибольшее паросочетание)
