WikiDer > Transitive Schließung

Das Transitive Schließung (Niederlande) oder Transitive Schließung (Flandern) ${displaystyle R^{ }}$ von a binäre Beziehung${Anzeigestil R}$ auf einen Sammlung${Anzeigestil M}$ ist die kleinste transitiv Beziehung an ${Anzeigestil M}$ die ursprüngliche Beziehung umfasst.

Dies bedeutet, dass für zwei Elemente ${Anzeigestil x}$ und ${displaystyle y}$ von ${Anzeigestil M}$ zählt das ${Anzeigestil x R^{ } y}$ existiert nur, wenn eine Reihe von Elementen vorhanden ist ${Displaystil x_{0},x_{1},Punkte x_{n}}$ existiert wo:${displaystyle x_{0}=x}$,${displaystyle x_{n}=y}$ und ${displaystyle x_{i} R x_{i 1}}$ vor dem ${displaystyle 0leq i$.

Jede binäre Beziehung hat einen transitiven Abschluss.

Stellt man die Beziehungen als a gerichteter Graph, enthält den Graphen des transitiven Abschlusses ${displaystyle R^{ }}$ ein Knotenbogen X knoten ja als Zählung von ${Anzeigestil R}$ enthält einen gerichteten Pfad mit einem oder mehreren Bögen von X zu ja. Der transitive Abschluss eines gerichteten, azyklischen Graphen ist der "Erreichbarkeitsgraph", der anzeigt, welche Knoten von anderen Knoten aus erreichbar sind. Es ist ein strikte Teilordnung über die Sammlung von Knöpfen.

Beispiele

In diesem Beispiel wird die ursprüngliche Beziehung durch ausgefüllte Pfeile dargestellt. Die gestrichelten Pfeile werden dem transitiven Abschluss hinzugefügt.

• In einer Ansammlung von Menschen kann man die Beziehung als "Vater von" betrachten. Dazu können zum Beispiel gehören:
  • A ist Vater von B
  • B ist Vater von C
  • C ist Vater von D und E

Der transitive Abschluss dieser Relation „ist Vater von“ kann als „ist männlicher Vorfahre von“ oder „ist Vorfahre von“ bezeichnet werden. Zusätzlich zu den bereits erwähnten Verbindungen enthält es auch Folgendes: A ist Vorfahre von C, D und E; B ist Vorfahre von D und E.

• Die Relation "ist der Chef von" in einer Organisation hat als transitiven Abschluss die Relation "ist ein hierarchischer Vorgesetzter von".

• Das Streckennetz einer Fluggesellschaft verbindet die Städte, zwischen denen ein Direktflug besteht. Diese transitive Sperrung verbindet diejenigen Städte, zwischen denen man mit einem oder mehreren Anschlussflügen fliegen kann.

• In der Sammlung von natürliche Zahlen ist der transitive Abschluss der Beziehung ${displaystyle a,R,b:Longleftrightarrow a=b 1}$ ("a folgt b") die Relation "ist größer als".

Berechnung des transitiven Abschlusses

Der transitive Abschluss einer Relation oder eines Graphen kann mit dem Warshall-Algorithmus bestimmt werden, der ein Spezialfall des Floyd-Warshall-Algorithmus. Dieser Algorithmus bestimmt den kürzesten Abstand zwischen allen Knotenpaaren in einem gewichteten gerichteten Graphen mit a dynamische Programmiermethode. Im Algorithmus von Warshall betrachtet man einen ungewichteten gerichteten Graphen; man kann auch sagen, dass alle Bögen ein Gewicht von 1 haben. Man arbeitet dann mit der binärBogenmatrix; anstatt Entfernungen zu addieren verwendet man die logische Konjunktion UND und statt des minimalen de logische Disjunktion ODER.

Anwendung

„Barrierefreiheit“ ist ein wichtiger Begriff bei der Befragung Datenbanken, die ein Netzwerk darstellen, das hierarchisch sein kann oder nicht, zum Beispiel a Ontologie, ein Soziales Netzwerk, ein Zitationsindex von wissenschaftlichen Publikationen oder eine Datenbank mit Hyperlinks von dem Weltweites Netz. Das Konzept der transitiven Schließung ist hierfür ein nützliches Werkzeug.

Transitive Reduktion

Das transitive Reduktion ist das Gegenteil des transitiven Abschlusses. Die transitive Reduktion einer binären Relation ${Anzeigestil R}$ ist die kleinste Relation mit dem gleichen transitiven Abschluss wie ${Anzeigestil R}$.

Es gibt Beziehungen, für die es keine transitive Reduktion gibt. Es gibt auch Relationen, für die es mehrere transitive Reduktionen gibt. Wenn der Graph der Relation jedoch ein gerichteter, azyklischer Graph ist, gibt es immer eine eindeutige transitive Reduktion.