Graphentheorie

Neue Frage »

Auf diesen Beitrag antworten »
Graphentheorie
Meine Frage:
Gegeben sei der folgende Graph G mit der Knotenmenge

V = {a, b, c, d, e, f, g, h}

und der Kantenmenge:

E = {{a, f}, {a, d}, {b, f}, {b, d}, {b, e}, {b, c}, {c, f}, {c, e}, {c, g}, {c, h}, {d, e}, {d, g}, {g, h}}

a) Zeichnen Sie den Graphen G.
b) Geben Sie die Nachbarschaft N(b) und N(g) an.
c) Geben Sie die Gradsequenz von G an.

Meine Ideen:
meine erste Frage bezieht sich auf Aufgabe b)

Nachbarschaft wurde folgendermaßen definiert: N(x)={y Element von V| {x,y}Element von E}

dann wären also die Nachbarschaft von N(b)= {b,f};{b,d};{b,e} und {b,c}?
oder muss ich da noch etwas bestimmtes beachten?

Richtig Probleme macht mir aber Aufgabe c)... den Grad eines Knoten ist die Anzahl seiner Nachbarn, dass ist soweit klar. Jedoch hab ich keine Ahnung wie ich an die Gradsequenz eines Graphen rann zu gehen habe
Cel Auf diesen Beitrag antworten »

b) hast du dir eigentlich richtig gedacht. Aber guck dir noch mal die Definition an, da steht nichts von 2er-Tupeln bzw. Mengen. Du gibst Mengen an, so darf es nicht sein. Zähle einfach die Nachbar auf. N(b) wäre also



Für die c) müsst du alle Knotengrade bestimmen und aufsteigend in ein 8-er Tupel schreiben.
Auf diesen Beitrag antworten »

ah alles klar ^^
danke danke
jetzt hab ich nur noch ne kleine frage um Missverständnisse zu vermeiden smile
N(g) wäre also

Cel Auf diesen Beitrag antworten »

Nein, nach deiner Definition stimmt das nicht. Das g muss in der Kantenmenge links stehen, bei d zum Beispiel steht es rechts. {d,g} befindet sich in E, aber {g,d} eben nicht. Müsste es aber, damit d in N(g) sein würde.
Auf diesen Beitrag antworten »

ah alles klar
also ist N(g)={h}
Pavel Auf diesen Beitrag antworten »

Zitat:
Original von Cel
Nein, nach deiner Definition stimmt das nicht. Das g muss in der Kantenmenge links stehen, bei d zum Beispiel steht es rechts. {d,g} befindet sich in E, aber {g,d} eben nicht. Müsste es aber, damit d in N(g) sein würde.

Also nach meinem Wissen ist gerade das besondere an Mengen, dass die Reihenfolge ihrer Elemente unerheblich ist.
Soll heißen, es ist gerade {d,g}={g,d}.
Sprächen wir über Tupel, so wäre die Anordnung von Bedeutung, bei Mengen aber nicht.
 
 
Cel Auf diesen Beitrag antworten »

Pavel hat vollkommen recht. Ich habe auch an Tupel, also an gerichtete Graphen gedacht. Deswegen stimmt deine ursprüngliche Nachbarschaft von g, Mö.
Auf diesen Beitrag antworten »

ok das mit der Nachbarschaft hab ich jetzt soweit verstanden
wie schaut das jetzt aber mit Aufgabe c) aus
ich habe jetzt, hoffentlich richtig, für alle Knoten die Grade bestimmt.

zum Beispiel für N(b)={f,d,e,c} ist der Grad deg(b)=4
und für N(g)={c,d,h} ist der Grad deg(g)=3

um jetzt also die Gradsequenz raus zu bekommen muss ich alle Knotengrade aufsteigend in ein Tupel schreiben....
also vom kleinsten zum größten Grad?
und dann bin ich fertig?
Cel Auf diesen Beitrag antworten »

Vollkommen richtig.
Auf diesen Beitrag antworten »

ich muss jetzt aber nochmal speziell nachfragen
ich hätte dann eine Gradsequenz die folgender Maßen ausschauen würde

(2,2,3,3,3,4,4,5) ich hab aber in manch anderen Foren Gradsequenzen gefunden, welche vom größten zum kleinsten Glied gehen
also (5,4,4,3,3,3,2,2)
Cel Auf diesen Beitrag antworten »

Das mag durchaus sein, ich habe Wiki zu Rate gezogen. Scheint dann wohl beides möglich zu sein (siehe z. B. hier), wie das bei dir aussieht, kann ich natürlich nicht sagen.
Auf diesen Beitrag antworten »

ok ich lass das erstmal beides stehen und frag morgen nochmal inner uni ^^
dann bedank ich mich an dieser stelle für die super Hilfe Big Laugh
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »