TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 304
Man zeige mit Hilfe eines graphentheoretischen Modells, daß es unmöglich ist, daß bei 5 Personen, die jeweils drei anderen eine Karte senden, alle genau von jenen Karten erhalten, denen sie auch eine geschickt haben.
{{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 lt. Panholzer[Bearbeiten | Quelltext bearbeiten]
siehe Bsp. 202 (ist quasi Erklärung für 201)
Ganz wichtig: Buch, Satz 2.13 (Handschlaglemma):
In einem schlichten, ungerichteten Graph ist die Summe aller Knotengrade gleich der doppelten Kantenmenge.
Nehmen wir an, jeder der 5 Knoten ist mit je 3 anderen Knoten genau durch eine, ungerichtete Kante verbunden. Der Knotengrad ist für jeden Knoten 3, d.h.: . Das widerspricht , denn 15 kann unmöglich sein (2 mal irgendwas muss immer eine gerade Zahl ergeben).
Das war's.
Anmerkungen[Bearbeiten | Quelltext bearbeiten]
Hallo Leute, ganz verstehe ich die Antwort/Begrünung in dem Link nicht, weil laut Angabe geht ja nur hervor, dass der Weggrad 3 (von jedem Knoten gehen 3 Karten/Kanten weg ist. Rein theoretisch könnten ja die vier anderen Knoten Karten an einen Knoten schicken - dh dann hätte mal einen Knotengrad von vier (hat alle vier Knoten als Nachbar) Hab mir das mit insg. 5 Knoten aufgezeichnet - es ist so, dass der letzte Knoten nur mehr zwei Karten erhält (wenn von jedem Knoten 3 Kanten ausgehen). Es dürfte eher von der Gesamtanzahl der Knoten abhängen, dh. bei 4 Knoten funktioniert es, bei 6 Knoten funktioniert es....
Links[Bearbeiten | Quelltext bearbeiten]
- siehe Informatik-Forum WS04