Покрывающее дерево графа называется деревом полноты, если множество его листьев индуцирует полный подграф в графе хоста. Учитывая граф и целое число , какова сложность определения, содержит ли дерево полноты с максимум листами?
Причина для того, чтобы задать этот вопрос, состоит в том, что соответствующая проблема для деревьев независимости является NP-полной, здесь дерево независимости представляет собой остовное дерево, так что множество его листьев является независимым множеством в графе хоста.
Другая причина - этот вопрос (и соответствующие ответы). Оказывается, что каждое остовное дерево в является деревом полноты тогда и только тогда, когда является полным графом или циклом.
Я не могу победить Дэвида в элегантности его ответа. Но потратив много времени на обдумывание этой проблемы, я бы хотел предать вам свое решение;)
Пусть - фиксированное целое число. Для заданного построим следующим образом: возьмем две копии , и клику на вершинах , новой вершине , зафиксируем вершину и вершина . получается из и , соединяя с , соединяя с и соединяя всех соседейG H G 1 G 2 Q k x , x 1 , x 2 , … , x k - 1 y v 1 ∈ G 1 v 2 ∈ G 2 H G 1 , G 2 , Q y x v 1 x 1 , х 2 , … , х к - 1 Вk ≥ 2 г ЧАС г1 г2 Q К х , х1, х2, … , Хк - 1 Y v1∈ G1 v2∈ G2 ЧАС г1, Г2, Q Y Икс v1 Икс1, х2, … , Хк - 1 v2 v1 в и всех соседей в к .г1 v2 г2 Y
Тогда легко видеть, что имеет гамильтонов цикл, если и только если имеет дерево полноты с не более чем листьями.г ЧАС К
источник