Beispiel 452

[dj_m.o.h.t.]

Man untersuche die vollständigen Graphen Kn für n<=6 auf Planarität!

Lösung: I have no idea! Was ist eigentlich Planarität? *sehrangestrengtnachdenkentun*

[Geli]

ups, falsches Bsp...

:eek:

[Zentor]

Planarität heißt glaub ich dass sich keine Kanten überschneiden
mfg Zentor

[lj_scampo]

Ich glaube, die Lösung ist:

Graphen mit 1, 2 und 3 Knoten trivialerweise planar.
Graph mit 4 Knoten planar (siehe Zeichnung)
Graphen ab 5 Knoten nicht mehr planar (siehe Zeichnung)

Einen Beweis, dass ab 5 Knoten keine Planarität mehr gegeben ist, habe ich leider nicht. Durch herumprobieren kann man sich aber relativ schnell davon überzeugen.

[MarvinTheRobot]

also der K6 ist auch nicht planar. K6 ist aber dasselbe wie K3,3

und da in den folgenden K´s sowohl K5 als auch K3,3 enthalten sein kann gibts keine planarität mehr.

(Siehe BARON Buch. ;-))

mfg, Phil.

[Joachim]

stimmt, ab 5 gibt es keinen planaren graphen mehr...das besagt ja auch die berühmte eulersche polyederformel aus der man unter anderem ableiten kann, dass folgendes für die planarität gelten muß: |E| = 3*|V| - 6

[Joachim]

natürlich meinte ich es kann keinen VOLLSTÄNDIGEN planaren graphen ab 5 knoten geben....(zeit zum schlafen gehen...;-) )