dominierend ein Turnier Graphen

Question

Ich schreibe einen Algorithmus die dominierende Menge eines Turniers Graphen zu finden. Ist das Minimum Spanning Tree eines gerichteten Graphen entspricht die dominierende Menge des Graphen? Mit anderen Worten, wenn ich die kleinste MST für das Turnier Diagramm finden (indem sie durch alle Scheitel Iterieren), kann ich dann sagen, dass dies auf die dominierenden Menge des Graphen entspricht?

Answer 1

Die Wikipedia-Artikel , dass die Probleme, heißt es in einem dominierenden Satz zu finden und einen Spanning Tree finden äquivalent sind. Bei einem Spanning Tree, die Nicht-Blattknoten eine dominierende Menge bilden, und eine verbundene dominierende Menge gegeben, können Sie leicht von der ursprünglichen Graphen erhalten Verbinden einen Spanning Tree davon mit den Eckpunkten, die ihn nicht gehören. Um jedoch ein Minimum zu finden Spanning Tree und die Suche nach einem minimal dominiert Satz geben verschiedene Probleme. Ich denke, dass sie gleichwertig sind wieder, aber ich bin nicht sicher.

Answer 2

Nein, denn die MST alle Knoten des Graphen sind, und die dominierende Menge vielleicht nicht.

Siehe zum Beispiel der Grafik hier: http://en.wikipedia.org/ wiki / Tournament_ (graph_theory) Vertices 2 und 4 eine dominierende Menge schaffen, und nicht einen Spanning Tree.