In der Mathematik ist der transitive Verschluss einer binären Beziehung R auf einem Satz X die transitive Beziehung R auf dem Satz X solch, dass R R enthält und R (Lidl und Pilz 1998:337) minimal ist. Wenn die binäre Beziehung selbst transitiv ist, dann besteht der transitive Verschluss dass dieselbe binäre Beziehung darin; sonst ist der transitive Verschluss eine verschiedene Beziehung. Zum Beispiel, wenn X eine Reihe von Flughäfen ist und x R y bedeutet, dass "es einen direkten Flug vom Flughafen x zum Flughafen y gibt" dann ist der transitive Verschluss von R auf X die Beziehung R: "Es ist möglich, von x bis y in einem oder mehr Flügen zu fliegen."

Transitive Beziehungen und Beispiele

Eine Beziehung R auf einem Satz X ist wenn, für den ganzen x, y, z in X, wann auch immer x R y und y R z dann x R z transitiv. Beispiele von transitiven Beziehungen schließen die Gleichheitsbeziehung auf jedem Satz, "weniger ein als oder gleiche" Beziehung auf jedem geradlinig bestellten Satz, und die Beziehung "x ist vorher y" auf dem Satz aller Leute geboren gewesen. Symbolisch kann das als angezeigt werden: wenn x

und, für,

:

Jeder Satz in diesem Aufbau nimmt die Beziehung vom vorherigen Satz, und fügt irgendwelche neuen Elemente hinzu, die notwendig sind, um Ketten zu machen, die "ein Schritt" mehr transitiv sind. Die Beziehung R wird durch die Einnahme von ganzem zusammen gemacht, den wir als schreiben

:

Um zu zeigen, dass R der transitive Verschluss von R ist, müssen wir zeigen, dass es R enthält, dass es transitiv ist, und dass es der kleinste Satz mit beiden jener Eigenschaften ist.

• : enthält ganzen, also insbesondere enthält.

ist

• transitiv: Jedes Element dessen ist in einem, so muss durch das folgende Denken transitiv sein: wenn und, dann vom associativity der Zusammensetzung, (und so in) wegen der Definition dessen.

ist

• minimal: Lassen Sie, jede transitive Beziehung zu sein, die enthält, wir wollen das zeigen. Es ist genügend, das für jeden zu zeigen. So, seitdem enthält. Und seitdem ist transitiv, wann auch immer, gemäß dem Aufbau, und was es bedeutet, transitiv zu sein. Deshalb, durch die Induktion, enthält jeden, und so auch.

Gebrauch

Bemerken Sie, dass die Vereinigung von zwei transitiven Beziehungen nicht transitiv zu sein braucht. Um transitivity zu bewahren, muss man den transitiven Verschluss nehmen. Das kommt zum Beispiel vor, wenn es die Vereinigung von zwei Gleichwertigkeitsbeziehungen oder zwei Vorordnungen nimmt. Um eine neue Gleichwertigkeitsbeziehung zu erhalten oder zu vorbestellen, muss man den transitiven Verschluss nehmen (reflexivity, und Symmetrie - im Fall von Gleichwertigkeitsbeziehungen - sind automatisch).

Der transitive Verschluss eines geleiteten acyclic Graphen oder DAG ist die reachability Beziehung des DAG und einer strengen teilweisen Ordnung.

Graph-Theorie

In der Informatik kann vom Konzept des transitiven Verschlusses als das Konstruieren einer Datenstruktur gedacht werden, die es möglich macht, auf reachability Fragen zu antworten. D. h. kann man vom Knoten zum Knoten d in einem oder mehr Sprüngen kommen? Eine binäre Beziehung sagt Ihnen nur, dass Knoten verbunden zum Knoten b zu sein, und dass Knoten b mit dem Knoten c usw. verbunden wird. Nachdem der transitive Verschluss, wie gezeichnet, in der folgenden Zahl gebaut wird, in einem O (1) Operation kann man beschließen, dass Knoten d vom Knoten a erreichbar ist. Die Datenstruktur wird normalerweise als eine Matrix so versorgt, wenn Matrix [1] [4] = 1, dann ist es der Fall, dass Knoten 1 Knoten 4 durch einen oder mehr Sprünge erreichen kann.

Beziehung zur Kompliziertheit

In der rechenbetonten Kompliziertheitstheorie die Kompliziertheitsklasse entspricht NL genau zum Satz von logischen Sätzen expressible das Verwenden der Logik der ersten Ordnung zusammen mit dem transitiven Verschluss. Das ist, weil das transitive Verschluss-Eigentum eine nahe Beziehung mit dem NL-complete Problem STCON hat, um geleitete Pfade in einem Graphen zu finden. Ähnlich ist die Klasse L Logik der ersten Ordnung mit dem auswechselbaren, transitiven Verschluss. Wenn transitiver Verschluss zur Logik der zweiten Ordnung statt dessen hinzugefügt wird, erhalten wir PSPACE.

Algorithmen

Effiziente Algorithmen, für den transitiven Verschluss eines Graphen zu schätzen, können hier gefunden werden. Die einfachste Technik ist wahrscheinlich der Algorithmus von Floyd-Warshall. Die schnellsten Grenzfall-Methoden, die nicht praktisch sind, reduzieren das Problem auf die Matrixmultiplikation.

Siehe auch

• Die transitive Verminderung (eine kleinste Beziehung, die den transitiven Verschluss von R als sein transitiver Verschluss hat)
• Symmetrischer Verschluss
• Reflexiver Verschluss
• Erbbeziehung
• Lidl, R. und Pilz, G., 1998, Angewandte abstrakte Algebra, 2. Ausgabe, Studententexte in der Mathematik, dem Springer, der internationalen Standardbuchnummer 0-387-98290-6
• Keller, U., 2004, Einige Bemerkungen auf Definability des Transitiven Verschlusses in First-order Logic und Datalog

Außenverbindungen

• "Transitiver Verschluss und die Verminderung", Das Steinige Bach-Algorithmus-Behältnis, Steven Skiena.