np-полнота в связующем дереве с ограниченной степенью

Question

Я понимаю, почему связующее дерево с ограниченными степенями считается NP Завершенным со степенью или 2 (это пример задачи о гамильтоновом пути), но я не понимаю, почему это относится к степеням> 2. Если кто-то может объяснитьпочему это NP Полная задача для степени> 2, было бы очень полезно

Answer 1

Ну, я думаю, что вы можете сделать простое сокращение от экземпляра, ограниченного 2, до экземпляра General k.

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

Формальное сокращение будет:

F (V, E) = (V ', E'), когда: V '= {(v, i) | vв исходном графе 0 Удачи и надеюсь, что это помогло:)