Durchlaufbarkeit von Graphen - LinkFang.de





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

Hauptartikel: 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

Hauptartikel: 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

Hauptartikel: 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 für einige 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.


Kategorien: Graphentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Durchlaufbarkeit von Graphen (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.