Остовное дерево с максимальным количеством листьев: различия между версиями

Задача построения остовного дерева с максимальным количеством листьев применяется в расчетах компьютерной графики с целью создания представлений полосы треугольников для быстрого интерактивного рендеринга [5]. Также она находит применение в области перераспределения трафика и проектирования сетей – например, для проектирования оптических сетей и распределения используемых длин волн для снижения стоимости сети – в терминах оконечного оборудования либо электронных переключателей [6]. Задача о минимальной энергии в беспроводных сетях заключается в нахождении радиус-вектора передачи для всех станций таким образом, чтобы полная мощность излучения всей сети была насколько возможно малой. Ограниченная версия этой задачи эквивалентна задаче нахождения остовного дерева с максимальным количеством листьев [ ]. Задача поиска остовных деревьев с большим числом листьев эквивалентна задаче поиска небольших связных доминирующих множеств и в связи с этим также носит название задачи о минимальном связном доминирующем множестве [13].