Mit gegebenen Gradzahlen bipartiter Graph

Aufrufe: 270     Aktiv: 03.07.2022 um 14:09
0
Hallo! 

Ich habe in einer Aufgabe die Gradzahlen jeder Ecke gegeben und soll untersuchen, ob der Graph bipartit ist. Wie untersuche ich das?

Graph: $\Omega$ = $({{\alpha_1,..., \alpha_7}}; \Omega_K)$ mit $(deg(\alpha_1),..., deg(\alpha_7))$ = $(4,4,3,3,2,2,0)$

Hat jemand Tipps?

EDIT vom 01.07.2022 um 17:20:

Aufgabe:
Diese Frage melden
gefragt

Student, Punkte: 22

 
Habe ich getan.   ─   anonymaa0df 01.07.2022 um 17:21
Kommentar schreiben
2 Antworten
0
Das ist eine schöne Aufgabe zum Ausprobieren. Man muss natürlich wissen, was bipartit bedeutet. Wie könnte der Graph aussehen? Wenn du einen Graphen hast, musst du nur noch schauen, ob er bipartit ist.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 28.29K

 
Ich habe den Graph mal konstruiert und festgestellt, dass dieser Graph nicht bipartit ist, weil er Kreise der Länge 3 enthält. Aber der Graph, den ich konstruiert habe, ist er eindeutig? Also reicht es, wenn ich einen Graphen zu den Gradzahlen zeichne, schaue ob er biparit ist und dann fertig?   ─   anonymaa0df 01.07.2022 um 11:40
Kann ich damit argumentieren, dass der Graph asymmetrisch ist und die Automorphismengruppe des Graphen trivial ist, und somit der Graph eindeutig bestimmt ist?
Somit existiert kein bipartiter Graph mit diesen Angaben.   ─   anonymaa0df 03.07.2022 um 13:58
Aber selbst, wenn die Automorphismengruppe mehr Elemente enthält, als die Identität, so wären die Kantenrelationen doch immer noch enthalten. Heißt also, dass alle Kreise von Länge 3 auch in allen Elementen der Aut.Gruppe sein müssten. Folglich sind auch alle isomorphen Graphen nicht bipartit.   ─   anonymaa0df 03.07.2022 um 14:03

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Cauchy wurde bereits informiert.
0
Dachte ich mir fast - die Aufgabe lautet anders als Du zuerst gesagt hast. Mach dir den Unterschied klar!
Kannst du also einen bipartiten Graphen finden mit diesen Angaben?
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 34.37K

 
Der Unterschied ist, dass ich untersuchen soll, ob überhaupt ein bipartiter Graph mit dieser Gradbeschreibung existiert. Somit müsste ich noch untersuchen, ob es für alle Graphen, die man aus dieser Gradinformation konstruieren kann, gilt (also ob der jeweilige Graph bipartit ist, oder nicht), richtig?   ─   anonymaa0df 03.07.2022 um 14:00

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.