Eulertouren Vokabeln

Aufrufe: 35     Aktiv: 04.02.2021 um 08:58

0
Ich verstehe nicht was mit folgenden Aufgabenstellungen gemeint ist:
(gezeigt werden verschieden Graphen ohne Richtungen bei den verbindenden Kanten)

"Bestimmen Sie die lexikographisch kleinste Eulertour mit Anfangspunkt 5 im folgenden schlichten Graphen."
-Was bedeutet lexikographisch in diesem Zusammenhang? Was bedeutet kleinste Eulertour? Wieso nicht Eulerzug? Ich verstehe die Bedeutung von all diesen Wörtern leider nicht und stundenlanges googlen hilft mir bislang auch nicht weiter.


Weitere Aufgaben:
"Besitzt der folgende Graph einen Eulerzug?"
-Woher weiß ich ob ein Graph einen Eulerzug oder eine Eulertour hat?

"Bestimmen Sie den lexikographisch größten Eulerzug im folgenden schlichten Graphen."
-In wie weit kann ein Eulerzug größer sein als ein anderer und wie bestimmt man den größten statt dem kleinsten? Und wann ist ein Graph bitte "schlicht"?

Eulertour vs Eulerzug: Unterschied unklar.

"Satz. Jeder Graph, der h ̈ochstens eine nicht-triviale Komponente besitzt (z.B. ein zusammenh ̈angender Graph) und genau zwei Knoten u, v mit ungeradem Grad, besitzt auch einen u-v-Eulerzug."
- Was ist bitte eine nicht triviale Komponente?

Kennt jemand die Bedeutungen von diesen Vokabeln und kann diese bitte erklären, sodass ich weiß was ich bei den Aufgaben machen muss?
Diese Frage melden
gefragt

Student, Punkte: 10

 

Kommentar schreiben

1 Antwort
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.
Allerdings sollte das alles auch in deiner Vorlesung definiert worden sein, schau da also auch nochmal nach.
Diese Antwort melden
geantwortet

Punkte: 5.3K
 

Kommentar schreiben