Graphentheorie: Bipartit oder Planar?

Aufrufe: 55     Aktiv: 15.06.2021 um 00:30

0



Hallo, 

ich soll hier bei diesen Graphen zeigen, ob diese bipartit oder planar sind. 

Bevor es zum Beweis kommt, habe ich einfach mal allgemein bestimmt, ob es generell bipartit oder planar ist und habe folgendes: 

 

G1 -> bipartit, planar

G2 -> bipartit, planar

G3 -> bipartit, NICHT planar

G4 -> bipartit, planar

 

Für mich sind hier irgendwie alle Graphen bipartit, denn ich kann die Knotenmenge V jeweils bei allen Graphen grundsätzlich in zwei Teilen auftteilen. Kann das so überhaupt stimmen? 

 

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
1
Bipartit: Deine Def. stimmt natürlich so nicht. Bevor Du die Aufgabe angehst, ist es notwendig, dass Du die genauen Definitionen nachschaust, in diesem Fall z.B. hier
 https://de.wikipedia.org/wiki/Bipartiter_Graph
Und die sechste dort erwähnte Eigenschaft kann helfen zu erkennen, ob bipartit oder nicht (aber nur, wenn ihr diese Eigenschaft schon in der Vorlesung hattet. Nachschauen!).
Jedenfalls sieht man damit, dass G1 und G4 nicht bipartit sind.
Falls einer bipartit ist, weist man das am besten mit der Def. nach.
Planar: Kenne ich mich nicht gut aus. G1, G2 sind planar. Weiteres hängt davon ab, wie ihr "planar" definiert habt und welche Eigenschaften zur Verfügung stehen. Nachschauen. Welche sind das bei Euch?
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 15.45K

 

Vielen Dank für die tolle Antwort! ;)

Also bei uns lautet die Definition für einen planaren Graphen wie gefolgt:

"A planar graph is a graph which can be drawn in the plane without edge crossings. A suitable drawing is callaed a (planar) embedding."

Eigenschaften wurden bei uns gar nicht erwähnt von einem planaren Graphen...

Aber es gibt das sogenannte Corollary-Beweis, mit dem kann ich zeigen, ob ein Graph planar ist oder nicht. Also mit der Formel "k <= 3e - 6" d.h. die Anzahl der Kanten müssen kleiner gleich 3*Ecken - 6 sein.

(ii) Was genau bedeutet "keinen Kreis ungerader Länge enthält" ? Was für ein Kreis?




  ─   userfaece3 14.06.2021 um 19:17

Diesen "Corollary-Beweis" kenne ich nicht, aber jedenfalls ist das so eine Eigenschaft, die ich meinte. Man muss aber darauf achten, ob das eine hinreichende oder/und notwendige Bedingung ist. Mit der Def. von "planar" sieht man, dass G1 und G2 planar sind.
"Kreis:" Ich helfe Dir gerne, gerade bei so einer reizvollen Frage (die Ausgangsfrage). Aber nicht, indem ich für Dich Begriffe anclicke und das Ergebnis mit cut-and-paste hier reinstelle. Wenn Du dazu weitere Fragen hast, gerne. Wenn Du ne englisch-sprachige Lehrveranstaltung hast, sind die Begriffe natürlich auch wieder andere.
  ─   mikn 14.06.2021 um 20:39

Okay, ich glaube jetzt weiß ich was mit Kreis/Zyklus gemeint ist, wenn die Knoten einfach sozusagen irgendwo einen Kreis bilden.

Mir ist nur nicht klar, warum eigentlich G1 nicht bipartit ist? Bei G4 ist es mir klar, ein Graph ist auch bipartit, wenn es einen Kreis mit einer geraden Anzahl an Kanten hat, was hier nicht der Fall ist.

Und bei G1 vermute ich mal, wenn ich diesen Graphen in zwei Teilmengen teilen würde, dann muss ja jeder Knoten von der Teilmenge1 mit den Knoten aus der Teilmenge2 verbunden sein und umgekehrt, und das trifft hier ja auch nicht zu. Stimmt das?
  ─   userfaece3 14.06.2021 um 23:17

Schau dir die sechste Eigenschaft nochmal genau an, so dass du sie aussagenlogisch wirklich verstehst. Ich habe bei G1 und G4 nur die benutzt.   ─   mikn 15.06.2021 um 00:30

Kommentar schreiben