DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Die Elemente von V heißen Ecken. Ist (x,y) Adj, so heißen x und y adjazent (oder benachbart). Wird definieren eine Menge E von zweielementigen Teilmengen von V durch {x,y} E falls (x,y) Adj. Die Elemente von E werden (ungerichtete) Kanten genannt. "V" und "E" kommen von den englischen Worten "vertices" und "edges" und sind völlig üblich. "{x,y} E" kürzt man oft auf "xy E" ab. In der Digraphen-Darstellung eines Graphen gibt es keine Schlingen, und zu jeder gerichteten Kante (x,y) gibt es auch die Gegenrichtung (y,x). Deshalb wird die Darstellung fast immer vereinfacht, indem je zwei antiparallel gerichtete Kanten durch eine (richtungslose) Linie zwischen den Ecken ersetzt werden. Anstatt der Darstellung rechts oben nimmt man also die einfachere Darstellung rechts unten. Natürlich ist |E| = 2|Adj| gleich der Anzahl dieser Linien.

Graphen "sind" Strukturen, die aus einer Menge V und einer Menge E zweielementiger Teilmengen von E bestehen. Diese Beschreibung ist üblicher als die oben.

G sei ein Graph mit Eckenmenge V und Kantenmenge E. Der Grad dG(x) einer Ecke x V ist die Zahl der Kanten zv mit x=z oder x=v, d.h. die Zahl der Ecken y V mit {x,y} Adj. Diese Zahl kann auch eine unendliche Kardinalzahl sein.

Mittels Doppelte Abzählung ergibt sich sofort:
Die Zahl der Ecken ungeraden Grades in jedem endlichen Graphen ist gerade.

Bipartite Graphen lassen sich algorithmisch schnell erkennen und die Bipartition erzeugen. Ein Beispiel eines Problems, das auf den zweiten Blick auf genau diese Bestimmung der Bipartition eines bipartiten Graphen hinausläft.

Ein Weg (von x₀ nach x_k) in einem Graphen ist eine endliche Folge x₀, x₁, ... , x_k verschiedener Ecken bei denen je zwei aufeinanderfolgende --- x_i und x_i+1 --- benachbart sind. Bei einem Kreis müssen zusätzlich auch noch x_k und x₀ benachbart sein (der Weg schließt sich zum Kreis). Die Länge eines Kreises bzw. Weges ist gleich der Anzahl der beteiligten Ecken, bzw. diese Anzahl minus eins.

Zwei Ecken x, y eines Graphen liegen genau dann in derselben Zusammenhangskomponente falls es einen Weg von x nach y gibt.

Der Abstand d_G(x,y) zweier Ecken x und y in einem Graphen G ist die kürzeste Länge eines Weges von x nach y falls es solche Wege überhaupt gibt (d.h. falls x und y in derselben Komponente liegen). Andernfalls sagen wir, der Abstand ist unendlich. Beachten Sie folgende Eigenschaften des Abstands:
d_G(x,y)=0 genau dann wenn x = y,
d_G(x,y) = d_G(y,x) (Symmetrie des Abstands), und
d_G(x,z) d_G(x,y) + d_G(y,z) (die sogenannte Dreiecksungleichung).

Sehr viele Probleme, bei denen man es zuerst nicht vermutet, lassen sich als Abstandsprobleme in Graphen umformulieren. Beispiele sind das bekannte "Türme von Hanoi"-Rätsel, aber etwa auch gewisse Reihenfolgerätsel, siehe auch diese interessante externe Seite über das 3-Gläser-Problem (das aber mit Digraphen modelliert wird).

Es gibt eine interessante Charakterisierung bipartiter Graphen mittels Weglängen:

Ein Graph ist genau dann bipartit, falls es in ihm keine Kreise ungerader Länge gibt.

Beweis: (1) Sei G bipartit mit Bipartition A und B der Eckenmenge. Die Ecken jedes Kreises müssen abwechselnd in A und B liegen, weshalb die Länge gerade sein muß. (2) Ist umgekehrt G ohne Kreise ungerader Länge, dann zeigen wir, wie wir in jeder Zusammenhangskomponente Q von G eine solche Bipartion der Eckenmenge finden können. Da keine Kanten zwischen Zusammenhangskomponenten verlaufen können, setzen sich diese Bipartitionen der Komponenten zu einer zulässigen Bipartition der gesamten Eckenmenge zusammen. Wir wählen eine beliebige Ecke x in Q und definieren A als die Menge der Ecken y in Q mit dG(x,y) gerade, und B als die Menge der Ecken y in Q mit dG(x,y) ungerade. Nehmen wir an (*), diese Bipartition der Eckenmenge von Q erfülle obige Eigenschaft nicht, d.h. es gäbe oBdA benachbarte Ecken y, z in A. Dann sind beide Zahlen dG(x,y) und dG(x,z) gerade. Andererseits folgt wegen dG(y,z)=1 (mit Hilfe obiger Dreiecksungleichung) der Widerspruch |dG(x,y) - dG(x,z)| 1. Also ist Annahme (*) falsch, und die Bipartion OK.

1. Setze m(y) := -1 für alle Ecken y.
2. d := 0; m(x₀) := 0; NewMembers := {x₀};
3. while (NewMembers Ø) {
   • NewMembers := Ø;
   • for (y: m(y)=d) for (z: (z,y) Adj) if (m(z) == -1) {
     • NewMembers := NewMembers {z};
     • m(z) := d+1; }
   • d := d+1; }
4. Ausgabe von m; STOP;

Übungsaufgabe: für eine beliebige natürliche Zahl n definieren wir den Graphen H_n auf der Eckenmenge V aller 0-1 Worte der Länge n (d.h. auf {0,1}ⁿ): Zwei Worte sind genau dann benachbart, wenn sie sich in genau einer Koordinate unterscheiden. Zeigen Sie, daß dieser Graph zusammenhängend und bipartit ist, daß der Abstand zweier beliebiger Ecken hüchstens gleich n ist, und skizzieren Sie H₄.

Test

Wieviele Zusammenhangskomponenten hat der Graph Ist der Graph bipartit? dG(x,y) = ? dG(x,z) = ? Wieviel Kreise gibt es im Graphen Wieviele Wege gibt es von x nach y