Graphentheorie

Graphentheorie Definition

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

Ein Graph umfasst Knoten (auch als Ecken bezeichnet, z. B. Städte) und Kanten (Linien), die die Knoten verbinden können (z. B. die Luftlinien oder Straßenverbindungen zwischen jeweils zwei Städten). Die Kanten erhalten oft noch Gewichte bzw. Bewertungen, z. B. 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 (vgl. 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 z. B. sein, die kürzeste, schnellste oder günstigste Tour für fünf bestimmte Städte zu finden.

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.

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 haben denselben Anfangs- und Endknoten.

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

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

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

Alternative Begriffe: Graphen-Theorie.