Grundbegriffe der Graphentheorie

Bevor wir Graphen genauer untersuchen, vereinbaren wir noch:

Vereinfachte Angabe der Kanten

Wir notieren eine Kante { a, b } oft kurz als ab oder a-b.

Damit bedeutet ab  ∈  K also { a, b }  ∈  K. Da wir ungerichtete Graphen betrachten, ist ab immer gleichwertig zu ba. Sobald gerichtete Graphen zugelassen werden, müssen wir ab (die gerichtete Kante von a nach b) von ba (die gerichtete Kante von b nach a) unterscheiden.

Beispiel

Den Graphen des obigen Beispiels können wir nun in der besser lesbaren Form G = (E, K) mit E = { 1, 2, 3, 4 }, K = { 12, 13, 14, 23, 34 } angeben. Sobald die Ecken zweistellig sind, können Klammern oder die Notation a-b verwendet werden, um zum Beispiel die Kante 11-2 = { 2, 11 } von der Kante 1-12 = { 1, 12 } zu unterscheiden.

Wir erinnern zudem an:

Definition (Mächtigkeit oder Kardinalität einer endlichen Menge)

Für eine endliche Menge M sei |M| die Anzahl der Elemente von M. Die natürliche Zahl |M| heißt die Mächtigkeit oder Kardinalität von M. Gilt |M| = n für eine endliche Menge, so heißt M eine n-elementige Menge oder eine Menge mit genau n Elementen.

Ist M = { a₁, …, a_n } mit paarweise verschiedenen a_i, so gilt |M| = n. Ist dagegen M = { b₁, …, b_m } gegeben ohne weitere Information über die Elemente b_i, so gilt |M| ≤ m, da z. B { 1, 2 } = { 1, 1, 2 } = { 1, 2, 1, 2 }.

Ordnung und Größe

Nach diesen Vorbereitungen definieren wir:

Definition (Ordnung, Größe)

Sei G = (E, K) ein Graph. Dann heißt |E| die Ordnung und |K| die Größe von G.

Dass die Größe über die Kantenmenge und nicht über die Eckenmenge erklärt wird, hat seine Gründe in der Komplexitätstheorie für graphentheoretische Algorithmen: In der Regel ist |K| das Maß, das über die Laufzeit eines Algorithmus entscheidet und nicht |E|.

Beispiele

(1)	Der Graph G = ({ 1, 2, 3 }, ∅) hat die Ordnung 3 und die Größe 0.

(2)	Der Graph G = ({ 1, 2, 3, 4, 5 }, { 12, 24 } } hat die Ordnung 5 und die Größe 2. Streichen der an keinen Kanten beteiligten Ecken 3 und 5 liefert den Graphen G′ = ({ 1, 2, 4 }, { 12, 24 } } der Ordnung 3 mit unveränderter Größe 2.

Aus der Ordnung ergibt sich eine Schranke für die Größe:

Satz (Größenabschätzung)

Sei G = (E, K) ein Graph der Ordnung n. Dann gilt 2|K| ≤ n (n − 1).

Beweis

Sei M = { { a, b } | a, b  ∈  E, a ≠ b } die Menge aller Teilmengen von E mit genau zwei Elementen. Dann gilt

|M| = $( \binom{n}{2} )$ = ^{n (n − 1)}₂.

Wegen K ⊆ M folgt die Abschätzung.

Alternativ können wir auch Adjazenz-Matrizen und eine Gauß-Summe verwenden, um diese Abschätzung zu erhalten. Denn eine Adjazenz-Matrix eines Graphen mit n Ecken ist durch die 1 + … + (n − 1) = n (n − 1)/2 Einträge oberhalb (bzw. unterhalb) der Hauptdiagonalen bestimmt. Diese Einträge entsprechen genau den möglichen Kanten des Graphen.

Nachbarschaftsverhältnisse

Viele der folgenden Begriffe sind beinahe selbsterklärend:

Definition (Nachbarn, Grad, isolierte Ecke, Gradfolge)

Sei G = (E, K) ein Graph. Sind a, b Ecken von G mit ab  ∈  K, so heißen die Ecken a und b benachbart und a ein Nachbar von b in G. Wir setzen

N(a)	= { b  ∈  E \| b ist Nachbar von a },(Menge der Nachbarecken)
d(a)	= \|N(a)\|.(Grad einer Ecke)

Eine Ecke a heißt isoliert, falls d(a) = 0.

Ordnen wir die Ecken von G als Folge e₁, …, e_n so an, dass d(e_i) ≤ d(e_i + 1) für alle 1 ≤ i < |E| gilt, so heißt d(e₁), …, d(e_n) die Gradfolge von G.

Die Nachbarschafts- und Gradbildung können wir als Funktionen auf der Eckenmenge auffassen. Es gilt

N : E → ℘(E) mit ℘(E) = { A | A ⊆ E }, d : E → ℕ.

Anordnung der Gradfolge

In der Gradfolge ordnen wir die Grade von klein nach groß. Die Gradfolge wird in der Literatur oft auch umgekehrt (von groß nach klein) definiert.

Beispiel

Sei G = (E, K) mit E = { 1, 2, 3, 4, 5, 6, 7 } und

K = { 13, 14, 16, 17, 34, 35, 45, 47, 56 }).

Dann gilt

N(1) = { 3, 4, 6, 7 }	N(2) = { }	N(3) = { 1, 4, 5 }
N(4) = { 1, 3, 5, 7 }	N(5) = { 3, 4, 6 }	N(6) = { 1, 5 }
N(7) = { 1, 4 }

Damit ergibt sich für die Gradfunktion

d(1) = 4, d(2) = 0, d(3) = 3, d(4) = 4, d(5) = 3, d(6) = 2, d(7) = 2.

Die Gradfolge von G ist 0, 2, 2, 3, 3, 4, 4.

Dass in diesem Beispiel die Summe 0 + 2 + 2 + 3 + 3 + 4 + 4 = 18 über alle Grade das Doppelte der Anzahl 9 der Kanten ist, ist kein Zufall. Unser erstes bemerkenswertes Ergebnis der Graphentheorie ist:

Satz (Gradsumme)

Sei G = (E, K) ein Graph der Größe k = |K|. Dann gilt

∑_{a  ∈  E} d(a) = 2k.

Beweis

Jede Kante hat genau zwei Nachbarn und trägt damit genau 2 zur Gradsumme bei. Genauer zeigt man die Behauptung durch Induktion nach der Größe k ≥ 0 (Übung).