¿Hay un término para estos subgrafos de "descendencia" de gráficos acíclicos dirigidos?

Question

Considerar un gráfico acíclico dirigido $ g $ con el conjunto de vértices $ v $ .Elija un vértice $ v $ , y deje que $ H $ sea el subgrafo que contiene $ v $ y todos los demás vértices en $ g $ que son accesibles desde $ v $ (junto con los bordes dirigidos asociados).

(en otras palabras, si elegimos $ v \ in v $ , entonces estamos interesados en el subconjunto que consiste en $ v $ y todos sus descendientes).

¿Hay un término aceptado para este subconjunto particular de vértices (o el subgrafo)?Parece ser un concepto bastante elemental, así que esperaba encontrar una frase de uso común para esto, pero mi búsqueda se está vacía hasta ahora.Gracias por las respuestas o clientes potenciales!

Answer 1

tipo de. Pero vamos a utilizar la forma habitual de inactividad de la computadora de describir esto, utilizando el idioma de relaciones binarias .

Probablemente ya está familiarizado con las relaciones binarias, como la igualdad $= $ , menos-o-igual a $ \ le $ , subconjunto $ \ subestesteq $ , etc. En general, una relación binaria $ r $ sobre un conjunto $ x $ es un subconjunto $ r \ subespeteq x \ veces x $ . Si $ (x, y) \ en R $ , denotamos esto como $ xry $ .

Si $ \ forall x \ in x, xrx $ , luego $ r $ es Reflexivo . Las relaciones $= $ y $ \ le $ son reflexivo, pero $ \ lt $ no lo es.

Si $ \ forall x, y, z \ in x, xrez \, \ wedge \, yrz \ rudowarrow xrz $ , luego $ R $ es transitivo . Muchas relaciones son transitivas, incluidas todas las que se indican anteriormente. Si $ x \ le y $ y $ y \ le z $ , luego $ x \ le z $ .

Dada una relación $ r $ , el cierre transitivo reflexivo de $ r $ < / span>, denoted $ r ^ * $ , es la relación más pequeña $ r ^ * $ tal que $ r \ subespeteq r ^ * $ , y $ r ^ * $ es reflexivo y transitivo.

Interpretando su gráfico como una relación binaria (ya que los bordes realmente parecen importarle, solo está interesado en el conjunto de vértices), esto es exactamente lo que desea: $ XR ^ * y $ Si y solo si $ y $ es un" descendiente "(por su significado) de $ x x $ .

Cuando mira la literatura, deberá conocer una notación más: el cierre transitivo de $ r $ , denota $ r ^ + $ , es la relación más pequeña $ r ^ + $ tal que $ r \ subespeteq r ^ + $ , y $ r ^ + $ es transitivo. Los algoritmos para computar el cierre transitivo y el cierre transitivo reflexivo están relacionados, ya que difieren solo por las entradas "diagonales": $ r ^ + \ taza \ izquierda \ {(x, x) \, | \, x \ in x \ derecha \}= r ^ * $ .

Hay varios algoritmos estándar para computar la RTC de una relación. Si la relación es densa, en el sentido de que es factible representarlo como una matriz bit, la algoritmo de Floyd-Warshall es uno de los algoritmos prácticos más rápidos; Su tiempo de ejecución es $ \ theta (| v | ^ 3) $ en teoría, pero el bucle interno es bastante rápido en el hardware real dado que es un montón de bit. Manipulaciones vectoriales.

Para las relaciones dispersas, consulte Tesis de Esko Nuutila , que contiene un Muy buena encuesta, así como algunos algoritmos más recientes.