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

Sei G ein einfacher Graph. Man zeige, dass dann die Anzahl der Knoten ungeraden Grades gerade ist.

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

Hilfreiches

Handschlaglemma

Handschlaglemma

In einem einfachen Graphen G gilt: $\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$ Die Summe der Knotengrade ist genau doppelt so groß wie die Anzahl der Kanten. $E(G)$ ist die Menge der Kanten, $V(G)$ die Menge der Knoten des Graphen $G$.

Lösung

Aus dem Handschlaglemma ist ersichtlich, dass die Summe der Knotengrade gerade sein muss, da diese als das Doppelte der Kantenanzahl dargestellt werden kann.

Außerdem kann ein Knotengrad entweder gerade sein oder nicht, die (gerade) Summe der Knotengrade setzt sich also zusammen aus der Summe der Knoten mit geradem Knotengrad und der Summe der Knoten mit ungeraden Knotengrad. Formal:

$\sum _{v\in V(G)}d(v)=\sum d(v_{g})+\sum d(v_{u})$

Daraus folgt, dass sich die Summe der ungeraden Knotengrade aus einer geraden Anzahl von Summanden zusammensetzt, da nur dann die Summe der ungeraden Knotengrade gerade ist.

Anmerkung

Dieser Schluss ist nur dann richtig, wenn man zeigen kann, dass die $\sum d(v_{g})$ gerade ist. Ansonsten würde der 2. Summand ebenfalls ungerade sein müssen, damit man auf ein gerades Ergebnis kommt. (${\overline {1}}+{\overline {1}}={\overline {0}}$)

Nun man kann sich aber überlegen, dass $\sum d(v_{g})$ gerade sein muss:

Wenn der Grad eines Knoten gerade ist, bedeutet das nichts anderes, als dass er $2\cdot n$ Nachbarn hat. Daraus folgt, dass immer nur gerade Zahlen addiert werden, wodurch auch die Summe gerade sein muss:

$\Rightarrow \sum d(v_{g})=2\cdot p$ (gerades Ergebnis)

Links

• Diskussion Informatik-Forum WS07 Beispiel 202