TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 309
Man zeige mit Hilfe eines geeigneten graphentheoretischen Modells, daß es in jeder Stadt mindestens zwei Bewohner mit der gleichen Anzahl von Nachbarn gibt.
{{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ösungsvorschlag:[Bearbeiten | Quelltext bearbeiten]
Lösungsmodell wäre ein Binärbaum, da in der Minimalkonfiguration (Wurzel und 2 Blätter) bereits die Bedingung erfüllt ist, ebenso gilt das für jeden Randknoten oder 2 beliebige Knoten in der Mitte des Baums. Leider eine falsche Überlegung auf Grund der nicht sehr präzisen Angaben.
Lt. Urbanek soll man zeigen, daß jeder Graph mindestens 2 Knoten (Nachbarn) vom selben Knotengrad besitzt.
Es existiert ein a,b enthalten in der Knotenmenge V(G) wobei a ungleich b ist.
0 d(a) < n und 0 d(b) < n
wobei n die Knotenanzahl und der Grad n-1 ist. Da 0 kein Nachbar von n-1 ist, müssen mindestens 2 Knotengrade gleich sein.
Hapi
-- Etwas anders erkärt: Die möglichen Knotengrade sind 0, ..., n-1 bei n Knoten (ein Knoten kann maximal mit seinen n-1 Nachbarn verbunden sein im schlichten Graphen). n-1 und 0 schließen sich Gegenseitig aus: Ist ein Knoten mit n-1 (allen) verbunden, so ist keiner mit 0 verbunden. Es gibt also für n Knoten nur n-1 Knotengrade (0, ..., n-2 oder 1, ..., n-1) und laut Taubenschlaglemma haben dann 2 Knoten denselben Knotengrad.
Ähnliche Beispiele[Bearbeiten | Quelltext bearbeiten]
https://vowi.fsinf.at/wiki/TU_Wien:Mathematik_1_UE_(diverse)/%C3%9Cbungen_WS06/Beispiel_195