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

Gegeben sei der ungerichtete Graph $G=\langle V,E\rangle$ mit $V=\{a,b,c,d,e\}$ und $E=\{ab,ac,ae,bc,bd,ce\}$. Man veranschauliche G graphisch, bestimme seine Adjazenzmatrix sowie alle Knotengrade und zeige, dass die Anzahl der Knoten, die einen ungeraden Knotengrad besitzen, gerade ist. Gilt diese Aussage für jeden ungerichteten Graphen?

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
}}

Lösung

graphische Veranschaulichung (von mnemetz)

Adjazenzmatrix (von ska83)

(berechnet von ska83, in amsmath übertragen von mnmetz)

$A_{G}={\begin{pmatrix}&a&b&c&d&e\\a&0&1&1&0&1\\b&1&0&1&1&0\\c&1&1&0&0&1\\d&0&1&0&0&0\\e&1&0&1&0&0\end{pmatrix}}$

Knotengrade (von ska83)

d(a) = 3, d(b)= 3, d(c)=3, d(d)=1, d(e)=2

Anzahl der Knoten mit ungeradem Knotengrad (von ska83)

Die Aussage gilt nur dann, wenn es eine gerade Anzahl an ungeraden Knotengraden gibt. Summe d = 2 * |E|

Anzahl der Knoten mit ungeradem Knotengrad (von hanzzz)

Ja die Aussage gilt in jedem ungerichtetem Graphen. (jedenfalls konnte ich kein Gegenbsp. finden ;-) )

Die Summe aller Knotengrade ist ja 2 * |E(G)| (Handschlaglemma) also muss die Summe aller Knotengrade gerade sein.

Die Summe aller Knotengrade muss die Summe aller Knotengrade mit ungeradem Knotengrad + die Summe aller Knotengrade mit geradem Knotengrad sein.

Schauen wir uns mal die Summe aller Knotengrade mit geradem Knotengrad an: Die Summe einer geraden Zahl ist immer gerade. Vgl.: 2 + 4 = 6, 2 + 4 + 6 = 12

Der erste Teil ist also IMMER erfüllt, d.h. die Summe aller Knotengrade mit ungeradem Knotengrad muss auch gerade sein.

Das schauen wir uns mal näher an: Die Summe von ungeraden Zahlen ist nur dann gerade, wenn die Anzahl der Summanden gerade ist. Ist die Anzahl der Summanden ungerade ist die Summe auch ungerade. Dann wäre die Gleichung nicht mehr erfüllt. => Die Anzahl an Knoten mit ungeradem Knotengrad muss gerade sein! Vgl.: 3 + 7 = 10 (Summe von 2 ungerade Zahlen (=gerade Anzahl an Summanden) ergibt immer eine gerade Zahl) 3 + 7 + 5 = 15 (Summe von 3 ungerade Zahlen (=ungerade Anzahl an Summanden) ergibt immer eine ungerade Zahl)

Für diese Ausführung gibts natürlich keine Gewähr. (das ganze stellt man am besten noch mit einer "Gleichung" dar (siehe Weblink) - aber dafür bin ich jetzt zu faul :-P )

Ergänzung von mnemetz

Behauptung Es sei G = {V, E} ein beliebiger ungerichteter Graph. Dann ist die Anzahl der Knoten von G, die einen ungeraden Knotengrad haben, gerade.

Beweis Wir bezeichnen für $v\in V$ mit B(v) die Menge der von v ausgehenden Kanten. Da jede Kante von genau zwei Knoten ausgeht, gilt:

$\sum _{v\in V}|B(v)|=2*|E|$

Es sei nun U die Menge der Knoten von G mit ungeradem Knotengrad. Dann ist $2*|E|=\sum _{v\in V}|B(v)|=\sum _{v\in U}|B(v)|+\sum _{v\in V\backslash U}|B(v)|=$

Umformen liefert: $\sum _{v\in U}|B(v)|=2*|E|-\sum _{v\in V\backslash U}|B(v)|$

Nun ist nach Wahl von U |B(v)| fuer alle $v\in U$ ungerade und fuer alle $v\in V\backslash U$ gerade. Damit ist auch die Summe ueber alle |B(v)| mit $v\in V\backslash U$ gerade. Also steht auf der rechten Seite der obigen Gleichung eine gerade Zahl, etwa

$\sum _{v\in U}|B(v)|=2*n$

für ein passendes $n\in \mathbb {N}$.

Da die Summanden der Summe auf der linken Seite aber alle ungerade sind, muss ihre Anzahl gerade sein. Die Anzahl der Summanden ist aber gerade |U| = die Anzahl der Knoten von G mit ungeradem Grad. Damit ist die Behauptung gezeigt.

Anzahl der Knoten mit ungeradem Knotengrad (von Soymilk-drinker)

Meine Lösung ist ähnlich der vollständigen Induktion (wenn's nicht sogar ist). Ich suche mir einen Grundzustand der gültig ist und sehe nach ob ich durch Erweiterung auf alle anderen Zustände kommen kann.

Als Grundzustand wähle ich einfach einen Graphen ohne Kanten. Daher haben alle Knoten den Grad 0, und die Anzahl der Knoten mit ungeradem Grad ist somit 0. 0 ist eine gerade Zahl, also stimmt die Behauptung.

Jetzt erweitere ich den Graphen um eine Kante, dabei gibt es 3 Möglichkeiten:

1.) Eine neue Kante wird zwischen 2 Knoten eingefügt die jeweils einen geraden Grad haben. Dadurch erhöht sich der Grad jedes Knoten um 1 und aus gerade wird ungerade. Jetzt haben wir also 2 weitere Knoten mit ungeradem Grad.

2.) Eine neue Kante wird zwischen 2 Knoten eingefügt die jeweils einen ungeraden Grad haben. Dadurch erhöht sich der Grad jedes Knoten um 1 und aus ungerade wird gerade. Jetzt haben wir also 2 weniger Knoten mit ungeradem Grad.

3.) Eine neue Kante wird zwischen 2 Knoten eingefügt wobei ein Knoten einen ungeraden und die andere einen geraden Grad hat. Damit erhöht sich der Grade jedes Knoten um 1, aus dem geraden wird ein ungerader Grad und aus dem ungeraden ein gerader. Damit haben wir einen Knoten mit ungeradem Grad mehr, aber gleichzeitig auch wieder einen weniger (hebt sich also auf)

Ich hab also einen gültigen Anfangszustand (Graph ohne Kanten) und durch hinzufügen von Kanten (3 Fälle) bleibt die Behauptung gültig. Damit ist bewiesen dass die Aussage stimmt.

Hinweis: 2. und 3. können erst auftreten wenn der Graph mindestens eine Kante hat, ansonsten gibts ja nur gerade Grade. Nur falls der Prof nachfragt.

Anmerkung: Schöner Beweis, aber in der Angabe ist nur von ungerichteten Graphen die Rede. Also gibts noch 1 weiteren Fall zu berücksichtigen, nämlich Schlingen. Die erhöhen den Knotengrad von genau einem Knoten um eins (unintuitiv ich weiß). Also gilt die Aussage nicht in jedem ungerichteten Graphen. (Siehe Adjazenzmatrix des Graphen mit Schlinge im Buch als Bsp für einen Graphen der die Aussage nicht erfüllt) (Andererseits steht im Buch auch, dass bei der Gradberechnung Schlingen doppelt gezählt werden müssen, was für mich im Widerspruch zur im Buch dargestellten Adjazenzmatrix steht, die einen ungeraden Knoten darstellt...)

Lösung mit Hnadschlaglemma (wie mnemetz)

Wir setzten einfach in des Hnadschlaglemma ein $2*|E|=\sum _{v\in V}|d(v)|=\sum |d(a)+d(b)+d(c)+d(d)|$ Dann einsetzten E(G) = 5 $2*|E(G)|=3+3+3+1=>10=10$

Webressourcen

• f.thread:21552 (von ska83 gepostet)
• https://web.archive.org/web/20180817161420/https://matheplanet.com/default3.html?call=viewtopic.php%3ftopic=626&forum=3