Eulerkreis in einem gewichteten Graphen |
| 12.07.2018, 19:20 | Lateralus | Auf diesen Beitrag antworten » |
| Eulerkreis in einem gewichteten Graphen Hallo liebe Community, ich stecke momentan bei einer Aufgabe fest, die sich das "Müllabfuhrproblem" nennt: Es ist ein ungerichteter und gewichteter Graph gegeben. Ziel ist es nun die kürzeste Route zu ermitteln. Dabei gelten folgende Bedingungen: - Das "Müllabfuhrauto" startet im Depot und kehrt wieder dort zurück. Start- und Endpunkt sind also identisch. - Jede "Straße" (d.h alle Kanten) müssen abgelaufen werden. Wie kann ich nun diese Route finden? Aus meiner Übung weiß ich, dass ich zunächst den Dijkstra und dann den Hierholzer/Fleury-Algorithmus anwenden muss. Das Vorgehen der Algorithmen ist mir bekannt, ich weiß allerdings nicht wie ich diese richtig einzubetten habe. Zudem gibt es das Problem, dass der Graph kein Eulerkreis ist, da ein Knoten mit ungerader Eckenordnung vorhanden ist (Knoten h). Meine Frage ist nun, wie ich diese Route unter der zu Hilfenahme der Algorithmen herausfinden kann und wie ich mit dem Knoten h umgehen kann. Freundliche Grüße Marco Meine Ideen: Mit dem Dijkstra-Algorithmus habe ich zumindest die Wege mit dem geringsten Gewicht von dem Knoten a (depot) zu den restlichen Knoten herausgefunden. |
||
| 13.07.2018, 10:29 | Huggy | Auf diesen Beitrag antworten » |
| RE: Eulerkreis in einem gewichteten Graphen Da ich mir gern auch mit Sachen beschäftige, von denen ich keine Ahnung habe, habe ich mir den Graphen mal angeschaut. Dabei ist mir aufgefallen, dass neben dem Knoten h auch der Knoten g eine ungerade Ordnung hat. Wenn man den Graphen also durch eine virtuelle Kante zwischen g und h ergänzt, ist eine Eulertour möglich, für deren Auffindung du nach meinem Verständnis einen Algorithmus hast. Jetzt ist diese virtuelle Kante noch durch einen realen Weg zwischen g und h zu ersetzen und das solte der kürzeste Weg zwischen g und h sein. Nach meiner Internetrecherche sollte dies gerade der Dijkstra-Algorithmus leisten. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
