Graphen

Neue Frage »

gast Auf diesen Beitrag antworten »
Graphen
Gibt es einen Graph, dessen Ecken alle einen unterschiedlichen Grad haben? Wie kann ich das begründen?
cmenke Auf diesen Beitrag antworten »

Hallo Gast,

Deine Vorgaben sind ein bisschen knapp.
Du hast nichts davon gesagt, dass Schlingen verboten sind, aber ich gehe mal stark davon aus (da die Sache sonst recht einfach wäre).
Für einfache Graphen ohne Schlingen weiß ich die Antwort nicht so aus dem Stehgreif, glaube aber nicht, dass es geht.

Solltest du zu "ja" tendieren, so brauchst du einfach nur ein Beispiel zu liefern.
Bei "nein" musst du einen richtigen Beweis liefern und das stinkt gewaltig nach Widerspruchsbeweis.
Eine Sache, die mir spontan dazu einfällt ist, dass jede neue Kante den Grad von zwei Ecken erhöht. Damit ist die Summe der Grade auch immer gerade (nämlich Anzahl der Kanten * 2). Außerdem ist der Grad einer Ecke höchstens so hoch wie Anzahl der Ecken - 1 (mehrere Kanten zwischen zwei Ecken werden jawohl auch verboten sein).

Vielleicht kannst du damit was basteln?
Tobias Auf diesen Beitrag antworten »

Hat ein Graph Schlingen, so existiert so ein Graph (an jeder Ecke eine unterschiedliche Anzahl Schlingen).

Sind Mehrfachkanten erlaubt, so existiert ebenfalls ein solcher Graph (-> Drei Knoten und je zwei Knoten sind durch eine Kante, je zwei durch zwei und je zwei durch drei Kanten verbunden.)

Ein Graph ist schlicht, wenn er weder Schlingen noch Mehrfachkanten besitzt. Ein schlichter Graph mit mehr als einer Ecke erfüllt die Bedinung nicht. Als Beweis eignet sich das Schubfachprinzip über den Grad in Zusammenhang mit dem Handschlaglemma.
eule Auf diesen Beitrag antworten »

Die Anwort ist nein. Du hast n Ecken und für die möglichen Eckengrade gilt dass diese zwischen 0 und n-1 liegen. ok? Das sind aber genau n mögliche Eckengrade.

Angenommen es gäbe eine Graphen dessen n Ecken alle unterschiedlichen Grad haben dann
müßten die n verschiedenen Eckengrade den n verschiedenen Ecken zugewiesen werden.
Dann gäbe es in dem Graphen gleichzeitig eine Ecke mit Grad n-1 und eine mit Grad 0 Wid.
Neue Frage »
Antworten »



Verwandte Themen

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