https://demowiki.knowlus.com/index.php?action=history&feed=atom&title=Durchlaufbarkeit_von_Graphen 2026-04-07T21:29:37Z Versionsgeschichte dieser Seite in Demo Wiki MediaWiki 1.44.2 https://demowiki.knowlus.com/index.php?title=Durchlaufbarkeit_von_Graphen&diff=10712&oldid=prev 2025-03-11T11:59:42Z

<p><span class="autocomment">growthexperiments-addlink-summary-summary:1|1|0</span></p> <p><b>Neue Seite</b></p><div>{{Belege fehlen}}<br /> Es gibt in der [[Graphentheorie]] zahlreiche Probleme, die sich mit dem &#039;&#039;&#039;Durchlaufen von [[Graph (Graphentheorie)|Graph]]en&#039;&#039;&#039; befassen. Man unterscheidet Probleme beim Durchlaufen der [[Kante (Graphentheorie)|Kanten]] von Problemen beim Durchlaufen der [[Knoten (Graphentheorie)|Knoten]]. Im Folgenden werden die wichtigsten Probleme dieser Art kurz vorgestellt.<br /> <br /> == Eulerkreisproblem ==<br /> {{Hauptartikel|Eulerkreisproblem}}<br /> Das Eulerkreisproblem untersucht die Durchlaufbarkeit der Kanten eines Graphen. Gefragt ist hier, ob es einen [[Zyklus (Graphentheorie)|Zyklus]] gibt, der alle Kanten des Graphen genau einmal durchläuft. Man stellt fest, dass es notwendig und hinreichend ist, wenn der Graph [[Zusammenhängender Graph|zusammenhängend]] ist und alle Knoten geraden [[Grad (Graphentheorie)|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.<br /> <br /> == Briefträgerproblem ==<br /> {{Hauptartikel|Briefträgerproblem}}<br /> Das Briefträgerproblem (engl. &#039;&#039;Chinese Postman Problem&#039;&#039;), fragt nach einer kürzesten Route über alle Kanten eines [[Kantengewichteter Graph|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 [[Matching (Graphentheorie)|perfekte Paarung]] im [[Distanzgraph]]en 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.<br /> <br /> == Hamiltonkreisproblem ==<br /> {{Hauptartikel|Hamiltonkreisproblem}}<br /> Das Hamiltonkreisproblem untersucht die Durchlaufbarkeit der Knoten eines Graphen. Gefragt ist, ob es einen [[Kreis (Graphentheorie)|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.<br /> <br /> == Problem des Handlungsreisenden ==<br /> {{Hauptartikel|Problem des Handlungsreisenden}}<br /> Das Problem des Handlungsreisenden (engl. &#039;&#039;Traveling Salesperson Problem&#039;&#039;) fragt nach einer kürzesten Rundreise über alle Knoten eines kantengewichteten [[Vollständiger Graph|vollständigen]] Graphen. Auch dieses Problem ist NP-vollständig. Mit Hilfe einiger vernünftiger Annahmen ([[Dreiecksungleichung]]) ist es möglich das Problem wenigstens [[Approximationsalgorithmus|approximativ]] zu behandeln.<br /> <br /> [[Kategorie:Graphentheorie]]</div>

imported>Jule Glühwurm