Planarität von Graphen

Aufrufe: 317     Aktiv: 23.05.2023 um 17:08
0

Ist dieser Graph planar? 
Ich dachte er wäre es nicht, aber habe dann eulerschen Polyedersatz angewandt um einen Widerspruch zu erhalten und bin leider zu keinem gekommen.... Jetzt bin ich mir unsicher, ob er vllt doch planar ist.

EDIT vom 23.05.2023 um 15:38:

Die Lösung:
Diese Frage melden
gefragt

Student, Punkte: 79

 
Kommentar schreiben
1 Antwort
0
Ich komme schon darauf, dass die Gleichung aus dem EPsatz nicht erfüllt ist. Was hast Du denn für die drei Größen erhalten?
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.93K

 
Knotenmenge = 19, Kantenmenge = 45 und mit der Formel aus dem Polyedersatz: Facetten = 28.   ─   emiliahlg 18.05.2023 um 17:26
Kann man denn die Facetten einfach zählen? Ich dachte, das könnte man nicht machen, da ja die obige Darstellung nur eine von vielen ist und sich bei einer anderen Skizze auch die Facetten ändern könnten...
   ─   emiliahlg 18.05.2023 um 18:08
Hm, ich musste auch nochmal weiter nachlesen (Thema ist eine Weile her bei mir). Du hast recht, die Facetten kann man nur bei einer planaren Einbettung zählen - wenn es eine gibt.
Wenn der Graph also planar ist, dann gibt es eine p. Einbettung, bei der zählt man durch und die EP-Formel gilt. Und zwar unabhängig von der Einbettung (kann ja versch. geben). Die obige Darstellung ist aber wg der Überschneidungen keine planare Einbettung, daher kann man daran die F nicht zählen.
Dann geht es nicht mit der EP-Formel. Ich überleg nochmal weiter.   ─   mikn 18.05.2023 um 19:19
Meine andere Idee ist der Sechsfarbensatz... Aber da bin ich mir auch nicht sicher, ob es klappt.   ─   emiliahlg 18.05.2023 um 21:38
Ich habe jetzt diverse Kriterien für nicht-planar ausprobiert, keines greift. Die Färbung hatte ich als erstes probiert, ich meine man kommt mit 4 Farben aus und dann greift das Kriterium auch nicht.
Vielleicht ist K_3,3 ein Minor? Sehe ich nicht auf Anhieb, ein Teilgraph ist K_3,3 jedenfalls nicht.   ─   mikn 18.05.2023 um 21:47
Das mit den Minoren hab ich schon im Internet gelesen, das haben wir aber in der Vorlesung noch nicht gemacht... Deshalb darf ich es eigentlich noch nicht verwenden.
Ich habe das Übungsblatt mittlerweile schon abgegeben, falls es dich interessiert kann ich dann die Lösung hier noch reinschreiben, wenn ich sie hab :) Und danke für den Aufwand! :)   ─   emiliahlg 19.05.2023 um 08:24
Ja, gerne, mach das. Bin gespannt. Sorry, dass ich nicht wirklich helfen konnte. War aber interessant mich mit dieser Frage zu beschäftigen.   ─   mikn 19.05.2023 um 11:05
Habe die Lösung hochgeladen :) Der Sinn der Aufgabe war tatsächlich darauf zu kommen, dass man über K5 und K3,3 die Nicht-Planarität nachweisen kann, aber das wurde leider nicht gut kommuniziert, weil eigentlich jeder gedacht hat, dass man die Bedingung nur verwenden darf, wenn sie im Skript stand...   ─   emiliahlg 23.05.2023 um 15:41
Ok, danke. Ich verstehe es so, dass in der Vorlesung/Skript stand, dass K5 und K3,3 nicht planar sind. In der Aufgabe sollte man dann wohl selbst drauf kommen, dass als Nachweis auch K3,3 als Minor (die Sache mit dem f in der Lösung) ausreicht. Nunja, da wäre schon ein Tipp bei der Aufgabe angemessen gewesen. Ist ja auch mit diesem Tipp immer noch nicht-trivial (finde ich).
   ─   mikn 23.05.2023 um 17:08

Kommentar schreiben