Wie erkenne ich das ein Graph planar ist?
Ich weiß, dass man es einfach zeichnen kann aber bei komplizierten Graphen ist das schwer,
Gibt es kein Rechenweg, Satz oder irgendwas?
1 Antwort
Generell ist es relativ schwer zu zeigen, dass ein Graph planar ist, ohne ihn zu zeichnen. Im wesentlichen musst du dafür zeigen, dass dieser Graph ein paar bestimmte Untergraphen nicht enthält: schau dir dafür den Satz von Kuratowski bzw Satz von Wagner an. Unter anderem müsstest du zeigen, dass keine Kombination von 5 Ecken vollständig verbunden sind, also K_5 (der Graph mit 5 Ecken und 10 Kanten) kein Untergraph ist.
Dafür gibt es einige Möglichkeiten (wenn man Glück hat) zu zeigen, dass etwas kein planarer Graph ist. Dafür benutzt du die Eulersche Polyederformel um aus der Anzahl der Ecken und Kanten die Anzahl der Flächen zu berechnen:
Flächen = Kanten + 2 - Ecken
und benutzt dann Abschätzungen dazu, ob das sein kann: zB muss in einem zusammenhängenden planaren Graphen mit mehr als einer Kante gelten, dass
2 Kanten >/= 3 Flächen.
Im Fall von K_5 würde das bedeuten, dass
Flächen = 10 + 2 - 5 = 7
und
20 >= 21, ein Widerspruch.
Deswegen ist zB K_5 nicht planar.
