Übungen

Aufgabe 1: tratsCH trATsch

"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)

(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.