Decomposizione DAG in componenti "paralleli"

Question

Consideriamo un DAG (grafo diretto aciclico) con singola sorgente e singolo sink, per cui l'insieme di tutti i suoi percorsi dalla sorgente al sink può essere suddiviso in sottoinsiemi, in modo tale che due percorsi qualsiasi da sottoinsiemi diversi non abbiano archi comuni .

Questo DAG può essere scomposto in una serie di componenti "paralleli", che hanno in comune solo l'origine e il sink. Questa decomposizione ha un nome?

Answer 1

Nel contesto dei grafici paralleli in serie , diciamo semplicemente che il grafico è una composizione parallela di quei componenti.

In particolare, dati digrafi $D_1, \dots, D_n$ ciascuno con una fonte designata $s_i$ e affondare $t_i$, la loro composizione parallela si ottiene nel modo seguente:

1. Prendi l'unione disgiunta di $D_1$ attraverso $D_n$.
2. Unisci il file $n$ vertici $s_1, \dots, s_n$ in un'unica fonte $s$ con un vantaggio $s \to v$ ogni volta che abbiamo avuto un vantaggio $s_i \to v$ per ogni $i$.
3. Unisci il file $n$ vertici $t_1, \dots, t_n$ in un unico lavandino $t$ con un vantaggio $v \to t$ ogni volta che abbiamo avuto un vantaggio $v \to t_i$ per ogni $i$.

Di solito, il nostro obiettivo è definire i digrafi serie-paralleli come grafici che possono essere ottenuti da molti diretti$K_2$E 'da questa operazione e dalla composizione in serie. Ma la composizione parallela può essere definita anche quando i singoli digrafi che stiamo componendo non hanno questa struttura.

(Se guardi il collegamento di Wikipedia, fornisce una definizione per i grafici non orientati, ma menziona che si estende ai digrafi paralleli in serie, che è quello che ho fatto qui.)