Gibt es einen Begriff für diese "Descendanz" -untergraphie von gerichteten azyklischen Diagrammen?

Question

Betrachten Sie eine gerichtete azyklische Grafik $ g $ mit vertex-set $ V $ .Wählen Sie einen Scheitelpunkt $ V $ , und lassen Sie $ H $ Seien Sie der Untergraphie, der $ V $ und alle anderen Scheitelpunkte in $ G $ , die von $ V $ erreichbar sind (zusammen mit den zugehörigen gerichteten Kanten).

(mit anderen Worten, wenn wir $ v \ in V $ wählen, interessieren wir uns an der Teilmenge, die aus $ V $ und alle seine Nachkommen).

Gibt es einen akzeptierten Begriff für diese spezielle Teilmenge von Ecken (oder den Untergrafik)?Es scheint ein ziemlich elementares Konzept zu sein, also erwartete ich, dass ich dafür erwartet hatte, einen häufig verwendeten Phrase zu finden, aber meine Suche kommt bisher leer.Vielen Dank für Antworten oder Leads!

Answer 1

Art von. Aber wir werden die übliche Computer-Säkreationsweise verwenden, um dies zu beschreiben, mit der Sprache von binäre Beziehungen .

Sie sind wahrscheinlich bereits mit binären Beziehungen vertraut, wie Gleichheit $= $ , weniger als oder gleich- $ \ le $ , Subset $ \ SubseteQ $ usw. Im Allgemeinen ist ein binärer Relation $ R $ über einen Set $ x $ ist eine Teilmenge $ r \ Subseteq x \ times x $ . Wenn $ (x, y) \ in R $ , bezeichnen wir dies als $ XRY $ .

wenn $ \ fürall x \ in x, xrx $ , dann $ r $ ist reflexiv . Die Beziehungen $= $ und $ \ le $ sind reflexiv, aber $ \ lt $ ist nicht.

wenn $ \ fürall x, y, z \ in x, xry \, \ wedge \, yrz \ rightarrow XRZ $ , dann $ R $ ist transitive . Viele Beziehungen sind transitiv, einschließlich aller oben angegebenen Personen. Wenn $ X \ le y $ und $ y \ le z $ , dann $ x \ le z $ .

Angesichts einer Beziehung $ R $ , der reflexive transitive Verschluss von $ r $ < / span>, gekennzeichnete $ r ^ * $ , ist der kleinste Relation $ r ^ * $ so $ r \ subseteq r ^ * $ , und $ r ^ * $ ist reflexiv und transitiv.

Ihre Grafik als binärer Beziehung zu interpretieren (da die Kanten Ihnen nicht wirklich wichtig sind, sind Sie nur für die Set von Eiter-Set interessiert), so dass Sie möchten: $ XR ^ * y $ Wenn und nur wenn $ y $ ein" Nachkomme "(durch Ihre Bedeutung) von $ x $ .

Wenn Sie auf die Literatur ansehen, müssen Sie ein weiteres Stück der Notation kennen: Der transitive Verschluss von $ R $ , bezeichnet $ r ^ + $ , ist der kleinste Relation $ r ^ + $ so, dass $ r \ subseticq r ^ + $ und $ r ^ + $ ist transitiv. Algorithmen zum Berechnen des transitiven Verschlusses und des reflexiven transitiven Verschlusses sind zusammenhängend, da sie sich nur durch die "diagonalen" Einträge unterscheiden: $ r ^ + \ cup \ link \ {(x, x) \, | \, x \ in x \ rechts \}= r ^ * $ .

Es gibt mehrere Standardalgorithmen zum Berechnen des RTC einer Beziehung. Wenn die Beziehung dicht ist, in dem Sinne, dass es möglich ist, es als Bitmatrix darzustellen, ist der Floyd-Warshall-Algorithmus ist einer der schnellsten praktischen Algorithmen; Die Laufzeit ist $ \ theta (| V | ^ 3) $ theoretisch, aber die innere Schleife ist auf echte Hardware recht schnell, da es ein Bündel von Bit ist Vektormanipulationen.

für spärliche Beziehungen, siehe Esko Nuutilas These , das eine enthält Sehr gute Umfrage sowie einige neuere Algorithmen.