Durchlaufbarkeit von Graphen
Es gibt in der
Graphentheorie zahlreiche Probleme, die sich mit dem
Durchlaufen von Graphen befassen. Man unterscheidet in Probleme, die sich einerseits mit dem Durchlaufen der
Kanten, andererseits mit dem Durchlaufen der
Knoten befassen. 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.
Wir Mathematiker sind die wahren Dichter, nur müssen wir das, was unsere Phantasie schafft, noch beweisen.
Leopold Kronecker
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld
• Dοrfplatz 25 • 17237 Blankеnsее
• Tel.: 01734332309 (Vodafone/D2) •
Email: cο@maτhepedιa.dе