 |
 |
 |
 |
 |
 |
Startseite » Forum » Graph: Planar oder Bipartit?
Graph: Planar oder Bipartit?
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Hallo! ich habe hier ein bisschen Schwierigkeiten um zu erkennen, wann ein Graph genau bipartit ist. Mir ist klar, dass wenn der Graph einen Kreis ungerader Länge (was genau bedeutet das?) enthält oder sich in zwei disjunkte Teilmengen teilen lässt, dann sind diese Graphen bipartit. Deshalb habe ich mal folgendes Ergebnis bis jetzt: ◘ NICHT bipartit (Teilt man die Mengen in zwei disjunkte Menge, dann hat nicht jeder Knoten eine Kante, die von der Teilmenge1 nach Teilmenge2 führt.) ◘ planar wegen Collorary ◘ NICHT bipartit, lässt sich nicht in zwei disjunkte Teilmengen teilen. ◘ planar wegen Collorary ◘ NICHT bipartit, zuviele Kanten. ◘ NICHT planar wegen Collorary ◘ NICHT bipartit, lässt sich nicht in zwei disjunkte Teilmengen teilen. ◘ planar wegen Collorary Kann mir hier jemand weiterhelfen?  Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, wie lautet denn das Corollar, von dem du sprichst? Übrigens: ist bipartit. Gruß ermanus |
 |
|
Ah ja, das hätte ich vielleicht noch erwähnen sollen... Corollar: Ein zusammenhängender und planarer Graph hat mindestens 3 Ecken und die Kanten sind höchstens so groß wie die Anzahl der Kanten . Habe noch ein Bild drangehängt, wo noch ein bisschen mehr über das Corollar steht, also so wie es unser Professor definiert hat. Fragen: Warum ist eigentlich bipartit? Weil es sich in zwei disjunkte Teilmengen teilen lässt, kann das sein? Und was bedeutet eigentlich, dass ein Graph einen Kreis mit einer ungeraden Länge enthält? Dass die Knoten quasi sowas wie einen Kreis bilden, mit einer ungeraden Anzahl an Knoten?  |
|
|
|
Mir scheint, dass das Corollar nur eine notwendige Bedingung für Planarität liefert, d.h. dass man aus der Erfülltheit der angegebenen Ungleichungen nicht auf Planarität schließen kann, wohl aber aus der Nichterfülltheit auf Nichtplanarität. Zu bipartit siehe angehängtes Bild:  |
|
|
|
Das heißt, mit Corollar kann ich nicht wirklich beurteilen, ob ein Graph planar ist? Wie könnte ich das sonst noch am Besten zeigen oder beweisen? Aso, die roten Knoten bilden sozusagen einen Kreis ungerader Länge? |
|
|
|
Kennst du den Satz von Kuratowski? |
|
|
|
"Aso, die roten Knoten bilden sozusagen einen Kreis ungerader Länge? " Nein. Die roten Knoten bilden die eine Menge, die schwarzen die andere, so dass wir eine Zerlegung der Knoten in zwei disjunkte Teilmengen haben und Kanten nie zwischen Knoten derselben Menge verlaufen. Ein Kreis ist ein geschlossener Kantenzug. Seine Länge ist die Anzahl der Kanten = Anzahl der Knoten. |
|
|
|
Kennst du den Satz von Kuratowski? Ja, also es wurde mal kurz erwähnt in der Vorlesung, hab' es jedoch irgendwie nicht ganz verstanden. Also man schaut hier sozusagen, ob ein Graph eine Teilmenge von einem anderen Graphen ist bzw. ein Graph aus einem anderen Graphen entsteht, richtig? Nein. Die roten Knoten... Ah, dann lassen sich also doch zwei disjunkte Teilmenge bilden. Danke für die ausführliche Erklärung! |
|
|
|
Zu . wäre der Graph nicht planar, müsste er nach Kuratowski einen oder einen oder eine Unterteilung derselben als Teilgraphen enthalten. Das ist aber offenbar nicht der Fall. |
|
|
|
Ich habe es nun nochmals probiert und meinen verbesserten Ansatz hier als Bild angefügt. Möchtest Du vielleicht kurz einen Blick darauf werfen? Würde mich sehr freuen.   |
|
|
|
Melde mich in 2 Stunden zu deinen neuen ergebnissen ... |
|
|
|
Passt gut, nur kein Stress... ;-) |
|
|
|
Bei den Graphen, wo du den Satz von Kuratowski benutzen möchtest, um Planarität zu begründen, kannst du nicht sagen "IST weder ein , noch ein , noch eine Unterteilung ...", sondern du meinst sicher "ENTHÄLT weder ein ..." Bei findest du in der Tat einen -Teilgraphen, nach meinem Geschmack bietet sich aber eher an: "wenn man einen Knoten löscht, erhält man einen . Nach Kuratowski ist also nicht planar." ist nicht bipartit; denn er enthält als geschlossene Kantenzüge Dreiecke, also "Kreise" der Länge 3 (ungerade). |
|
|
|
Wow, danke für das super tolle Feedback! Finde es zwar nicht schwer die Aufgabe, aber ich merke, dass man da echt genau sein muss, um zu erkennen, ob planar oder bipartit. Ich werde es dann später korrigieren und wenn Du möchtest, dann kannst Du dann nachher nochmals einen Blick drauf werfen. Aber nur wenn Du natürlich Lust und Laune hast. ;-) |
 |
|
So, hier habe ich nochmals die verbesserte Version, denke jetzt müsste es passen außer die ganzen Satzformulierungen sind eventuell etwas dünn gehalten... Sonst ist die Frage für mich hier abgeschlossen. Danke für die super tolle Hilfe hier, hab' wieder mal was dazu gelernt! ;-)   |
|
|
|
Ja. So ist das alles prima! Gruß ermanus |
1538285
1538171