Связующие деревья с минимальным количеством листьев

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

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

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

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

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


graph data-structures tree np spanning-tree
person user7427473    schedule 16.01.2017    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

person templatetypedef    schedule 16.01.2017
comment
Спасибо. Просто хочу добавить, что версия задачи с принятием решений является NP-полной: учитывая целое число k›=2, представляющее максимальное количество листьев, разрешенных в остовном дереве, графе G и дереве-кандидате решения T, проверить тривиально за полиномиальное время, если T является остовным деревом для G с числом листьев, меньшим или равным k. - person user7427473; 17.01.2017
comment
@ user7427473 Абсолютно. Как указано в исходном вопросе, у вас не было этого бита, поэтому я упомянул NP-твердость, а не полноту. - person templatetypedef; 17.01.2017