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

Aus VoWi
Wechseln zu: Navigation, Suche

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

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[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]

  • siehe Informatik-Forum WS04