Minimaler Spanning-Baum eines vollständigen Graphen

-1

Angenommen G = (V, E) ist eine vollständige Grafik.Minimaler Spanning-Baum eines vollständigen Graphen

Die Scheitelpunkte sind eine Menge von Punkten in der Ebene und die Kanten sollten Liniensegmente zwischen den Punkten sein. Das Gewicht jeder Kante [a, b] sei die Länge des Segments "ab".

über Prim-Algorithmus und Kruskals Algorithmus Nach der Lektüre, ich habe einige gute Kenntnis, dass diese gierigen Algorithmen, um den minimalen Spannbaum ein Graphen ausgegeben.

Meine Frage ist: Nachdem ein Minimum Spanning Tree von G zu erhalten, Gibt es eine Möglichkeit zu beweisen, dass der minimale Spannbaum von G ein ebener Graph ist?

Quelle

2017-11-30 arsalunic612

Mein Bauch sagt, dass alle Bäume sind planar. Wähle eine Wurzel aus. Setzen Sie es auf Zeile Null Spalte Null. Fügen Sie seine untergeordneten Elemente in Zeile eins in separaten Spalten hinzu. Wiederholen Sie das, jedes Mal, wenn Sie die Eltern nach rechts verschieben, um sich mit dem linken der direkten Kinder in der nächsten Reihe auszurichten. Jetzt schneidet keine der Kanten. – Patrick87

alle Bäume sind zwei färbbar - so muss es nach dem Vierfarbsatz eben sein. –

@ Patrick87 Das OP betrachtet eine Menge von Punkten in der Ebene mit spezifischen Startkoordinaten, wobei die Längen der Kanten die tatsächlichen Abstände zwischen den Punkten sind. Es ist sicherlich möglich, einen Baum zu konstruieren, an dem sich die Linien kreuzen, wenn die Punkte im Raum fixiert sind. Die Frage ist, dass bei einer Menge von Punkten, die in Räume mit spezifischen Koordinaten eingebettet sind, sich irgendeine der Kanten der MST schneidet (außer an Endpunkten). – Dave

Sie können überprüfen, ob der minimale Spannbaum wie jedes Diagramm eben ist. Es gibt eine einfache Möglichkeit zu überprüfen, ob ein Diagramm planar ist. Die sehr bekannt Euler Formel

„Wenn G eine zusammenhängende ebene Graph mit e Kanten und v Vertices, wo v> = 3, dann < e = 3 V - 6. Auch G kann nicht eine Ecke vom Grad von mehr als 5.“

oder Sie können auf der folgenden Methode verlassen:

Satz -„haben Lassen G sein eine verbunden einfachen planaren Graphen mit e Kanten und v Vertices. Dann ist die Anzahl der Flächen f im Diagramm gleich f = e-v + 2.“

Euler zeigte auch, dass für jedes angeschlossene ebenen Graphen, gilt die folgende Beziehung:

v - e + f = 2.

Gut Glück

Quelle

2017-11-30 01:12:52 enyard

Dieser Beweis ist für planaren Graph ich glaube. gibt es einen Beweis für ein Flugzeug-Diagramm? – arsalunic612

Minimaler Spanning-Baum eines vollständigen Graphen

Antwort

Verwandte Themen