Durchlaufbarkeit von Graphen

Es gibt in der Graphentheorie zahlreiche Probleme, die sich mit dem Durchlaufen von Graphen befassen. Man unterscheidet Probleme beim Durchlaufen der Kanten von Problemen beim Durchlaufen der Knoten. Im Folgenden werden die wichtigsten Probleme dieser Art kurz vorgestellt.

Eulerkreisproblem

Das Eulerkreisproblem untersucht die Durchlaufbarkeit der Kanten eines Graphen. Gefragt ist hier, ob es einen Zyklus gibt, der alle Kanten des Graphen genau einmal durchläuft. Man stellt fest, dass es notwendig und hinreichend ist, wenn der Graph zusammenhängend ist und alle Knoten geraden Grad besitzen. Diese Eigenschaft lässt sich mittels Tiefensuche leicht in Linearzeit prüfen. Auch das Finden eines solchen Zyklus (sofern er existiert) ist damit mit linearer Laufzeit möglich.

Briefträgerproblem

Das Briefträgerproblem (engl. Chinese Postman Problem), fragt nach einer kürzesten Route über alle Kanten eines kantengewichteten Graphen. Für Graphen, die einen Eulerkreis besitzen, entspricht diese Route offensichtlich einem Eulerkreis. In anderen Graphen müssen notwendigerweise Kanten mehrfach durchlaufen werden. Die Länge dieser Kanten muss minimiert werden. Dazu genügt es eine kleinste perfekte Paarung im Distanzgraphen aller Knoten mit ungeradem Grad zu finden. Dies ist in Polynomialzeit möglich. Entsprechend der Kanten dieser Paarung müssen die zugehörigen Kanten im Originalgraphen vervielfältigt werden. Dadurch entsteht ein Graph, der einen Eulerkreis besitzt. Es genügt nun einen Eulerkreis zu finden.

Hamiltonkreisproblem

Das Hamiltonkreisproblem untersucht die Durchlaufbarkeit der Knoten eines Graphen. Gefragt ist, ob es einen Kreis gibt, der jeden Knoten des Graphen enthält. Das Problem ist NP-vollständig. Es sind einige hinreichende und notwendige Bedingungen für die Existenz eines Hamiltonkreises bekannt, so dass auf einigen Graphen effizient geprüft werden kann, ob sie einen Hamiltonkreis besitzen.

Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (engl. Traveling Salesperson Problem) fragt nach einer kürzesten Rundreise über alle Knoten eines kantengewichteten vollständigen Graphen. Auch dieses Problem ist NP-vollständig. Mit Hilfe einiger vernünftiger Annahmen (Dreiecksungleichung) ist es möglich das Problem wenigstens approximativ zu behandeln.