Учитывая невзвешенный граф, как мне найти остовное дерево с 1. Максимальное количество листьев 2 минимальное количество листьев

  1. Напишите алгоритм поиска остовного дерева с максимальным числом листьев.
  2. Напишите алгоритм поиска остовного дерева с минимальным количеством узлов.

Я пока не могу придумать решение для следующих вопросов.

В первой части я думал найти вершину с наивысшей степенью и поместить ее на предпоследний уровень так, чтобы последний уровень получил максимальное количество листьев.


graph algorithm spanning-tree
person Prateek Agrawal    schedule 20.03.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

Поэтому для обеих задач необходимо разработать алгоритмы аппроксимации.

person Deepu    schedule 20.03.2020