Graphentheorie

Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander 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, insbesondere der Komplexitätstheorie von großer Bedeutung.

Auf den ersten Blick scheint die Graphentheorie eher eine abstrakte und realitätsferne Disziplin der Mathematik zu sein. Tatsächlich lassen sich aber sehr viele Alltagsprobleme mit Hilfe von Graphen modellieren.

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 bzw. Bögen) miteinander verbunden sind. Die Form der Punkte und Linien spielt in der Graphentheorie keine Rolle.

Man unterscheidet dabei zwischen:

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

Kompliziertere Graphentypen sind:

Multigraphen, bei denen im Gegensatz zu einfachen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen und
Hypergraphen, bei denen im Gegensatz zu einfachen 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.

Exakte Definitionen der verschiedenen Graphentypen findet man im Artikel Graph (Graphentheorie).

Eigenschaften von Graphen

Graphen können verschiedene Eigenschaften haben. So kann ein Graph zusammenhängend, bipartit, eben, eulersch oder hamiltonisch sein. Es kann nach der Existenz spezieller Teilgraphen gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Färbungszahl, Stabilitätszahl oder Cliquenzahl gefragt werden.

Die verschiedenen Eigenschaften können zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl immer kleiner als die Kantenzusammenhangszahl, welche wiederum immer kleiner als der Minimalgrad des betrachteten Graphen ist. In ebenen Graphen ist die Färbungszahl immer kleiner als 5. Diese Aussage ist auch als der 4-Farben-Satz bekannt.

Einige der aufgezählten Grapheneigenschaften sind relativ leicht algorithmisch bestimmbar, d.h. die entsprechenden Algorithmen benötigen in Abhängigkeit der Größe der Graphen nur wenig Zeit, um die Grapheneigenschaft zu berechnen. Andere Eigenschaften sind nur schwer berechenbar und selbst die schnellsten Supercomputer scheitern dann oft schon an relativ kleinen Graphen.

Geschichte

Die Anfänge der Graphentheorie gehen bis in das Jahr 1736 zurück. Damals publizierte Leonhard Euler eine Lösung für das Königsberger Brückenproblem. Die Frage war, ob es einen Rundgang durch die Stadt Königsberg gibt, der jede der sieben Brücken über die Pregel genau einmal benutzt. Euler konnte für dieses Problem eine notwendige Bedingung angeben, und so die Existenz eines solchen Rundganges verneinen. Eine hinreichende Bedingung, sowie einen effizienten Algorithmus, der in einem Graphen einen solchen Rundgang finden kann, wurde erst 1873 von Hierholzer angegeben.

Links

Einen Überblick über die in der Wikipedia verfügbaren graphentheoretischen Artikel liefert diese Liste.

Noch unerklärte Teile des alten Artikels

Formale Definition

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).

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

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. Der Graph ist mit den Gruppen {1,3}, {2,4}, {5} 3-partit. (1,2,5,1,2,3) ist ein Weg und (5,1,2,3) sogar ein Pfad.

Seine Adjazenzmatrix hat folgende Gestallt:

  | 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

Begriffe

Beipiel:

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    |
         |__________|

Plättbarkeit

Informal heißt ein Graph planar oder plättbar, wenn man ihn in die Ebene zeichnen kann, ohne dass sich zwei Kanten überschneiden. Ein Graph der in die Ebene eingebettet ist heißt eben.

Beispiel: Die beiden oben gezeichneten Graphen sind eben.

Der vollständige Graph K₅ ist der einfachste Graph, der nicht planar ist.

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

Bäume

Ein Baum kann auch eine Wurzel haben - ein spezieller Knoten, der in Bezug auf gewisse Anwendungen als Startpunkt oder Basis angesehen wird.

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.

Ausführungen zur Adjazenzmatrix

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.