TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 299

From VoWi
Jump to navigation Jump to search

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.

Lösung lt. Panholzer

siehe Bsp. 202 (ist quasi Erklärung für 201)

Ganz wichtig: Buch, Satz 2.13 (Handschlaglemma):

\sum d(v)=2 \cdot |E|

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 d(v) ist für jeden Knoten 3, d.h.: \sum d(v)=3+3+3+3+3=15. Das widerspricht \sum d(v)=2\cdot|E|, denn 15 kann unmöglich 2\cdot|E| sein (2 mal irgendwas muss immer eine gerade Zahl ergeben).

Das war's.

Anmerkungen

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

  • siehe Informatik-Forum WS04