Sind folgende Graphen Planar, wenn nein wie kann ich es zeigen?
1 Antwort
Es gibt zwei Möglichkeiten: Du machst das mit einem der Planaritätstest-Algorithmen, die du sicher in deinem Skript oder einem Buch finden kannst. Oder du "siehst" eine Möglichkeit, in dem Graphen einen K_5 oder K_33-Minor zu finden (Kuratowski-Kriterium). Dann ist der Graph nicht planar.
Für b) kann man z. B. die Knoten 1, 3, 6 und 9 zu einem Knoten A und die Knoten 5 und 8 zu einem Knoten B zusammenziehen. Der entstehende neue Graph ist dann der K_5, also ist b) nicht planar. Bei a) würde ich wohl nach einem K33 suchen, aber auf die Schnelle habe ich keinen gefunden.
kann man beim ersten , sozusagen Knoten4 und 7 ignorieren und trotzdem ist er nicht planar ?.
Man könnte ja Knoten 8,5 und Knoten 2,9 Zusammenziehen und dann Kommt der K5 raus ??