C'è un termine per questi sottogruppi "discendenti" di grafici aciclici diretti?

Question

Considera un grafico acyclico diretto $ G $ con set vertice $ V $ .Scegli un vertice $ V $ e lascia che $ h $ essere il sottografo contenente $ V $ e tutti gli altri vertici in $ G $ che sono raggiungibili da $ V $ (insieme ai bordi diretti associati).

(in altre parole, se scegliamo $ v \ in V $ , quindi siamo interessati al sottoinsieme composto da $ V $ e tutti i suoi discendenti).

Esiste un termine accettato per questo particolare sottoinsieme di vertici (o il sottogramma)?Sembra essere un concetto abbastanza elementare, quindi mi aspettavo di trovare una frase comunemente usata per questo, ma la mia ricerca sta arrivando vuota finora.Grazie per tutte le risposte o lead!

Answer 1

tipo di. Ma useremo il solito modo di compendire computer per descriverlo, usando la lingua di relazioni binarie .

Probabilmente hai già familiarità con le relazioni binarie, come l'uguaglianza $= $ , meno-che-o-uguale a $ \ le $ , sottoinsiem $ \ SOTETEQ $ , e così via. In generale, una relazione binaria $ R $ su un set $ x $ è un sottoinsieme $ R \ SOTETETQ X \ TIMES x $ . Se $ (x, y) \ in R $ , indichiamo questo come $ xry $ . .

se $ \ forlt x \ in x, xrx $ , quindi $ r $ è Riflesso . Le relazioni $= $ e $ \ le $ sono riflessivi, ma $ \ lt $ non è.

Se $ \ forlt x, y, z \ in x, xry \, \ wedge \, yrz \ raddrow xrz $ , quindi $ R $ è transitivo . Un sacco di relazioni sono transitivi, compresi tutte quelle sopra riportate. Se $ x \ le y $ e $ y \ le z $ , quindi $ x \ le z $ .

Data una relazione $ R $ , la chiusura transitiva del reflexive di $ R $ < / span>, denotato $ r ^ * $ , è la relazione più piccola $ r ^ * $ tale $ R \ SOTETETQ R ^ * $ e $ R ^ * $ è riflessivo e transitivo. .

Interpretazione del grafico come una relazione binaria (dal momento che i bordi non sembrano davvero importanti, sei interessato solo al set di vertici), questo è esattamente quello che vuoi: $ xr ^ * y $ se e solo se $ y $ è un" discendente "(dal tuo significato) di $ x $ .

Quando guardi la letteratura, dovrai conoscere un altro pezzo di notazione: la chiusura transitiva di $ r $ , denotato $ R ^ + $ , è la relazione più piccola $ r ^ + $ tale che $ R \ SOTETETQ R ^ + $ e $ R ^ + $ è transitivo. Algoritmi per il calcolo della chiusura transitiva e la chiusura transitiva riflessiva sono correlate, poiché differiscono solo dalle voci "diagonali": $ r ^ + \ Cup \ Sinistra \ {(x, x) \, | \, x \ in x \ destro \}= r ^ * $ .

Ci sono diversi algoritmi standard per il calcolo della RTC di una relazione. Se la relazione è densa, nel senso che è possibile rappresentarlo come una matrice di bit, il Algoritmo Floyd-Warshall è uno degli algoritmi pratici più veloci; il suo tempo di esecuzione è $ \ theta (| v | ^ 3) $ in teoria, ma il ciclo interno è abbastanza veloce su hardware reale dato che è un mucchio di bit Manipolazioni vettoriali

Per le relazioni sparse, vedere Tesi di Esko Nuutila , che contiene a Ottimo sondaggio e altri algoritmi più recenti.