Dörfer im Gebirge

Einige Dörfer in den Bergen sind über ein Straßennetz zu erreichen. Eine Hauptstraße führt zum ersten Dorf des Tales. Nach einem Unwetter sind einige Dörfer aber nicht mehr erreichbar und melden SOS.

Daraus lässt sich auf den Zustand der Straßen schließen. Es gibt drei Möglichkeiten:

1 = Die Straße ist nicht befahrbar

2 = Die Straße ist befahrbar

3 = Ohne weitere Information ist nicht entscheidbar, ob sie befahrbar oder nicht

befahrbar ist

Die Hauptstraße ist immer befahrbar. Unten ist das Straßennetz abgebildet. Die Hauptstraße führt zu Dorf A ganz links oben.

Gib für jede andere Straße ihren Zustand an.

Mit Hilfe des folgenden Algorithmus kann man den Zustand der Straßen automatisch er- mitteln:

Setze alle Straßen auf "nicht entscheidbar".

Kennzeichne alle Straßen von einem unerreichbaren Dorf zu einem erreichbaren Dorf als "nicht befahrbar".

Für jede Straße S zwischen zwei erreichbaren Dörfern:

Markiere S als "nicht befahrbar".

Bestimme die Anzahl der Dörfer, die von Dorf A aus über "befahrbare" oder "nicht entscheidbare" Straßen erreichbar sind (inklusive A selbst).

Stimmt die Anzahl mit der Anzahl der Dörfer ohne "SOS" überein, setze S auf "nicht entscheidbar". Andernfalls setze S auf "befahrbar".