Decomposição do DAG em componentes "paralelos"

Question

Vamos considerar um DAG (gráfico acíclico direcionado) com fonte única e coletor único , para o qual o conjunto de todos os seus caminhos da fonte ao coletor pode ser dividido em subconjuntos, de modo que quaisquer dois caminhos de subconjuntos diferentes não tenham arcos comuns .

Este DAG pode ser decomposto em vários componentes "paralelos", que têm apenas a origem e o coletor em comum. Essa decomposição tem nome?

Answer 1

No contexto de gráficos paralelos em série , simplesmente dizemos que o gráfico é uma composição paralela desses componentes.

Especificamente, dados dígrafos $D_1, \dots, D_n$ cada um com uma fonte designada $s_i$ e afundar $t_i$, sua composição paralela é obtida da seguinte maneira:

1. Considere a união disjunta de $D_1$ através $D_n$.
2. Fundir o $n$ vértices $s_1, \dots, s_n$ em uma única fonte $s$ com uma vantagem $s \to v$ sempre que tínhamos uma vantagem $s_i \to v$ para qualquer $i$.
3. Fundir o $n$ vértices $t_1, \dots, t_n$ em uma única pia $t$ com uma vantagem $v \to t$ sempre que tínhamos uma vantagem $v \to t_i$ para qualquer $i$.

Normalmente, nosso objetivo é definir dígrafos série-paralelos como gráficos que podem ser obtidos a partir de muitos$K_2$por esta operação e por composição em série. Mas a composição paralela pode ser definida mesmo quando os dígrafos individuais que estamos compondo não têm essa estrutura.

(Se você olhar o link da Wikipedia, ele dá uma definição para gráficos não direcionados, mas menciona que se estende a dígrafos paralelos em série, que é o que fiz aqui.)