Graphentheorie für Dummies
-
Hallo,
Ich habe ziemliche Probleme bei einem vermutlich recht simplen Beispiel das mit grundlegendem Graphentheorie-Wissen zu knacken sein sollte:
Man zeige mit Hilfe eines geeigneten graphentheoretischen Modells, dass es in jeder Stadt mindestens zwei Bewohner mit der gleichen Anzahl von Nachbarn gibt.
Mir ist völlig klar, dass das der Fall sein muss, allerdings weiß ich nicht so recht, wie ich das formal beweisen soll. Wäre nett, wenn mir jemand einen Ansatz liefern könnte!
-
Ich schätze mal, Du setzt voraus, daß in einer Stadt immer mindestens 2 Leute wohnen ;).
Sagen wir mal, Du hast n Leute. Wieviele Nachbarn kann man da haben? 0...n-1. Was anderes kommt nicht in Frage, man ist schließlich nicht sein eigener Nachbar. Wenn wir mal davon ausgehen, daß Nachbarschaft symmetrisch ist, also ich nicht der Nachbar von jemandem sein kann der nicht mein Nachbar ist, dann können wir noch etwas mehr rausholen:
Möglichkeit a) Jeder hat mindestens einen Nachbarn. 0 kommt in obiger Liste also nicht vor. Also nur 1...n-1. Das sind n-1 Zahlen, aber n Leute, also haben mindestens zwei die gleiche Anzahl an Nachbarn.
Möglichkeit b) Es gibt jemanden der keinen Nachbarn hat. Dann kann aber auch niemand mehr n-1 Nachbarn haben (zu dem einen kommt man ja nicht hin). Also bleiben diesmal 0..n-2 in der Liste. Das sind aber auch nur n-1 Stück.
MfG Jester
-
Wow, das ging ja verdammt schnell und die Lösung gefällt mir richtig gut!
Danke vielmals, das hilft mir sehr!