Spanning Trees mit minimalen Anzahl von Blättern

Question

Also mein Problem ist folgendes:

Ich habe eine ungerichtete (komplett) Graph G = (V, E), und ich möchte alle möglichen Spannbäume erzeugen mit minimaler Anzahl von Blättern, dh mit einer minimalen Anzahl von Scheitelpunkten von Grad 1. Nennen wir diese Art von Bäumen MIN_LEAF.

Möglicherweise würde ich direkt wie zu generieren, unter allen Bäumen mit minimaler Anzahl von Blättern, die eine, die auch das Mindestgesamtgewicht hat (bitte beachten Sie, dass dies ein Minimum Spanning Tree ist nicht unbedingt). Ist das Problem zu entscheiden, ob ein Baum T ist ein MIN_LEAF für einen gegebenen Graphen G NP-vollständig?

Wenn ja, frage ich mich, ob eine Art heuristischer Algorithmus existiert (gierige oder lokale Suche), der zumindest eine ungefähre Lösung für dieses Problem bieten kann.

Vielen Dank im Voraus.

Answer 1

Das erste Problem, das Sie beschrieben haben - einen Spanning Tree mit möglichst wenigen Blättern zu finden - ist NP -hard. Sie können dies sehen, indem Sie das Hamilton-Pfadproblem auf dieses Problem reduzieren: Beachten Sie, dass ein Hamilton-Pfad ein spannender Baum eines Graphen ist und nur zwei Blattknoten hat und dass jeder Spannbaum eines Graphen mit genau zwei Blattknoten ein Hamilton-Operator sein muss Pfad. Dies bedeutet, dass das schwierige Problem der Bestimmung, ob ein Hamilton-Pfad in einem Graph existiert, gelöst werden kann, indem der Minimum-Leaf-Spanning-Tree des Graphen gefunden wird: Der Pfad existiert genau dann, wenn der Minimum-Leaf-Spanning Tree genau existiert Zwei Blätter. Das zweite Problem, das Sie beschrieben haben, enthält dieses erste Problem als Sonderfall und wird daher auch NP -hard sein.

Eine schnelle Google-Suche ergab das Papier "On finding spanning trees with few leaves", das scheint, es könnte ein guter Ausgangspunkt für Approximationsalgorithmen sein (sie haben eine 2-Approximation für beliebige Graphen) und weitere Lektüre zu dem Thema.