Descomposición de DAG en componentes "paralelos"

Question

Consideremos un DAG (gráfico acíclico dirigido) con una sola fuente y un solo sumidero, para el cual el conjunto de todas sus rutas desde la fuente hasta el sumidero se puede dividir en subconjuntos, de modo que dos rutas de diferentes subconjuntos no tienen arcos comunes .

Este DAG se puede descomponer en varios componentes "paralelos", que solo tienen en común la fuente y el sumidero. ¿Tiene nombre esta descomposición?

Answer 1

En el contexto de los gráficos de series paralelas , simplemente decimos que el gráfico es una composición paralela de esos componentes.

Específicamente, dados los dígrafos $D_1, \dots, D_n$ cada uno con una fuente designada $s_i$ y hundirse $t_i$, su composición paralela se obtiene de la siguiente manera:

1. Tome la unión disjunta de $D_1$ mediante $D_n$.
2. Fusionar el $n$ vértices $s_1, \dots, s_n$ en una sola fuente $s$ con un borde $s \to v$ cada vez que teníamos una ventaja $s_i \to v$ para cualquier $i$.
3. Fusionar el $n$ vértices $t_1, \dots, t_n$ en un solo fregadero $t$ con un borde $v \to t$ cada vez que teníamos una ventaja $v \to t_i$ para cualquier $i$.

Por lo general, nuestro objetivo es definir los dígrafos en serie-paralelo como gráficos que se pueden obtener de muchos$K_2$es por esta operación y por composición en serie. Pero la composición paralela se puede definir incluso cuando los dígrafos individuales que estamos componiendo no tienen esta estructura.

(Si miras el enlace de Wikipedia, da una definición de gráficos no dirigidos, pero menciona que se extiende a dígrafos paralelos en serie, que es lo que he hecho aquí).