Grad (Graphentheorie)

Ein ungerichteter Graph. Die Knoten sind mit ihrem Grad beschriftet.

In einem ungerichteten Graphen ${\displaystyle G}$ ist für jeden Knoten ${\displaystyle v}$ der Grad ${\displaystyle d_{G}(v)}$ definiert als die Anzahl aller Kanten von ${\displaystyle G}$, die an ${\displaystyle v}$ angrenzen. Sofern vorhanden werden Schlingen dabei doppelt gezählt.

Statt ${\displaystyle d_{G}(v)}$ wird oft auch die Notation ${\displaystyle \deg _{G}(v)}$ verwendet. Der Index ${\displaystyle G}$ kann weggelassen werden, falls klar ist, um welchen Graphen es sich handelt.

Den kleinsten Grad eines Knotens in ${\displaystyle G}$ nennt man den Minimalgrad von ${\displaystyle G}$ und bezeichnet diesen mit ${\displaystyle \delta (G)}$, den größten Grad eines Knotens in ${\displaystyle G}$ nennt man den Maximalgrad von ${\displaystyle G}$, dieser wird meist mit ${\displaystyle \Delta (G)}$ bezeichnet. Der Durchschnitt aller Knotengrade von ${\displaystyle G}$ wird Durchschnittsgrad genannt und mit ${\displaystyle d(G)}$ bezeichnet.

Ein gerichteter Graph mit beschrifteten Knoten: (Eingangsgrad, Ausgangsgrad)

In einem gerichteten Graphen ${\displaystyle G}$ wird unterschieden, ob eine Kante an einem Knoten beginnt oder endet. Mit ${\displaystyle d_{G}^{-}(v)}$ bezeichnet man den Eingangsgrad des Knotens ${\displaystyle v}$ in einem gerichteten Graphen ${\displaystyle G}$ und mit ${\displaystyle d_{G}^{+}(v)}$ dessen Ausgangsgrad.

Dabei ist ${\displaystyle d_{G}^{-}(v)}$ die Anzahl aller Kanten, die in ${\displaystyle v}$ enden und ${\displaystyle d_{G}^{+}(v)}$ die Anzahl aller Kanten, die in ${\displaystyle v}$ starten.

Einen Knoten ohne Eingangskanten (${\displaystyle d_{G}^{-}(v)=0}$) nennt man Quelle, einen Knoten ohne Ausgangskanten (${\displaystyle d_{G}^{+}(v)=0}$) nennt man Senke.

Zusammenhängende planare Graphen mit ${\displaystyle |V|}$ Knoten, ${\displaystyle |E|}$ Kanten und ${\displaystyle |F|}$ Flächen erfüllen die Ungleichung ${\displaystyle 2\cdot |E|\geq 3\cdot |F|}$, weil jede Fläche benachbart zu mindestens drei Kanten und jede Kante genau zwei Flächen begrenzt. Daraus und aus der Gleichung ${\displaystyle |V|-|E|+|F|=2}$ (Eulerscher Polyedersatz) folgt ${\displaystyle |E|\leq 3\cdot |V|-6}$ und daraus folgt für den durchschnittlichen Knotengrad

${\displaystyle d(G)={\frac {\sum _{v\in V}d_{G}(v)}{|V|}}={\frac {2\cdot |E|}{|V|}}\leq {\frac {2\cdot (3\cdot |V|-6)}{|V|}}={\frac {6\cdot |V|-12}{|V|}}<6}$

Das heißt, dass für endliche planare Graphen der durchschnittliche Knotengrad kleiner als 6 ist. Graphen mit höherem durchschnittlichen Knotengrad können nicht planar sein.