Benutzer:DixMartin/Graphalgorithmen

Betrachteter Gegenstand

→ Hauptartikel: Graph (Graphentheorie)

In der Graphentheorie bezeichnet ein Graph eine Menge von Knoten (auch Ecken oder Punkte genannt) zusammen mit einer Menge von Kanten. Eine Kante ist hierbei eine Menge von genau zwei Knoten. Eine Kante gibt an, ob zwei Knoten miteinander in Beziehung stehen, bzw. ob sie in der bildlichen Darstellung des Graphen verbunden sind. Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent. Wenn die Kanten statt durch Mengen durch geordnete Paare von Knoten angegeben sind, spricht man von gerichteten Graphen. In diesem Falle unterscheidet man zwischen der Kante (a,b) – als Kante von Knoten a zu Knoten b – und der Kante (b,a) – als Kante von Knoten b zu Knoten a. Knoten und Kanten können auch mit Farben (formal mit natürlichen Zahlen) oder Gewichten (d. h. rationalen oder reellen Zahlen) versehen werden. Man spricht dann von knoten- bzw. kantengefärbten oder -gewichteten Graphen.

Komplexere Graphentypen sind:

Multigraphen, bei denen die Kantenmenge eine Multimenge ist
Hypergraphen, bei denen eine Kante eine beliebig große Menge von Knoten darstellt (man spricht in diesem Falle auch von Hyperkanten)
Petri-Netze mit zwei Arten von Knoten

Ist die Menge der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen.

Graphen als Datenstruktur

Graphen lassen sich insbesondere mit folgenden Datenstrukturen als Datenstruktur repräsentieren:

Grapheneigenschaften

Graphen können verschiedene Eigenschaften haben. So kann ein Graph

zusammenhängend (im allgemeinen k-zusammenhängend)
bipartit, (im allgemeinen k-partit)
planar,
eulersch oder hamiltonisch sein.

Es kann nach der Existenz spezieller Teilgraphen oder Minoren gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Bogenzusammenhangszahl, chromatische Zahl, Stabilitätszahl oder Cliquenzahl. Zwei Graphen können isomorph (strukturell gleich) oder automorph zueinander sein.

Wenn ein Knoten besonders ausgezeichnet ist, spricht man von einer Wurzel bzw. einm gewurzeltem Graphen.

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

Graphenklassen

Grundsätzlich werden Graphen in gerichtete und ungerichtete Graphen unterteilt.

azyklische Graphen: Weg, Pfad, Wald, Baum
zyklische Graphen: Zyklus, Kreis, Vollständige Graphen

Aufgrund des Vorhandenseins bestimmter Eigenschaften lassen sich weitere Graphenklassen unterscheiden wie

Bipartite Graphen
Planare Graphen

Grundlegende Begriffe und Probleme

Die Graphentheorie definiert eine Vielzahl von grundlegenden Begriffen sehr intuitiv einleuchtend:

Weitere grundlegende Begriffe sind:

Graphen können verschiedene Eigenschaften haben. So kann ein Graph zusammenhängend, bipartit, planar, 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, Bogenzusammenhangszahl, chromatische Zahl, Stabilitätszahl oder Cliquenzahl.

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

Einige der aufgezählten Grapheneigenschaften sind relativ schnell algorithmisch bestimmbar, etwa wenn der Aufwand höchstens mit dem Quadrat der Größe der Graphen wächst. Andere Eigenschaften praktisch angewandter Graphen sind innerhalb der Lebensdauer heutiger Computer nicht exakt zu bestimmen. Allerdings kann in diesen Fällen der Einsatz von heuristischen Verfahren zu sinnvollen Näherungslösungen führen.

Probleme

Die wichtigsten Probleme und Ergebnisse der Graphentheorie werden in folgenden Artikeln dargestellt:

Algorithmen