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

Question

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

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

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

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

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

Answer 1

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

В результате быстрого поиска в Google появилась статья "О нахождении остовных деревьев с несколькими листьями", которая кажется хорошей отправной точкой для алгоритмов аппроксимации (они имеют 2-аппроксимацию для произвольных графиков) и дальнейшего изучения предмета.