Wie erkenne ich ob ein Graph planar is?
Ich weiß, dass ein Graph nicht planar ist wenn er K5 oder K3,3 enthält, wie erkenne ich jedoch das der Graph K5 oder K3,3 enthält, wonach muss ich schauen ? Woran kann ich das genau sehen. Ich verstehe darunter irgendwie das der Graph ab 5 Knotenpunkten nicht mehr planar sein kann. Hier ein Beispiel graph
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik, Informatik
Ein planarer Graph kann in der Ebene ohne Kantenüberschneidungen gezeichnet werden. Das ist im Bild ja offensichtlich der Fall.
Das mit K₅ und K₃,₃ ist nur interessant, um zu beweisen, dass ein Graph nicht planar ist.