Graphentheorie

Die Graphentheorie ist ein Teilgebiet der Mathematik und der Informatik.
In der Graphentheorie ist ein Graph eine Menge von Punkten (man nennt diese dann Ecken oder auch Knoten), die eventuell durch Kanten miteinander verbunden sind.

Formal kann man dies so definieren:
Ein (un)gerichteter Graph G(V,E) ist eine Menge von Ecken V (engl. "vertex"), zusammen mit einer Menge E (engl. "edge") von (un)geordneten Paaren aus Elementen von V.

 1 _____ 2 _____ 3
  \     /       /
   \   /       /    
    \ /       /
     5 _____ 4

Ein Beispiel eines ungerichteten Graphen mit fünf Ecken.(Bei einem gerichteten Graph hat jede Kante eine Richtung. Diese wird beim Zeichnen durch Pfeile angezeigt.) Im folgenden ist die Rede von ungerichteten Graphen, falls nicht anders erwähnt.

benachbart

Zwei Ecken e1 und e2 bezeichnet man als benachbart, wenn sie durch eine Kante verbunden sind. Formal: wenn die Kantenmenge E das Paar (e1,e2) oder (e2,e1) enthält.

Eingangsmenge, Eingangsgrad (nur für gerichtete Graphen)

Die Menge aller Kanten, die zu einer Ecke e1 hin gerichtet sind, bezeichnet man als Eingangsmenge von e1. Die Anzahl dieser Kanten bezeichnet man als Eingangsgrad von e1. Analog sind Ausgangsmenge und Ausgangsgrad definiert.

Pfad

Ein Pfad ist eine Folge von Ecken mit der Eigenschaft, daß jede Ecke sowohl zur vorangehenden als auch zur nachfolgenden Ecke dieser Folge benachbart ist. Ein Pfad heißt einfach, wenn keine Ecke in der Folge zweimal vorkommt.
Bemerkung:
Ein Pfad läßt sich ebenso als Folge von Kanten definieren. Dies sei dem Leser überlassen.
Beipiel:
Im obigen Graphen ist (1,2,5,1,2,3) ein Pfad, und (5,1,2,3) sogar ein einfacher Pfad.

Kreis

Ein Kreis ist ein Pfad, der in derselben Ecke beginnt wie er endet, also ein geschlossener Pfad. Enthält ein Graph keinen Kreis, wird er als kreislos bezeichnet.
Beispiel:
(1,5,2,1) ist im obigen Graph ein Kreis

vollständig

Ein Graph heißt vollständig wenn jede Ecke zu jeder Ecke benachbart ist. Der vollständige Graph mit n Ecken wird oft mit K_n bezeichnet.
Beispiel:
Der obige Graph ist nicht vollständig. K₄ sieht folgendermaßen aus:

         1______2____
         |\     |   |
         | \    |   |
         |  \   |   |
         |   \  |   |
         |    \ |   |
         4_____3    |
         |__________|

Dies zeigt auch, daß ein Graph kein Streckengraph sein muß, d.h. die Kanten müssen nicht notwendigerweise geradlinig sein.

eben

Ein Graph ist eben, wenn man ihn in die Ebene zeichnen kann, ohne daß sich zwei Kanten überschneiden.
Beispiel:
Die beiden oben gezeichneten Graphen sind eben. Der vollständige Graph K₅ ist der einfachste Graph, der nicht eben ist.

gesättigt

Ein ebener Graph heißt gesättigt, wenn der durch Hinzufügen einer beliebigen Kante entstehende Graph nicht mehr eben ist.

Bekannte Problemstellungen in der Graphentheorie

Wichtige Algorithmen