Gradfolge

[Jeff_Mills]

Man zeichne alle Graphen mit der Gradfolge(3,3,2,2,2)
Was genau wir da von mir verlangt?


Beschreibt die Gradfolge(7,5,4,4,3,2,1,1,1) einen Graphen wir funktioniert bei diesem beispiel der Beweis

ich freue mich über alle Hinweise
danke

[Georg Kraml]

"Man zeichne alle Graphen mit der Gradfolge(3,3,2,2,2)
Was genau wir da von mir verlangt?"

Du sollst alle Graphen aufzeichnen, die fünf Knoten haben und bei denen diese fünf Knoten Knotengrade von 3, 3, 2, 2 bzw. 2 aufweisen. Tipp: es gibt mindestens 6 zusammenhängende solche Graphen und ausserdem mindestens einen nicht zusammenhängenden.

"Beschreibt die Gradfolge(7,5,4,4,3,2,1,1,1) einen Graphen"

Nein.

"wir funktioniert bei diesem beispiel der Beweis"

Eine Gradfolge s = a_1, a_2, ... a_n ist genau dann graphisch (d. h. ist genau dann Gradfolge mindestens eines Graphen), wenn die Gradfolge s_1 = a_2-1, a_3-1, ... a_{k+1}-1, a_{k+2}, ... a_n mit k = a_1 ebenfalls graphisch ist. (s_1 ergibt sich hier aus s, in dem man a_1 entfernt und von den ersten s_1 übriggebliebenen Elementen jeweils 1 abzieht.)

Wir probieren's aus:

s = 7 5 4 4 3 2 1 1 1
s_1 = 4 3 3 2 1 0 0 1
s_2 = 2 2 1 0 0 0 1
s_3 = 1 0 0 0 0 1
s_4 = ?

Bei s_4 haben wir ein Problem, da ein Knotengrad natürlich nicht kleiner als 0 sein kann. []

[Jeff_Mills]

Danke für die schnelle hilfe

kennst du dich auch mit differenzenglg aus ?
siehe den anderen post von mir

ciao

[Jeff_Mills]

aber ist s_3 nicht bereits graphisch?

2 vebundene Knoten un 4 isolierte?
daraus folgt s ist auch graphisch oder?


<5,3,3,2,2,1>

s_1= 2,2,1,1,0
s_2= 1,0,1,0
s_3= keine negativen grad => nicht graphisch?

aber dieser graph ist ganz sicher graphisch
oder ich verstehe graphisch nicht

danke

[seg2]

Ad Beispiel: "Man zeichne alle Graphen mit der Gradfolge(3,3,2,2,2)".

Sind dabei ausschließlich SCHLICHTE Graphen, also jene ohne Mehrfachkanten und Schleifen, gemeint?

@Georg Kraml:
Also sind zusammenhängende UND nicht zusammenhängende Graphen gefragt?

--> Kann jemand sagen, der/die weiß, was bei diesem Beispiel genau verlangt wird?


Woher ist dieses Beweisverfahren? Ist es das, was Prof. Kaiser verlangt?

lg und Danke im Voraus!

[orpheus]

Die Frage

"Beschreibt die Gradfolge(7,5,4,4,3,2,1,1,1) einen Graphen?"

würde ich mit "ja" beantworten (siehe Anhang). Kann mir vielleicht jemand einen Literaturhinweis zu dem Verfahren (Bestimmung des Graphen aus der Gradfolge) geben? Danke.