Graphentheorie

Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen untersucht.
Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik von großer Bedeutung.

In der Graphentheorie ist ein Graph eine Menge von Punkten (man nennt diese dann Ecken oder auch Knoten), die eventuell durch Linien (sog. Kanten) miteinander verbunden sind. Die Kanten können auch gerichtet sein, was durch Pfeile dargestellt wird. Je zwei Knoten können nur durch eine Kante verbunden sein. (Sogenannte Multigraphen lassen aber auch mehrfache Verbindungen zu.) Eine Verbindung eines Knotens zu sich selbst (Schleife) kann erlaubt sein oder verboten. Zusätzlich können sowohl Knoten als auch Kanten mit Gewichten (beliebige Zahlen) oder Farben versehen sein.

Formale Definition

Ein Graph G ist ein Tupel (V, E), wobei V eine Menge von Ecken oder Knoten (engl. "vertex") und E eine Menge von Kanten (engl. "edge") bezeichnet. Die Elemente von E sind üblicherweise geordnete Paare aus Elementen von V:

E ⊆ V × V

Werden anstatt geordneter Paare ungeordnete Paare verwendet oder wird verlangt, dass für jedes Paar (a, b) aus E auch (b, a) in E ist, dann ist der Graph ungerichtet, andernfalls gerichtet.

Die Kanten können auch als binäre Relation auf der Eckenmenge V angesehen werden. So entspricht jeder binären Relation ein Graph und umgekehrt. Relationen auf zwei verschiedenen Mengen ergeben einen bipartiten Graphen (siehe unten).

Beispiel

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

Dieser Graph hat fünf Ecken: V = {1,2,3,4,5}. Die Kantenmenge als Menge ungeordneter Paare ist E = { (1,2), (1,5), (2,3), (2,5), (3,4), (4,5) }. Betrachtet man geordnete Paare, so müssen auch (2,1), (5,1), etc. in E aufgenommen werden.

Begriffe

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

Unter einem Graphen versteht man üblicherweise einen einfachen Graphen. Das heißt, dass je zwei Knoten nur durch maximal eine Kante verbunden sind. Sind mehrfache Verbindungen möglich, so spricht man von einem Multigraphen.

Hypergraphen sind Graphen, in denen Kanten (Hyperkanten) nicht nur zwei sondern mehrere Ecken verbinden können. Die Adjazenzmatrix (siehe unten) wird dann zu einer höherdimensionalen Struktur - einem Tensor.

Multigraphen sind Graphen, in denen zwischen zwei Ecken mehrere Kanten verlaufen können. Formal wird dies durch eine Abbildung der Kanten in die Menge der natürlichen Zahlen beschrieben.

Ein gewichteter Graph ist ein Graph, bei dem den Kanten oder Knoten eine reele Zahl zugeordnet wird. Zur Unterscheidung spricht man dann auch von kanten- oder knotengewichteten Graphen.

Die Menge aller Kanten, die zu einer Ecke a hin gerichtet sind, bezeichnet man als Eingangsmenge von a. Die Anzahl dieser Kanten bezeichnet man als Eingangsgrad von a. Analog sind Ausgangsmenge und Ausgangsgrad definiert. Bei ungerichteten Graphen spricht man nur von Grad oder Valenz eines Knotens. In einem regulären Graphen haben alle Ecken den gleichen Grad.

Ein k-partiter Graph ist ein Graph, in dem man die Ecken so in k Gruppen einteilen kann, dass es keine Verbindungen zwischen Ecken der gleichen Gruppe gibt. Ein bipartiter Graph ist ein 2-partiter Graph. Obiger Graph z.B. ist mit den Gruppen {1,3}, {2,4}, {5} 3-partit.

Ein Pfad ist eine Folge von Ecken mit der Eigenschaft, dass zwei aufeinanderfolgende Ecken dieser Folge verbunden sind. Ein Pfad heißt einfach, wenn keine Ecke in der Folge zweimal vorkommt.
Bemerkung: In der Literatur wird statt von einem Pfad auch oft von einem Weg gesprochen und ein Weg, in dem keine Ecke in der Folge zweimal vorkommt als Pfad bezeichnet. Bemerkung: Ein Pfad lässt 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.

Ein Graph heißt zusammenhängend, wenn zwischen je zwei beliebigen Ecken ein Pfad exisitert.

Ein Zyklus oder Kreis ist ein Pfad, der in derselben Ecke beginnt wie er endet, also ein geschlossener Pfad. Bemerkung: In der Literatur wird ein Zyklus oft nur dann auch als Kreis bezeichnet, wenn außer der ersten und letzten Ecke keine Ecke zweimal vorkommt. Enthält ein Graph keinen Zyklus, wird er als zyklenlos, kreislos oder kreisfrei bezeichnet.
Beispiel: (1,5,2,1) ist im obigen Graph ein Zyklus.

Ein ungerichteter Graph heißt Baum, falls er zusammenhängend und kreifrei ist. Ein Baum hat immern n-1 Kanten, wobei n die Anzahl der Ecken ist.

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, dass ein Graph kein Streckengraph sein muss, d.h. die Kanten müssen nicht notwendigerweise geradlinig sein.

Ein Graph heißt eben oder planar, wenn man ihn in die Ebene zeichnen kann, ohne dass 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.

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

Ein Graph heißt zusammenhängend, wenn je zwei Knoten über einen Pfad verbunden sind.

Ein Baum ist ein zusammenhängener zyklenloser Graph. Ein Baum kann auch eine Wurzel haben - ein spezieller Knoten, der in Bezug auf gewisse Anwendungen als Startpunkt oder Basis angesehen wird. Zwischen zwei Knoten eines Baumes gibt es genau einen einfachen Pfad. Ein spannender Baum ist ein Teilgraph eines Graphen G, der nur Kanten aus G und alle Ecken aus G enthält. Ein nicht-zusammenhängender zyklenloser Graph heißt Wald.

Unter einer Graphenfärbung versteht man üblicherweise die Zuweisung von sog. Farben zu den Ecken in einer Weise, dass keine zwei benachbarten Ecken die gleiche Farbe haben. Die kleinste Anzahl von Farben mit der ein Graph färbbar ist, wird als Farbzahl bezeichnet. Man sagt, dass ein Graph k-färbbar ist, wenn die Farbzahl kleiner oder gleich k ist.

Vertauscht man Kanten und Ecken eines Graphen miteinander, entsteht ein dualer Graph.

Adjazenzmatrix

Die Kantenmenge kann auch in einer sogenannten Adjazenzmatrix oder Nachbarschaftsmatrix dargestellt werden. Die Matrix hat die Größe n×n, wenn n die Anzahl der Ecken ist. Das Element an der Stelle (i,j) ist 1 oder wahr, wenn der i-te Knoten mit dem j-ten verbunden ist, andernfalls 0 oder falsch. Für obigen Graphen ergibt sich folgende Matrix:

  | 1 2 3 4 5
--+----------
1 | 0 1 0 0 1
2 | 1 0 1 0 1
3 | 0 1 0 1 0
4 | 0 0 1 0 1
5 | 1 1 0 1 0

Ist die Matrix symmetrisch (d.h. M_i,j = M_j,i), so ist der Graph ungerichtet. Werden Schleifen (also Verbindungen eines Knotens zu sich selbst) verboten, dann muss die Diagonale (d.h. i=j) leer sein.

Bei Graphen mit Kantengewichten können die Gewichte als Elemente der Adjazenzmatrix eingetragen werden, wobei oft 0 (oder ∞) für keine Verbindung steht.

Sind zwei Graphen auf der selben Knotenmenge gegeben, dann können die Adjazenzmatrizen multipliziert werden (Matrixmuliplikation). Die Elemente der Ergebnismatrix geben an, ob ein Knoten durch eine Kante aus dem ersten Graphen gefolgt von einer Kante aus dem zweiten Graphen erreicht werden kann. Dementsprechend ergibt die Multiplikation einer Adjazenzmatrix mit sich selbst (Quadration) die Verbindungen über exakt zwei Kanten an. Allgemein gibt M^k die Existenz von Verbindungen (Pfade) der Länge k an.

Wichtige Problemstellungen und Algorithmen in der Graphentheorie

Um einen Graphen mit einer möglichst kleinen Anzahl von Farben zu färben, wird üblicherweise der Greedy-Algorithmus verwendet. Dieser findet jedoch nicht immer eine Lösung für die kleinstmögliche Anzahl von Farben. Das Vier-Farben-Problem beschäftigt sich mit der Frage, ob vier Farben ausreichen, um einen beliebigen planaren Graphen zu färben.

Das Problem, den kleinsten spannenden Baum zu finden, kann mit Hilfe des Kruskal-Algorithmus oder des Prim-Algorithmus gelöst werden.

Der Dijkstra-Algorithmus findet den kürzesten Pfad in einem Graphen.

Das Traveling-Salesman-Problem ist das Problem, den kürzesten (im Sinne der Kantengewichtung) geschlossenen Pfad zu finden, der alle Ecken enthält. Dieses Problem hat sehr hohe rechnerische Komplexität. Daher wird es meist nur über Heuristiken annähernd gelöst, wie z.B. mit dem Nächster-Nachbar-Algorithmus.

DER NEUE ARTIKEL

Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen untersucht.

Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik von großer Bedeutung.

betrachteter Gegenstand

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

Man klassifiziert dabei in:

endliche Graphen, bei denen die Menge der Knoten und Kanten endlich ist von unendlichen Graphen, auf die dies nicht zutrifft und
gerichtete Graphen, bei denen die Kanten gerichtet sein können (dargestellt durch Pfeile statt Linien), von ungerichteten Graphen.

Kompliziertere Graphentypen sind:

Multigraphen, bei denen im Gegensatz zu üblichen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen und
Hypergraphen, bei denen im Gegensatz zu üblichen Graphen Kanten mehr als nur zwei Knoten verbinden können.

Je nach Problemstellung können Knoten und Kanten auch mit Farben (formal mit natürlichen Zahlen) oder Gewichten (d.h. mit beliebigen Zahlen) versehen werden. Man spricht dann von Knoten- bzw. Kantengefärbten oder -gewichteten Graphen.

Eine Liste mit Links auf exakte Definitionen findet man unter Graphentypen.

Eigenschaften von Graphen

hier kommt noch etwas Text mit ein paar Beispielen.

Eine Liste mit Links auf exakte Definitionen findet man unter Grapheneigenschaften.

graphentheoretische Probleme