Ich verstehe, warum der Bounded Degree Spanning Tree als NP Complete mit einem Grad oder 2 betrachtet wird (es ist eine Instanz des Hamiltonian Path Problems), aber ich verstehe nicht, warum dies für Grad & gt; 2. Wenn jemand erklären könnte, warum dies ein NP-Problem für Grad & gt; 2, wäre es am hilfreichsten
Nun, ich denke, dass Sie eine einfache Reduktion von der Instanz von bounded um 2 auf die Instanz von General k machen können.
Intuitiv werden wir mit jedem Knoten des ursprünglichen Graphen neue k-2 Knoten verbinden. Daher muss jeder aufspannende Baum die k-2 Kanten vom ursprünglichen Knoten zu den neuen Knoten enthalten, die wir mit ihm verbunden haben, und ein aufspannender Baum von Grad k existiert höchstens, wenn es einen aufspannenden Baum des Grades von höchstens 2 gibt Originalgraph.
Die formelle Kürzung wird sein:
F (V, E) = (V ', E'), wenn: V '= {(v, i) | v ist in dem ursprünglichen Graph, 0 & lt; i & lt; k + 1), E '= EU {((v, 0), (v, i))}, und ich schreibe keinen formalen Beweis für die Korrektheit, denn schließlich sind wir nicht in einem Mathe-Forum.
Viel Glück und hoffe, dass es geholfen hat:)
Tags und Links graph tree np-complete