TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 298

Aus VoWi
Wechseln zu: Navigation, Suche

Man zeige, daß es in einem schlichten, gerichteten Graphen G = (V,E) immer zwei Knoten x,y \in V, x \ne y, gibt mit gleichem Weggrad d^+(x) = d^+(y), wenn es keinen Knoten x \in V(G) mit Weggrad d^+(x)= 0 gibt.

Hallo Leute,

habe die Frage in einem anderen Forum gepostet, kann aber nicht wirklich was mit der Antwort anfangen - vielleicht habt Ihr noch Ideen dazu:

https://web.archive.org/web/20180817161701/https://www.matheraum.de/read?t=330726

Erklärung by death angel:

In einem schlichten gerichteten Graphen mit n Knoten ist der größtmögliche Weggrad n-1. Angenommen man hat einen schlichten gerichteten Graphen mit n Knoten, die alle verschiedene Weggrade haben, wobei kein Knoten den Weggrad 0 hat. Dann muss ein Knoten einen Weggrad von n oder größer als n haben (sonst kommt man nicht auf n unterschiedliche Weggrade). Dies ist ein Widerspruch zur Annahme (der größtmögliche Weggrad ist ja n-1). Somit müssen mindestens zwei Knoten denselben Weggrad haben.

Versuch einer Zusammenfassung von Lumpi[Bearbeiten]

Zuerst eine Aufschlüsselung der Angabe-Vokabeln:

schlichter Graph: Es gibt keine Schlingen (Kante von Knoten die auf den selben Knoten Zeigt) und Mehrfachkanten (mehrere Kanten die selben Start- und Endknoten bzw. die selbe Richtung haben).

gerichteter Graph: Jede Kante hat eine Richtung (von Anfangsknoten zu Endknoten - mit Pfeilen dargestellt!)

Weggrad: Anzahl der Kanten die von einem Knoten weg zu einen anderen Knoten zeigen (Darstellung: die Pfeilspitze zeigt weg vom Knoten) Zeichen: d^+(x) wobei x der Knoten ist.

Weiters ist gegeben, dass es keinen Knoten x mit Weggrad d^+(x)=0 geben soll, also keinen Knoten mit Weggrad 0.

Daraus ergibt sich:

1.) Schlichter Graph: Ein Knoten darf höchstens eine Kante zu jedem anderen Knoten haben und keine Kante auf sich selbst. d.h. Bei n Knoten im Graph ist der maximale Weggrad d^+(x)=n-1

2.) Es gibt keinen Knoten mit Weggrad d^+(x)=0: Bei n Knoten im Graph ist der minimale Weggrad d^+(x)=1

Anmerkung von Knusper: Hier wird das Schubfachprinzip angewendet! 
                       Bei n Elementen (Knoten) und k Schubfächer(verschiedene Knotengrade), gilt n > k.

Also:

Der Weggrad jedes Knotens muss im Bereich von 1 bis n-1 liegen 1\le d^+(x)\le n-1.

Nun zeigen wir durch Widerspruch, dass in Graphen mit diesen Voraussetzungen mindestens zwei Knoten den selben Weggrad haben müssen:

Wir haben n Knoten  x_1,...,x_n. Es soll für jeden Knoten unterschiedliche Weggrade geben. d.h. d^+(x_n)\ne d^+(x_m), x_n\ne x_m

Also setzen wir alle möglichen Weggradwerte für die Knoten ein:

d^+(x_1)=1

d^+(x_2)=2

.

.

.

d^+(x_{(n-1)})=(n-1)

d^+(x_n)=n ? ... Widerspruch nach 1\le d^+(x)\le n-1 -> Unmöglich: d^+(x_n) muss einen der vorangegangenen Werte haben!

Es gibt leider wie vorhin bemerkt, n Knoten aber nur 1 bis n-1, also n-1 mögliche Weggrade, die ein beliebiger Knoten haben darf! d.h.: Es gibt mindestens ein d^+(x_n) für das es keinen neuen Weggrad-Wert gibt, es muss den Weggrad eines anderen x_m annehemen -> d^+(x_n)=d^+(x_m), x_n\ne x_m.

Es ist also nicht möglich in Graphen mit diesen Eigenschaften jedem Knoten einen eigenen Weggrad zuzuweisen. Es gibt zu wenig mögliche Weggrad-Werte.