kleiner Übungszettel als "Hausaufgabe"

Aufgabe 1

Die Mannschaft Blau-Weiß Hintertupflingen umfasst n Spieler, während Grün-Gelb Kleinlinsenkirchen N Spieler zählt, wobei n < N. Die Zuschauer sitzen bereits ungeduldig im Stadion, da fällt den Trainern ein, dass sie noch gar nicht festgelegt haben, welche zwei Spieler (aus jeder Mannschaft einer) zu Beginn feierlich die Fahne ins Stadion tragen sollen.
Aus ästhetischen Gründen sollen diese zwei Spieler gleich groß sein (eine Forderung des Sponsors). Die Spieler selbst sitzen noch in wirrer Unordnung in ihren Kabinen.

Gesucht ist eine Vorgehensweise, dieses Zweierpaar gleich großer Spieler zu finden. Da die Zuschauer schon ungeduldig auf Spielbeginn warten, soll dieses Verfahren möglichst schnell beendet sein, das heißt, es sollen möglichst wenig Vergleiche zwischen zwei Spielern stattfinden (und mehr als zwei Spieler können nicht gleichzeitig verglichen werden).

Nachträglicher Hinweis: Der Einfachheit halber dürft ihr davon ausgehen, dass ein solches Zweierpaar mit Sicherheit existiert! Ihr müsst also nicht das Paar suchen, das die ähnlichste Größe hat!

Diese Aufgabe beruht auf Aufgabe Alg2 des "Selbsttest zur Prüfung der Eignung zum Studium der Informatik" der Ludwig-Maximilians-Universität München, wie er unter http://www.pms.informatik.uni-muenchen.de/eignungstest/ veröffentlicht wurde und wird mit freundlicher Genehmigung der Autoren abgedruckt.

Aufgabe 2

Lorenzo hat einen sehr merkwürdigen Bekanntenkreis: Es gibt ziemlich viele Zweierpaare von Personen, die sich gegenseitig nicht leiden können. Begegnen sich zwei von diesen, so ist Streit vorprogrammiert, was Lorenzo auf seiner nächsten Geburtstagsparty natürlich vermeiden möchte.
Aus diesem Grund hat er vor, von einem solchen Zweierpaar höchstens eine Person einzuladen, trotzdem möchte er so viele wie möglich zu seiner Party einladen. Der Einfachheit halber sind Lorenzo alle seine Bekannten gleich sympathisch, so dass es ihm egal ist, wen er nun einlädt, solange es möglichst viele sind.

Mit der Kenntnis, welche Personen sich nicht leiden können, könnte man seinen Bekanntenkreis graphisch veranschaulichen, indem man Personen als Kreise darstellt und zwei Kreise miteinander verbindet, wenn sich diese zwei Personen nicht leiden können.
Ein Beispiel könnte so aussehen:

Uns interessiert nun weniger die Lösung zu Lorenzos konkretem Problem, sondern viel mehr euer Lösungsweg. Wir wollen wissen, warum ihr welche Person ausgewählt habt, und was ihr im folgenden daher beachten müsst.

Wem das zu einfach war, der überlegt sich nun, wie eine gültige Lösung allgemein für jeden beliebigen "Bekanntenkreis"-Graph ermittelt werden kann (in Form eines einfachen Regelwerkes, wann was mit einer Person zu geschehen hat).

Unsere Lösungen haben werden wir am Montag den 18. März demnächst auf unserer Homepage unter http://www.cs.uni-frankfurt.de/fsinf/sit/index.html veröffentlichen.

Bis dahin (und auch noch danach) beantworten wir gerne eure Fragen per Email an fsinf@cs.uni-frankfurt.de. Auch eure Lösungsansätze sehen wir uns gerne an.

Die PDF-Version des Übungszettels gibt es hier zum download.