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

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 16:44, 7 March 2019 by Gittenborg (talk | contribs) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 301 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 301 und überschrieb dabei eine Weiterleitung: versch…)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Man zeige dass es in jedem Graphen G mit n >= 2 Knoten wenigstens 2 Knoten mit gleichem Knotengrad gibt.

Lösung[edit]

  • Lösung durch einen indirekten Beweis. Wir führen die Annahme dass es einen Graph G gibt, der keine 2 Knoten gleichen Grades hat, zu einem Widerspruch.
  • Es sei also G ein Graph, der keine 2 Knoten gleichen Grades hat. Daraus folgt also, dass der Grad jedes Knotens verschieden sein muss.
  • Es sei weiters n die Anzahl der Knoten in G. Man kann sich überlegen dass der Grad für jeden Knoten in G zwischen 0 (d.h. der Knoten ist mit keinem anderen Knoten verbunden) und n-1 liegen muss (d.h. der Knoten ist mit allen anderen Knoten verbunden).
  • Da nun also genau die Knotengrade von 0 bis n-1 in Frage kommen und gleichzeitig jeder Knoten einen verschiedenen Grad haben muss (lt. obiger Forderung), heißt das also dass jeder Knotengrad von 0 bis n-1 genau einmal in G vorkommen muss, ansonsten würde sich das natürlich nicht ausgehen (kann man in diesem Sinn auch als bijektive Funktion interpretieren).
  • Es folgt dass es in G einen Knoten gibt der den Grad n-1 hat.
  • Der Knoten mit dem Grad n-1 verbindet alle anderen Knoten. Daraus folgt dass es keinen Knoten mit dem Grad 0 geben kann.
  • Wir fordern aber dass jeder Knotengrad genau einmal vorkommt, auch ein Knoten mit dem Grad 0. Das führt somit zu einem Widerspruch.
  • Es kann daher keinen Graphen geben, der lauter unterschiedliche Knotengrade hat. Daraus folgt, dass jeder Graph G zumindest 2 Knoten gleichen Grades besitzen muss, was zu zeigen war.

Der formale Nachweis kann ähnlich der "mündlichen" Argumentation analog geführt werden.

--Emkey08 00:55, 7. Dez 2007 (CET)

Diskussion[edit]

So erklärt von Tutor (GITTENBERGER) in Gruppe R

analog: Pidgeon-Hole-Prinzip

  • Einfacher Graph
  • 0 <= d(x) <= n-1
  • Menge möglicher Knotengrade: M={0,1,...,n-1}
  • M widerspricht sich selbst, weil einerseits ein Knoten mit 0 Verbindungen existiert, andererseits einer mit n-1 Verbindungen (dh 1 Verbindung zu jedem anderen Knoten)
  • -> M muss entweder sein {0,...,n-2} oder {1,...,n-1}
  • |M| < n -> mindestens zwei Knoten müssen den gleichen Knotengrad haben

braucht man lt. Tutor nur erklären (argumentieren), nicht "streng formal" anschreiben

Links[edit]

Diskussion Informatik-Forum WS05 Beispiel 549 alte Nummer, neu 203