Routenplanung

Ein klassisches Problem der Graphentheorie ist Eulersche Pfadproblem: Bestimme einen Pfad oder Kreis durch den Graphen, der jede Kante genau einmal benutzt. Eine erste Formulierung dieser Fragestellung ist als Königsberger Brückenproblem bekannt: ‘Der Fluss Pregel trennt die Stadt Königsberg (heute Kaliningrad) in fünf Teile die durch sieben Brücken miteinander verbunden sind. Gibt es einen Rundweg durch Königsberg, bei dem man jede Brücke genau einmal überquert?’

Beim verwandten Chinese Postman-Problem geht es darum, einen möglichst kurzen Weg in einem Graphen zu finden, der jede Kante (gerichtet oder ungerichtet) mindestens einmal verwendet und dann zum Ausgangspunkt zurückkehrt. Dieses Problem ist etwa für einen Postboten wichtig, der Briefe in einer Stadt austrägt und daher jede Straße entlanglaufen muss. Das Problem des Handlungsreisenden zielt darauf ab, eine möglichst kurze Rundreise durch alle Knoten eines Graphen zu finden.