Ein Graphenproblem

Komplizierte Beziehungen

"Die Leute vom Planeten Chator schreiben gern Schlechtes übereinander. Wer vielen über andere Schlechtes schreibt, gilt als besonders charmant. Aber natürlich nur, wenn die Kompromittierten nichts davon erfahren. Chatonen schreiben nur an Leute, die ihnen sympathisch sind. Doch die können den Tratsch weitertragen, und eventuell genau an den Falschen. Ein Chatone muss also gut aufpassen, dass er keinen Charmefehler macht. Dieses Missgeschick passierte unlängst Ator, als er Btor Schlechtes über Dtor schrieb. Zu dumm: Dtor ist dem Ctor sympathisch, der wiederum Btor sympathisch ist. Und so landete der Tratsch bei Dtor, der über Ator verständlicherweise sehr verärgert war. Dies hätte Ator mit ein wenig Übersicht vermeiden können, denn schließlich wissen alle Chatonen voneinander, wer wem sympathisch ist." (Quelle: Bundeswettbewerb Informatik 2004/2005 - 1. Runde)

Aufgabe 1

(a) Stelle die Sympathiebeziehungen der Chatonen mit einem gerichteten Graphen dar.

(b) Welches Problem muss hier gelöst werden. Beschreibe es mit Hilfe der Graphenterminologie.

Problem: Suche nach Wegen in Graphen

Ein häufig zu lösendes Graphenproblem besteht darin, in einem gegebenen Graphen einen Weg von einem Startknoten zu einem Zielknoten zu suchen.

Beim vorliegenden (gerichteten) Graphen könnte beispielsweise gefragt werden, ob es einen Weg (längs der Kanten des Graphen) vom Startknoten A zum Zielknoten D gibt.

Aufgabe 2

(a) Von welchen Startknoten zu welchen Zielknoten gibt es (k)einen Weg?

(b) Das Wegesuchproblem hast du vermutlich mit Überblick und Ausprobieren gelöst. Hast du eine Idee, wie man die Suche nach Wegen automatisiert durchführen könnte?