Existe um termo para esses subgraficos "descendentes" de gráficos acíclicos dirigidos?

Question

Considere um gráfico acíclico dirigido $ g $ com conjunto de vértices $ v $ .Escolha um vértice $ v $ e deixe $ h $ ser o subgraph contendo Matemática $ v $ e todos os outros vértices em $ g $ que são acessíveis a partir de $ v $ (junto com as bordas dirigidas associadas).

(em outras palavras, se escolhermos $ v \ in v $ , então estamos interessados no subconjunto consistindo de $ v $ e todos os seus descendentes).

Existe um termo aceito para este subconjunto específico de vértices (ou a subgraph)?Parece ser um conceito bastante elementar, então eu esperava encontrar uma frase comumente usada para isso, mas minha busca está chegando vazia até agora.Obrigado por quaisquer respostas ou leads!

Answer 1

tipo de. Mas vamos usar a maneira habitual de sencial de computação de descrever isso, usando a linguagem de Relações binárias .

Você provavelmente já está familiarizado com relações binárias, como igualdade $= $ , menos do que ou-igual a $ \ le $ , subconjunto $ \ subseteq $ e assim por diante. Em geral, uma relação binária $ R $ sobre um conjunto $ x $ é um subconjunto $ r \ subseteq x \ vezes x $ . Se $ (x, y) \ em R $ , denotamos isso como $ xry $ . .

Se $ \ forall x \ em x, xrx $ , então $ R $ é Reflexivo . As relações $= $ e $ \ Le $ são reflexivos, mas $ \ lt $ não é.

Se $ \ forall x, y, z \ in x, xry \, \ wedge \, yrz \ righttarrow xrz $ , então $ R $ é transitivo . Muitas relações são transitivas, incluindo todas as dadas acima. Se $ x \ le y $ e $ y \ le z $ , então $ x \ le z $ .

Dada uma relação $ R $ , o encerramento transitivo reflexivo da $ R $ < / span>, denotado $ r ^ * $ , é a menor relação $ r ^ * $ tal que $ r \ subseteq r ^ * $ , e $ r ^ * $ é reflexivo e transitivo. .

Interpretando seu gráfico como uma relação binária (já que as bordas não parecem realmente importar para você, você só está interessado no conjunto de vértices), isso é exatamente o que você quer: $ xr ^ * y $ se e somente se $ y $ é um" descendente "(pelo seu significado) de $ x $ .

Ao olhar para a literatura, você precisará saber mais um pedaço de notação: o encerramento transitivo de $ R $ , denotado $ r ^ + $ , é a menor relação $ r ^ + $ tal que $ r \ subseteq R ^ + $ , e $ r ^ + $ é transitivo. Algoritmos para computação do fechamento transitivo e o fechamento transitivo reflexivo estão relacionados, uma vez que diferem apenas pelas "diagonal" entradas: $ r ^ + \ cope \ left \ {(x, x) \, | \, x \ in x \ direita \}= r ^ * $ .

Existem vários algoritmos padrão para calcular o RTC de uma relação. Se a relação é densa, no sentido de que é viável representá-lo como uma matriz de um pouco, o Algoritmo Floyd-Warshall é um dos algoritmos práticos mais rápidos; Seu tempo de execução é $ \ theta (| v | ^ 3) $ em teoria, mas o loop interno é bastante rápido no hardware real, dado que é um monte de bit manipulações de vetor.

para relações esparsas, ver Esko Nuutila's Tese , que contém um muito boa pesquisa, bem como alguns algoritmos mais recentes.