Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

(ungerichtete) Graphen

Definition: Eine Menge V, zusammen mit einer irreflexiven und symmetrischen Relation Adj auf V wird ungerichteter Graph genannt.
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.

G sei ein Graph mit Eckenmenge V und Adjazenzrelation Adj. G ist zusammenhängend, falls er, betrachtet als Digraph, stark zusammenhängend ist. Andernfalls werden die starken Zusammenhangskomponenten des Digraphen als (Zusammenhangs-) Komponenten des Graphen bezeichnet.

Ein Graph ist bipartit, falls es eine Partition der Eckenmenge in zwei Mengen A und B gibt, so daß jede Kante zwischen einer Ecke aus A und einer Ecke aus B verläuft.

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 x0 nach xk) in einem Graphen ist eine endliche Folge x0, x1, ... , xk verschiedener Ecken bei denen je zwei aufeinanderfolgende --- xi und xi+1 --- benachbart sind. Bei einem Kreis müssen zusätzlich auch noch xk und x0 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 dG(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:
dG(x,y)=0 genau dann wenn x = y,
dG(x,y) = dG(y,x) (Symmetrie des Abstands), und
dG(x,z) £ dG(x,y) + dG(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.

Breadth First Search BFS

Zusammenhang, Bipartität, Abstände von einer festen Ecke lassen sich für endliche Graphen mit Varianten eines einzigen Grundalgorithmus berechnen. Wir starten mit einer festen Ecke x0, die die Marke "0" erhält. Alle Nachbarn von x0 erhalten die Marke "1". Alle noch unmarkierten Nachbarn (d.h. m=-1) von Ecken mit Marke "1" erhalten die Marke "2", usw. Abgebrochen wird, wenn es für ein i keine unmarkierten Nachbarn von Ecken mit Marke i gibt.
  1. Setze m(y) := -1 für alle Ecken y.
  2. d := 0; m(x0) := 0; NewMembers := {x0};
  3. while (NewMembers ¹ Æ) {
  4. Ausgabe von m; STOP;
Nun sind die Ecken mit Marke i gerade alle Ecken y mit dG(x0,y) = i. Gibt es am Schluß noch unmarkierte Ecken, so sind das die, die unendlichen Abstand zu x0 haben---genau dann ist G nicht zusammenhängend. Beachten Sie, daß die Markierungen der beiden Ecken jeder Kante höchstens um 1 unterscheiden können. Gibt es Kanten bei denen beide Ecken dieselbe Markierung haben, dann haben wir einen ungeraden Kreis und G ist nicht bipartit, andernfalls, falls es keine solche Kanten gibt, ist die Komponente von G, die x0 enthält, bipartit.
Übungsaufgabe: für eine beliebige natürliche Zahl n definieren wir den Graphen Hn auf der Eckenmenge V aller 0-1 Worte der Länge n (d.h. auf {0,1}n): 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 H4.

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

Jetzt könnten Sie sich spezielle Probleme auf Graphen anschauen, wie etwa Euler'sche Linien, oder ...
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.