(Twitter)
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?
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
Link
geantwortet
mikn
Lehrer/Professor, Punkte: 38.93K
Lehrer/Professor, Punkte: 38.93K
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
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
Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden.
Mikn wurde bereits informiert.
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