Planarität
-
Das ist eine alte Klausur-Aufgabe:
Zeigen Sie dass der Grph des Posets nicht planar ist:
http://mstg.bplaced.net/Poset.jpg
Ich wüsste gern die Lösung sowie allgemeine Tipps zu solchen Fragestellungen.
Ebenfalls:
Beweisen Sie dass der vollständige planare Graph mit 5 Knoten nicht planar ist.
Auch hier she ich alt aus...
-
shisha schrieb:
Das ist eine alte Klausur-Aufgabe:
Zeigen Sie dass der Grph des Posets nicht planar ist:
http://mstg.bplaced.net/Poset.jpg
Ich wüsste gern die Lösung sowie allgemeine Tipps zu solchen Fragestellungen.Der K5 und der K3,3 sind nicht plättbar. Da würde ich zuerst suchen, ob einer der bei9den in Deinem Graphen enthalten ist.
edit: http://de.wikipedia.org/wiki/Satz_von_Kuratowski#Die_Graphen_K3.2C3_und_K5Für K3,3 und K5 nimmt man anscheinend gerne den Polyedersatz. http://www.mathematik.uni-kassel.de/~meister/Vorlesungen/SS_04/El_Geo/ElGeo_K1_fin.pdf
-
ich finde den K_3,3 nicht, der enthalten sein muss. K_5 geht ja nicht da ich keine Valenz 5 an einem Knoten habe.
Aber wie finde ich den vollst. bipartiten Graphen mit je 3 Knoten?
-
Es muss nicht unbedingt der K3,3 enthalten sein, eine Unterteilung davon reicht. Unterteilung bedeutet, dass du eine oder mehrere Kanten durch Pfade ersetzt, also Knoten einfügst.
-
In diesem Skript: http://i11www.iti.uni-karlsruhe.de/_media/teaching/sommer2009/planargraphs/vorlesung.pdf ist eine Beweisskizze dafür, dass K_5 nicht planar ist. Auch die Euler-Formel, mit der man einfach nachrechnen kann, dass K_5 zu viele Kanten hat um planar zu sein, wird dort bewiesen.
