Gibt es einen Begriff für diese "Descendanz" -untergraphie von gerichteten azyklischen Diagrammen?
Frage
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!
Lösung
Art von. Aber wir werden die übliche Computer-Säkreationsweise verwenden, um dies zu beschreiben, mit der Sprache von binäre Beziehungen .
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.