Manfred Börgens - Problem 67 - Übersicht
Äquivalenzliste zu Problem 67
Transitive Relationen ↔ Tripeldarstellung
Zunächst löst man die 9 Graphen aus Frage 3 weiter auf, indem man aus den grünen Knoten weiße oder schwarze Knoten macht. Dadurch entsteht eine vollständige Liste von 39 verschiedenen Typen transitiver Relationen. Die 39 Graphen sind unten alle aufgeführt. Allerdings ist dabei offen, wie die Elemente a, b, c den drei Knoten zugeordnet sind. Es reicht offenbar aus, eine bestimmte Zuordnung zu wählen, da sich alle anderen Zuordnungen durch eine entsprechende Vertauschung der Positionen im Code ergeben. Die Äquivalenzliste arbeitet mit der folgenden Zuordnung:
(*)
Da a, b, c auch anders angeordnet werden können, steht unter den Graphen jeweils die Anzahl der Möglichkeiten für diese Anordnungen. Rechts neben den Graphen stehen die zugehörigen Codes für die Anordnung in (*) und ihre Anzahl. Addiert man die Produkte der beiden Anzahlen über alle 39 Graphen, so erhält man insgesamt 512 verschiedene Codes. Dies sollte nicht verwechselt werden mit den 512 Relationen aus Frage 1. Dass es 512 verschiedene Codes gibt (entsprechend 512 verschiedenen Schachteldarstellungen), ist einfach zu begründen: An 9 Positionen im Code kann eine 0 oder eine 1 stehen, also gibt es 29 Möglichkeiten dafür.
Manfred Börgens - Problem 67 - Übersicht
Publiziert 2009-06-13 Stand 2008-09-28
zurück zur Lösung
zur Leitseite