(Twitter)
0
Klären wir also erstmal alle Vokabeln:
- Allgemeines zu Graphen: Ein Graph ist eine Menge von Knoten und Kanten, eine Kante verbindet zwei Knoten. Ein Graph heißt schlicht, wenn keine zwei verschiedenen Knoten durch zwei Kanten ("Doppelkante") verbunden bzw. kein Knoten durch eine Kante mit sich selbst verbunden ("Schleife") ist. Ein Zug/Weg/Pfad ist eine Reihe von Kanten, sodass zwei aufeinanderfolgende Kanten immer einen gemeinsamen Knoten teilen. Ein Graph heißt zusammenhängend, wenn es einen Weg von jedem Knoten zu jedem anderen gibt. Ist ein Graph nicht zusammenhängend, spricht man von mehreren Zusammenhangskomponenten, das sind die einzelnen zusammenhängenden Teilgraphen. Der Grad eines Knotens ist die Anzahl der Kanten, die von ihm ausgehen.
- Zu Eulerwegen: Ein \(u\)-\(v\)-Eulerweg/-pfad/-tour ist ein Weg/Pfad/Zug von \(u\) nach \(v\), der jede Kante genau einmal enthält, denk ans Haus vom Nikolaus. Eine Eultertour/Eulerrundweg ist ein Eulerweg mit gleichem End- wie Anfangspunkt. Du hast den Satz richtig zitiert: Wenn der Graph zusammenhängend ist oder alle bis auf eine Zusammenhangskomponente nur aus einem Knoten und keiner Kante bestehen (das ist vermutlich mit den trivialen Komponenten gemeint), dann hat der Graph genau dann einen Eulerweg von \(u\) nach \(v\), wenn \(u\),\(v\) die einzigen Knoten mit ungeradem Grad sind. Gibt es keine Knoten mit ungeradem Grad, dann gibt es eine Eulertour.
- Zu Ordnungen: Die Lexographische Ordnung ist die Reihenfolge, in der Wörter in einem Wörterbuch stehen würden, alphabetisch sortiert. Ich gehe mal davon aus, dass die Knoten in deinem Graphen mit Buchstaben oder Zahlen beschriftet sind. Dann sollst du den Eulerweg/Eulertour finden, die im Wörterbuch als erstes/als letztes kommen würde. Versuch mal selbst zu überlegen, wie du diesen finden könntest.
Diese Antwort melden
Link
geantwortet
stal
Punkte: 11.27K
Punkte: 11.27K