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

Aus VoWi
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

Handschlaglemma
Handschlaglemma[Bearbeiten, Wikipedia, 2.13 Satz]

In einem einfachen Graphen G gilt: Die Summe der Knotengrade ist genau doppelt so groß wie die Anzahl der Kanten. ist die Menge der Kanten, die Menge der Knoten des Graphen .

Lösung[Bearbeiten | Quelltext bearbeiten]

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:

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[Bearbeiten | Quelltext bearbeiten]

Dieser Schluss ist nur dann richtig, wenn man zeigen kann, dass die gerade ist. Ansonsten würde der 2. Summand ebenfalls ungerade sein müssen, damit man auf ein gerades Ergebnis kommt. ()

Nun man kann sich aber überlegen, dass gerade sein muss:

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

(gerades Ergebnis)

Links[Bearbeiten | Quelltext bearbeiten]

  • Diskussion Informatik-Forum WS07 Beispiel 202