 |
 |
 |
 |
 |
 |
Startseite » Forum » Zeigen, dass ein Graph nicht planar ist
Zeigen, dass ein Graph nicht planar ist
Universität / Fachhochschule
Graphentheorie
Tags: Graph, Graphentheorie, planar
 
|
  |
|---|
|
Hi Leute, die Aufgabe um die es geht, habe ich als Foto angehängt. Es geht mir hierbei eigentlich nur um die . Wie genau kann ich zeigen oder eher begründen, dass ein Graph nicht planar ist. Ich weiß, dass zum Beispiel der und der nicht planar sind. Würde es dann zum Beispiel auch ausreichen wenn ich den angegebenen Graphen zeichne und dann zeige, dass einer von ihnen ein Teilgraph des angegebenen Graphen ist oder ist das zu schwammig. Ich habe den Graphen jetzt gezeichnet, aber bekomme nicht genau den hin. Lg Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Ohne deine griff kennen kann man nichts das sagen ich weiss auch nicht was und sind Gruß ledum |
|
|
|
Hallo, Bilder unterliegen hier einem Größenlimit von 500 kB. Vielleicht sieht man dein Bild deshalb nicht? Was das Zeichnen anbelangt, so könnte es sein, dass dies nicht ausreicht. Vermutlich fährst du besser, wenn du die Knoten benennst und nachweist, dass es sich um einen bzw. eben einen handelt. @ledum: ist ein Graph mit 5 Knoten und allen Punktpaaren als Kanten. Manchmal nennt man ihn auch den vollständigen Graphen mit 5 Knoten. (Man kann ihn sich als ein Fünfeck vorstellen, in dem je zwei Knoten benachbart sind. So wie in der Erweiterung von "Schere, Stein, Papier".) Der ist ein vollständig bipartiter Graph, bei dem es zwei Gruppen zu je drei Knoten gibt, die innerhalb der gleichen Gruppe gar keine Kanten haben. Zudem gilt: , wobei und die beiden verschiedenen Gruppen sind. Bilder siehe etwa de.wikipedia.org/wiki/Satz_von_Kuratowski#Die_Graphen_K5_und_K3,3 . Mfg Michael |
 |
|
Oh das war mein Fehler, ich habe da nicht drauf geachtet. Ich habe das Bild komprimiert und es sollte nun zu sehen sein. Auch aus der Knotenmenge kann ich keinen vollständigen bilden. Oder übersehe ich hier etwas. Lg  |
|
|
|
Hallo, der Minor, der daraus entsteht, dass die Knoten 6 und 7 verschmelzen, ist ein . Ich erinnere mich selbst nicht mehr an die Bildung von Minoren und finde die deutsche wikipedia an dieser Stelle ungeeignet. Unter de.wikipedia.org/wiki/Planarer_Graph#Eigenschaften oder auch gleich unter en.wikipedia.org/wiki/Graph_minor#Example findet sich, was damit gemeint ist. Mfg Michael |
 |
|
Ahh mir war gar nicht bekannt, dass man dies tun darf. Jetzt habe ich was neues dazu gelernt und die Lösung für die Aufgabe erhalten. Vielen Dank! |
|
|
|
Michael hat das ganz richtig erkannt. Was ein Minor ist, weiß ich nicht, aber dass die Kantenfolge (3,7),(7,6) eine Unterteilung von (3,6) darstellt, ist mir klar, und Kuratowski sagt ja, dass genau, wenn ein Teilgraph eine Unterteilung eines oder eines enthält, der Graph nicht planar ist. |
1559034
1558908