Grad (Graphentheorie)

Definitionen

Zwei Knoten heißen in einem ungerichteten Graphen (bzw. Hypergraphen) G benachbart oder adjazent, wenn sie Element einer Kante (bzw. Hyperkante) von G sind. Ein Knoten v und eine ungerichtete Kante e (bzw. Hyperkante) heißen inzident, falls v Element von e ist.

Ein Knoten x heißt Nachbar von einem Knoten y in einem ungerichteten Graphen (bzw. Hypergraphen) G, wenn {x, y} Kante von G ist. Mit N_G(v) bezeichnet man die Menge aller Nachbarn eines Knotens v in G. Ferner bezeichnet man mit N_G(X) die Menge aller Nachbarn der Knoten von X in G. N_G(v) bzw. N_G(X) nennt man auch Nachbarschaft von v bzw. X.

Mit d_G(v) bezeichnet man den Grad des Knotens v in einem ungerichteten Graphen G. Dabei ist d_G(v) in

• Graphen ohne Mehrfachkanten die Anzahl der Nachbarn von v,
• Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller mit v inzidenten Kanten.

Den kleinsten Grad eines Knotens in G bezeichnet man dann als Minimalgrad von G, den größten Grad eines Knotens in G bezeichnet man als Maximalgrad von G.

Ein Knoten x heißt Vorgänger von y in einem gerichteten Graphen G, wenn (x, y) gerichtete Kante von G ist. Mit N_G^-(v) bezeichnet man die Menge aller Vorgänger eines Knotens v in G. Ferner bezeichnet man mit N_G^-(X) die Menge aller Vorgänger der Knoten von X in G. N_G^-(v) bzw. N_G^-(X) nennt man auch Vorgängermenge von v bzw. X.

Analog heißt x Nachfolger von y in G, wenn (y, x) gerichtete Kante von G ist. Mit N_G⁺(v) bezeichnet man die Menge aller Nachfolger eines Knotens v in G. Ferner bezeichnet man mit N_G⁺(X) die Menge aller Vorgänger der Knoten von X in G. N_G⁺(v) bzw. N_G⁺(X) nennt man auch Vorgängermenge von v bzw. X.

Mit d_G^-(v) bezeichnet man den Eingangsgrad des Knotens v in einem gerichteten Graphen G und mit d_G⁺(v) dessen Ausgangsgrad. Dabei ist d_G^-(v) in

• Graphen ohne Mehrfachkanten die Anzahl der Vorgänger von v,
• Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (v, x).

und d_G⁺(v) in

• Graphen ohne Mehrfachkanten die Anzahl der Nachfolger von v,
• Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (x, v).

In ungerichteten Graphen Graphen bzw. Hypergraphen nennt man einen Knoten isoliert, wenn er keine Nachbarn besitzt. In gerichteten Graphen nennt man einen Knoten isoliert, wenn er keine Vorgänger und keine Nachfolger besitzt.

Falls klar ist, um welchen Graphen es sich handelt, läßt man den Index G bei N, N^-, N⁺, d, d^- und d⁺ auch oft weg.

Beispiele

kommen noch