Transitive series-parallel digraph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Transitive series-parallel digraph''' --- транзитивный параллельно-последовательный орграф. ''' Transitive series-p…») |
(нет различий)
|
Текущая версия от 14:05, 4 августа 2011
Transitive series-parallel digraph --- транзитивный параллельно-последовательный орграф.
Transitive series-parallel digraphs are recursively defined as:
(1) A digraph on a single node is TSP (transitive series-parallel).
(2) If [math]\displaystyle{ G_{1} = (V_{1},E_{1}) }[/math] and [math]\displaystyle{ G_{2} = (V_{2},E_{2}) }[/math] are TSP digraphs and [math]\displaystyle{ V_{1} \cap V_{2} = \emptyset }[/math], then
(2.1) [math]\displaystyle{ G_{1} \parallel G_{2} = (V_{1} \cup V_{2}, E_{1} \cup E_{2}) }[/math] is a TSP digraph (the parallel composition).
(2.2) [math]\displaystyle{ G_{1} \rightarrow G_{2} = (V_{1} \cup V_{2}, E_{1} \cup E_{2} \cup (V_{1} \times V_{2})) }[/math] is a TSP digraph (the series composition).
(3) There are no further TSP digraphs.