Zu den anderen Abschnitten:
 


Von Graphen, Genen und dem WWW


Online-Skriptum


Graphen
 

Die Welt der Graphen

Eine besondere Art von Objekten wird in fast jedem Abschnitt dieses Online-Skriptums Verwendung finden: Graphen. Die Welt der Graphen ist bunt und reichhaltig. Da gibt es Wege, Bäume, Wurzeln, Blätter, Farben, Gewichte und vieles mehr. Auch abstraktere Begriffe wie Ecke, Kante, Weg, Länge und Kreis treten auf und erhalten neue Bedeutungen. Trotz - oder vielleicht gerade wegen - der Einfachheit der ihr zu Grunde liegenden Idee beherbergt sie eine Vielfalt komplexer Strukturen. Insbesondere in Zusammenarbeit mit anderen Teilgebieten der Mathematik ergibt sich eine Fülle von Anwendungen. Graphen dienen dazu, Beziehungsstrukturen, Abläufe und Verzweigungen übersichtlich darzustellen, sind manchmal unentbehrliche Hilfsmittel, um Probleme zu lösen und treten bisweilen sogar als die zentralen Objekte des Interesses auf. Die Graphentheorie ist ein schnell wachsendes Gebiet der modernen Mathematik. Aber auch in ästhetischer Hinsicht ist die Welt der Graphen nicht ohne Reize, stellt sie doch ein schönes Beispiel für einen "diskreten" Blick auf die Welt dar.

Wir wollen hier keine Einführung in die Graphentheorie geben, sondern nur einige der grundlegenden Eigenschaften von Graphen besprechen, um ein bisschen Sicherheit im Umgang mit ihnen zu gewinnen und um uns ein kleines Vokabular für die folgenden Anwendungen zurecht zu legen. Wenden wir uns also der Frage zu, was ein Graph ist.
 

Was ist ein Graph?

Ein Graph (nicht zu verwechseln mit dem Begriff des Funktionsgraphen) ist ein Objekt, das in dieser Form veranschaulicht werden kann:

Es besteht aus Ecken (schwarze Punkte, auch Knoten genannt, englisch vertices) und Kanten (rote Linien, auch Bögen genannt, englisch edges). Jede Kante verbindet genau zwei (voneinander verschiedene) Ecken. Dabei kommt es nicht auf die präzise Lage und Form der Ecken und Kanten an: Wichtig ist lediglich, welche Ecken durch wieviele Kanten miteinander verbunden sind. So wollen wir beispielsweise zwischen dem obigen Graph und diesem

nicht unterscheiden. (Es ist ja lediglich eine Ecke nach oben gerutscht, und das Ganze wurde ein bisschen deformiert). Demgegenüber stellt diese Zeichnung

einen davon echt verschiedenen Graphen dar. Ein Graph drückt also in gewisser Weise eine "Beziehungsstruktur" aus, wobei es auf die Art der Beziehungen zwischen zwei Ecken nicht ankommt, sondern lediglich auf ihre Anzahl.
 

Formale Definition des Graphen

Um zu präzisieren, worauf es beim Begriff des Graphen ankommt und worauf nicht, benötigen wir eine genaue Definition. Es gibt verschiedene (äquivalente) Methoden, den Begriff des Graphen formal zu fassen. Eine ist diese:

Definition: Ein Graph ist gegeben durch

  • eine endliche Menge E (die Eckenmenge),
  • eine endliche Menge K (die Kantenmenge) und
  • eine Abbildung  : K  ®  F, wobei F die Menge aller 2-elementigen Teilmengen von E ist.

Überlegen wir kurz, was das bedeutet: Jede 2-elementige Teilmenge von E ist von der Form {x, y}, wobei x und y zwei (verschiedene) Elemente von E (d.h. zwei verschiedene Ecken) sind. (Man spricht auch von einem ungeordneten Paar). Die Funktion f ordnet jedem Element k Î K (d.h. jeder Kante) ein solches ungeordnetes Paar von Ecken zu. Die beiden Ecken dieses Paares bezeichnen wir als "durch die Kante k verbunden". Ist x Î E und k Î K, so sagen wir, dass "die Ecke x auf der Kante k liegt", wenn x Î f (k) ist. Durch diese Sprachregelungen entsteht die intuitive Vorstellung eines Graphen nach Art der obigen Zeichnungen.

In der graphentheoretischen Literatur, die formal rigoroser vorgeht, als wir es in der Folge tun werden, wird ein Graph G als Tripel (E, K, f ) betrachtet, manchmal auch einfach als Paar (E, K) oder in der Form G(E, K) angeschrieben. Die Ecken- und Kantenmenge eines gegebenen Graphen G schreibt man auch in der Form E(G) und K(G).

Beispiel für eine formale Charakterisierung eines Graphen:

  • Eckenmenge E = {x1x2x3x4x5x6x7}
  • Kantenmenge K = {k1k2k3k4k5k6k7}
  • Abbildung  : K  ®  F
        f(k1) = {x1, x2}         f(k5) = {x5, x6}
        f(k2) = {x1, x4}         f(k6) = {x5, x6}
        f(k3) = {x2, x3}         f(k7) = {x2, x4}
        f(k4) = {x3, x4}

Das ist genau der zu Beginn dieses Abschnitts angegebene Graph. (Übungsaufgabe: Fügen Sie die entsprechenden Ecken- und Kantenbezeichnungen in die erste der obigen Zeichnungen ein!)

Genau genommen kommt es nicht einmal darauf an, welcher Art die Elemente der Mengen E und K sind, sondern nur auf deren Mächtigkeit. Wir bezeichnen zwei durch die Tripel (E, K, f ) und (E', K', f ' ) gegebenen Graphen als isomorph, wenn sie durch bloße Umbenennung von Ecken und Kanten auseinander hervorgehen. Formal ausgedrückt ist das dann der Fall, wenn es zwei bijektive Abbildungen  h : E ® E'  und  j : K ® K'  gibt, für die  f ' = h o f o j-1  gilt, wobei die Wirkung von h auf 2-elementige Teilmengen von E durch h({x, y}) = {h(x), h(y)} definiert ist. Isomorphe Graphen werden vom graphentheoretischen Standpunkt nicht voneinander unterschieden.

Wenn Sie sich in der Literatur zur Graphentheorie ein bisschen umsehen, so werden Sie auf andere (äquivalente) Definitionen des Graphenbegriffs stoßen, beispielsweise auf diese:

Alternative Definition: Ein Graph ist gegeben durch

  • eine endliche Menge E (die Eckenmenge) und
  • eine Abbildung g : F  ®  N, wobei F die Menge aller 2-elementigen Teilmengen von E und N die Menge der natürlichen Zahlen (beginnend mit 0) ist.

Ist {x, y}eine 2-elementige Teilmenge von E, dann bezeichnet g({x, y}) die Anzahl der Kanten, die x und y verbinden. Die Kantenmenge K - von der hier nicht gesprochen wird - kann nachträglich (und bis auf bloße Umbenennung ihrer Elemente eindeutig) konstruiert werden. Werden die Ecken x und y durch r ( >0 ) Kanten verbunden, so können diese beispielsweise durch die r Paare ({x, y},1), ({x, y},2),...({x, y}, r) charakterisiert werden.

Nun sollte klar sein, was an einem in der Ebene gezeichneten Schaubild eines Graphen relevant ist und was nicht. Von der formalen Strenge der obigen Betrachtungen werden wir in den folgenden Abschnitten kaum Gebrauch machen, sie sollte aber im Hinterkiopf immer mitschwingen. Im Allgemeinen kommt man mit einem intuitiven Bild des Graphen und einer korrekten Verwendung der Begriffe "Ecke" und "Kante" recht weit. Vor diesem Hintergrund bildet natürlich auch die Zeichnung eine legitime (und schulgerechte) Methode, Graphen anzugeben.

Übungsaufgabe:

Stellt    denselben
Graphen
dar wie 
  ?

Begründen Sie Ihre Antwort!
 

Zwei weitere Definitionen

Wir werden im Folgenden zwei weitere Definitionen benötigen:

  • Gibt es in einem Graphen zwei Ecken, die durch mehr als eine Kante verbunden werden, so nennt man ihn "Graph mit Mehrfachkanten", andernfalls heißt er einfach.

         
    Graph mit Mehrfachkanten     einfacher Graph

    Einfache Graphen sind formal sehr leicht in den Griff zu bekommen, da von ihnen nur gesagt werden muss, welche Eckenpaare verbunden sind und welche nicht.

    Bezeichnet F die Menge aller 2-elementigen Teilmengen der Eckenmenge E, so kann ein einfacher Graph als Teilmenge K von F aufgefasst werden: {x, y} ist genau dann in K enthalten, wenn x und y durch eine Kante verbunden sind.
    Daher ist K gerade die Kantenmenge.

    Alternativ dazu kann ein einfacher Graph auch als Abbildung g : F  ®  Z2 betrachtet werden, wobei F die Menge aller 2-elementigen Teilmengen von E und Z2 = {0, 1} ist. Das gibt Anlass zu einer "binären" Betrachtungsweise: Werden die Elemente von F durchnummeriert, so kann ein einfacher Graph mit Eckenmenge E als Binärzahl (mit so vielen Stellen wie F Elemente hat) dargestellt werden. Dabei entspricht jeder 1-er einer Kante. Übungsaufgabe: Benutzen Sie diese Darstellungsform, um die Anzahl aller einfachen Graphen mit einer gegebenen Eckenmenge zu bestimmen!
  • Der Grad q(x) einer Ecke x Î E ist die Anzahl der Kanten, die von ihr ausgehen (d.h. die sie mit anderen Ecken verbinden). Ist q(x) = 0, so heißt x isolierte Ecke.

    Klarerweise ist die Summe der Grade aller Ecken gleich dem Doppelten der Anzahl der Kanten. (Beweis: Da jede Kante genau zwei Ecken verbindet, trägt sie insgesamt 2 zu dieser Summe bei).
     
Erweiterungen

Der oben definierte Begriff des Graphen kann in vielerlei Hinsicht erweitert werden:

  • Wird jede Kante mit einem Richtungssinn versehen, so spricht man von einem gerichteten Graphen. (In gerichteten Graphen wird darüber hinaus zugelassen, dass eine Kante eine Ecke mit sich selbst verbindet). Demgegenüber werden Graphen des oben definierten Typs manchmal auch ungerichtete Graphen genannt.
  • Ecken und Kanten können mit "Färbungen" oder mit (numerischen) "Gewichten" versehen werden. Dies führt zu den Begriffen der ecken- und kantengefärbten und der ecken- und kantengewichteten Graphen. (Auch in diesen verallgemeinerten Graphen wird manchmal zugelassen, dass eine Kante eine Ecke mit sich selbst verbindet).
  • In einem so genannten Hypergraphen kann eine "Kante" mehr als zwei Ecken "verbinden".
  • Ein unendlicher Graph besitzt unendlich viele Ecken oder Kanten. (Dabei wird im Allgemeinen vorausgesetzt, dass zwei Ecken nur durch eine endliche Anzahl von Kanten verbunden sind. Mit dieser Konvention ist ein Graph genau dann unendlich, wenn seine Eckenmenge unendlich ist). Demgegenüber werden Graphen des oben definierten Typs auch als endliche Graphen bezeichnet.

Von den daran anknüpfenden Begrifflichkeiten gibt die Seite http://de.wikipedia.org/wiki/Graph_(Graphentheorie) einen kleinen Geschmack.


¬   Vorbemerkungen Übersicht  Spaziergänge und Buslinien   ®