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

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

0 голосов
/ 20 марта 2020
  1. написать алгоритм для поиска остовного дерева с максимальным числом листьев.
  2. написать алгоритм для поиска остовного дерева с минимальным количеством узлов.

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

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

1 Ответ

0 голосов
/ 20 марта 2020

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

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

Таким образом, для обеих задач вам необходимо разработать приближенные алгоритмы.

...