TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 303

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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

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\leq d^{+}(x)\leq 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})\neq d^{+}(x_{m}),x_{n}\neq 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\leq d^{+}(x)\leq 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}\neq 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.