Series-parallel graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Series-parallel graph''' --- параллельно-последовательный граф. ''' Series-parallel graphs''' are recursively defined as: (1) A …») |
(нет различий)
|
Текущая версия от 15:44, 23 июня 2011
Series-parallel graph --- параллельно-последовательный граф.
Series-parallel graphs are recursively defined as:
(1) A one-vertex graph with a loop is series-paralel.
(2) Subdividing an edge of a series-parallel graph [math]\displaystyle{ G }[/math] with a new vertex gives a series-parallel graph (the series operation).
(3) Creating a parallel edge for a non-loop edge of a series-parallel graph (the parallel operation).
(4) There are no further series-parallel graphs.
Note that these graphs can have loops and multiple edges. Since series-parallel graphs are the graphs which contain no subgraphs homeomorphic to [math]\displaystyle{ K_{4} }[/math], the outerplanar graphs are series-parallel graphs.
See also
- Transitive series-parallel graph.