Indirekte Beziehungen abbilden?

[marabu]

Hallo,

ich erkenne hier ein graphentheoretisches Problem. Die "Tabelle" stellt die einzelnen Segmente (Kante mit ihren zwei Knoten, binary relation) des Graphen dar. Der ist ursprünglich ungerichtet. Zur Lösung der Frage "kennt A D?" kann ausgehend von A ein gerichteter Graph aufgebaut werden. Dazu werden alle Paare schrittweise aufgenommen, so wie du es selbst schon formuliert hast. Dazu müssen lediglich alle Paare normiert (deine Beispieldaten sind es schon) werden, dass heißt das geordnete Tupel (D, C) müsste zuerst in (C, D) transformiert werden, bevor es eingebaut werden kann. Sobald ein normiertes Tupel (x, D) gefunden wird ist die transitive Beziehung erwiesen.

Eine Adjazenzmatrix wäre eine äquivalente Darstellung. An die Stelle des Baums (der Bäume, mehrere sind möglich) tritt dann ein Suchalgorithmus mit Backtracking und Kantenmarkierung.

Gute Nacht