Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon: Erläuterung zu

Grad eines Knotens

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Der Grad $ \,\mathrm{grad}\,(v)$ eines Knotens $ v \in V$ ist die Anzahl der Kanten von $ G$, die $ v$ als Knoten enthalten. Der Grad $ \,\mathrm{grad}\,(v)$ eines Knotens $ v$ gibt also an, wie viele Nachbarn $ v$ besitzt.

Es ist

$\displaystyle \,\mathrm{grad}\, (v) \leq \vert E(G)\vert -1 \,, $

und in jedem Graphen $ G$ gilt:

(i)
Die Anzahl der Knoten von $ G$ die einen ungeraden Grad haben ist gerade.
(ii)
Es gibt in $ G$ zwei Knoten von gleichem Grad.
(i)
Es gilt die Gleichung

$\displaystyle \sum_{v\in V(G)} \,\mathrm{grad}\, v = 2\vert E(G)\vert \,. $

Damit die linke Seite eine gerade Zahl ergibt, muss die Anzahl der Knoten mit ungeradem Grad gerade sein.
(ii)
Die Aussage wird mit dem Schubfachprinzip bewiesen. Man setzt $ n=\vert E(G)\vert$. Die Schubfächer sind mit den möglichen Graden beschriftet. Wegen $ \,\mathrm{grad}\, v \leq n -1$ gibt es dann $ n-1$ verschiedene Schubfächer. Jeder Knoten wird nun in dem Schubfach abgelegt, der seinem Grad entspricht, d.h. Knoten im gleichen Schubfächern haben den gleichen Grad. Da es zwar $ n$ viele Knoten, jedoch nur $ n-1$ viele Schubfächer gibt, ist mindestens ein Schubfach doppelt belegt.
(Aus: Vorkurs Mathematik)
[Zurück zur Aussage]
  automatisch erstellt am 26.  2. 2007