Ich verstehe irgendwie nicht wie man Zeigen kann, ob ein Graph planar ist oder nicht. Ich weiß, dass es möglich sein muss, für diesen Graphen eine planare Einbettung zu machen.
Planare Einbettung heißt, dass man ermöglichen muss, diese Knoten so zu verbinden, dass die Kanten sich nicht kreuzen.
Ich hoffe ihr könnt mir helfen
Der erste Graph ist nicht planar, weil der durch {b, d, e, f, g} induzierte Teilgraph der K5 ist.
Der zweite Graph ist nicht planar, weil er K3,3 als Teilgraphen enthält. Partitionen sind {a, c, d} und {b, e, f}.
Der dritte Graph ist planar.
Versuche vielleicht deine Graphen aufzufalten.
Beim 1. Beispiel kannst du damit beginnen, dass du a nach links oben legst. Lege nun e sehr weit nach rechts unten und schaue mal, wie dein Graph nun aussieht.
cd und bf schneiden sich immer noch. Daher ist 1 wahrscheinlich nicht planar. Ausser du kannst noch besser auffalten.
Beim 3. Graphen kannst du c weit nach rechts unten legen und die Kanten von dort aus um die Figur rum zu den nötigen Knoten zeichnen. So bleiben keine überschneidende Kanten. Daher ist der 3. Graph planar.
Nachdem der erste das vermutlich nicht ist (vgl. mein erster Kommentar) und die Überschrift impliziert, dass genau einer der Graphen planar ist, muss es der dritte Graph sein.
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos
