Graphentheorie

Graphentheorie Definition

Die Graphentheorie bzw. Graphen helfen, Optimierungsprobleme des Operations Research abstrakt zu modellieren.

Ein Graph umfasst Knoten (auch als Ecken bezeichnet, zum Beispiel Städte) und Kanten (Linien), die die Knoten verbinden können (zum Beispiel die Luftlinien oder Straßenverbindungen zwischen jeweils zwei Städten). Die Kanten erhalten oft noch Gewichte bzw. Bewertungen, beispielsweise die Streckenlänge in km, die Reisezeit in Stunden oder die Reisekosten in €.

Man könnte die Knoten und Kanten zeichnen und mit den Gewichten / Bewertungen beschriften, das Problem wäre dadurch vollständig beschrieben (Computer und Algorithmen bevorzugen allerdings eine Darstellung in Matrix- bzw. Tabellenform (vergleiche Adjazenzmatrix ohne Gewichtung) oder in Mengenschreibweise).

Graphen werden oft kurz so dargestellt:

G = (V, E)

Dabei steht G für Graph, V für Vertices (englisch für Knoten) und E für Edges (englisch für Ecken bzw. Kanten).

Wenn man dann einen Graphen mit 3 Knoten A, B, und C beschreiben möchte, von denen (ungerichtet) A mit B und B mit C verbunden ist, kann man das so angeben:

V = {A, B, C}

E = {{A, B}, {B, C}}

Das Optimierungsproblem könnte etwa sein, die kürzeste, schnellste oder günstigste Tour für fünf bestimmte Städte zu finden.

Gerichtete Graphen vs. ungerichtete Graphen

Bei gerichteten Graphen (auch Digraph genannt, von Directed Graph) sind die Kanten wie Pfeile ("Einbahnstraßen"), bei ungerichteten Graphen sind die Kanten wie Linien ("Straßen") zu verstehen.

Ein gemischter Graph enthält beides.

Schleife / Schlinge

Eine Schleife / Schlinge ist eine Kante, deren Anfangs- und Endknoten identisch ist, mit anderen Worten: ein Knoten A wird durch eine Schleife mit sich selbst verbunden.

Parallele Kanten

Parallele Kanten haben denselben Anfangs- und Endknoten.

Einfacher Graph

Ein sogenannter einfacher Graph liegt vor, wenn er keine parallelen Kanten und keine Schleifen / Schlingen hat.

Zusammenhängender Graph

Ein zusammenhängender Graph liegt vor, wenn jedes beliebige Paar von Knoten durch Kanten direkt (zum Beispiel A - C) oder indirekt mit "Zwischenstationen" (zum Beispiel A - B - C) miteinander verbunden ist.

Vollständiger Graph

Ein vollständiger Graph liegt vor, wenn ein ungerichteter Graph alle möglichen Kanten hat; mit anderen Worten: alle Knoten sind mit allen anderen Knoten direkt verbunden.

Alternative Begriffe: Graphen-Theorie.