Existe-t-il un terme pour ces sous-graphiques "descendance" des graphiques acycliques dirigés?
Question
Considérez un graphique acyclique dirigé $ G $ avec sommet Vertex $ V $ .Choisissez un sommet $ V $ et laissez $ h $ être le sous-graphique contenant $ V $ et tous les autres sommets de $ g $ accessible de $ v (avec les bords dirigés associés).
(En d'autres termes, si nous choisissons $ v \ in v $ , nous sommes intéressés par le sous-ensemble composé de $ V $ et tous ses descendants).
Y a-t-il un terme accepté pour ce sous-ensemble particulier de sommets (ou le sous-graphique)?Cela semble être un concept assez élémentaire, donc je m'attendais à trouver une phrase couramment utilisée pour cela, mais ma recherche est vide jusqu'à présent.Merci pour toutes les réponses ou les prospects!
La solution
genre de. Mais nous allons utiliser la reconnaissance informatique habituelle de la décrire, en utilisant la langue de Relations binaires .
Il existe plusieurs algorithmes standard pour calculer le RTC d'une relation. Si la relation est dense, dans le sens où il est réalisable de le représenter comme une matrice de morve, le Algorithme Floyd-Warshall est l'un des algorithmes pratiques les plus rapides; son heure d'exécution est $ \ theta (| v | ^ 3) $ en théorie, mais la boucle interne est assez rapide sur le matériel réel étant donné qu'il s'agit d'un tas de bits manipulations de vecteur.
Pour les relations clairsemes, voir Thèse esko Nuutila , qui contient un Très bonne enquête ainsi que des algorithmes plus récents.