Dies ist eine alte Version des Dokuments!
Einführung in den Graphentester
Die Froschperspektive
Um entscheiden zu können, ob ein gegebener Graph einen Eulerkreis besitzt oder nicht, müssen wir zwei Kriterien überprüfen:
- Alle Knotengrade müssen gerade sein
- Der Graph muss zusammenhängen
Bei Algorithmen, die auf Graphen operieren, müssen wir einen Perspektivwechsel vornehmen: Wir sehen einen Graphen aus der "Vogelperspektive", d.h. wir nehmen den gesamten Graphen mit all seinen Knoten und Kanten wahr und lassen dann nur unsere Augen wandern - wenn uns eine Information fehlt, schauen wir einfach an die entscheidende Stelle und das Problem ist gelöst.
Wenn wir einen Graphen algorithmisch verarbeiten wollen, müssen wir schrittweise durch die Knotenanordnung wandern - wir sehen niemals weiter als bis zum Ende der nächsten Kante. Wir müssen also die Frosch-Perspektive einnehmen.