остовных деревьев с минимальным количеством листьев

Question

Так моя проблема заключается в следующем:

У меня неориентированный (полное) взвешенный граф G = (V, E), и я хотел бы, чтобы генерировать все возможные связующих деревьев с минимальным количеством листьев, т. е. с минимальным количеством вершин степени 1. Назовем этот вид деревьев MIN_LEAF.

Возможно, я хотел бы напрямую генерировать, среди всех деревьев с минимальным количеством листьев, тот, который имеет также минимальный общий вес (обратите внимание, что это не обязательно минимальное покрывающее дерево). Является ли проблема принятия решения о том, является ли дерево T MIN_LEAF для заданного графа G NP-полным?

Если это так, мне интересно, существует ли какой-то эвристический алгоритм (жадный или локальный поиск), который может хотя бы дать приблизительное решение этой проблемы.

Заранее спасибо.

Answer 1

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

Быстрый поиск в Google показал бумагу "On finding spanning trees with few leaves", которая кажется хорошей отправной точкой для алгоритмов аппроксимации (они имеют 2-приближение для произвольных графов) и дальнейшего чтения на эту тему.