Graphentheorie

Graphentheorie Definition

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

Ein Graph umfasst Knoten (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 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 z.B. der Streckenlängen in km in Matrix- bzw. Tabellenform).

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