26. Februar 2017 23:47:48 CET
Hallo,
in der Aufgabe 2.4 wird verlangt ein Programm zu entwickeln, welches einem Ausgibt, ob man jeden Knoten von jeden anderen Knoten, nach den Regeln des Linksabbiegeverbotes, erreichen kann.
Wenn ich mir meine Definition anschaue stelle ich fest, dass man immer einen Knoten von jeden anderen Knoten aus besuchen kann.
Hätte zumindest kein Beispiel, wo das nicht irgendwie über Umwege gehen würde.
Außer der Start und Endpunkt sind überhaupt nicht (auch im Ursprünglichen ungericheten Graphen) miteinander Verbunden.
Würde in diesem Fall eine Art von Beweis ausreichen um Nr 2.4 zu bearbeiten? Immerhin wäre es doch unnötigt ein Programm zu schreiben, dessen Ergebnis von vorhinein bekannt ist.
Wie sollte ein solche Beweis aussehen, bzw. was für eine Art von Beweis sollte es sein?
7. März 2017 08:48:38 CET
Ein formaler Beweis wäre OK, da hier nur nach dem "ob" gefragt wird (eigentlich eine typisch mathematische Fragestellung; Informatiker hätten eigentlich gerne noch für alle Kreuzungspaare die Wege angegeben). Vermutlich müsstest du deine Definition formalisieren können, wohl mit den Mitteln der Graphentheorie.
Möglicherweise ist ein Algorithmus einfacher …
