DAG-Zerlegung in "parallele" Komponenten

Question

Betrachten wir eine DAG (gerichteter azyklischer Graph) mit einer einzelnen Quelle und einer einzelnen Senke, für die die Menge aller Pfade von der Quelle zur Senke in Teilmengen aufgeteilt werden kann, sodass zwei beliebige Pfade aus verschiedenen Teilmengen keine gemeinsamen Bögen haben .

Diese DAG kann in eine Reihe von "parallelen" Komponenten zerlegt werden, die nur die Quelle und die Senke gemeinsam haben. Hat diese Zerlegung einen Namen?

Answer 1

Im Zusammenhang mit seriell-parallelen Graphen sagen wir einfach, dass der Graph eine parallele Zusammensetzung dieser Komponenten ist.

Insbesondere gegebene Digraphen $D_1, \dots, D_n$ jeweils mit einer bestimmten Quelle $s_i$ und sinken $t_i$wird ihre parallele Zusammensetzung auf folgende Weise erhalten:

1. Nehmen Sie die disjunkte Vereinigung von $D_1$ durch $D_n$.
2. Führen Sie die $n$ Eckpunkte $s_1, \dots, s_n$ in eine einzige Quelle $s$ mit einer Kante $s \to v$ wann immer wir einen Vorteil hatten $s_i \to v$ für jeden $i$.
3. Führen Sie die $n$ Eckpunkte $t_1, \dots, t_n$ in ein einziges Waschbecken $t$ mit einer Kante $v \to t$ wann immer wir einen Vorteil hatten $v \to t_i$ für jeden $i$.

Normalerweise ist es unser Ziel, seriell-parallele Digraphen als Graphen zu definieren , die von vielen gerichteten erhalten werden können$K_2$'s durch diese Operation und durch Serienzusammensetzung. Die parallele Komposition kann jedoch auch dann definiert werden, wenn die einzelnen Digraphen, die wir komponieren, diese Struktur nicht haben.

(Wenn Sie sich den Wikipedia-Link ansehen, gibt er eine Definition für ungerichtete Diagramme, erwähnt jedoch, dass er sich auf seriell-parallele Digraphen erstreckt, was ich hier getan habe.)