Series-parallel graph
From Wikipedia, the free encyclopedia
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Contents |
[edit] Definition and terminology
In this context, the term graph means multigraph.
There are several ways to define series-parallel graphs. The following definition basically follows the one used in[1]
A two-terminal graph (TTG) is a graph with two distinguished vertices, s and t called source and sink, respectively.
The parallel composition P = P(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sources of X and Y to create the source of P and merging the sinks of X and Y to create the sink of P.
The series composition S = S(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sink of X with the source of Y. The source of X becomes source of P and the sink of Y becomes the sink of P.
A two-terminal series-parallel graph (TTSPG) is a graph that may be constructed by a sequence of series and parallel compositions starting from a set of copies of a single-edge graph K2 with assigned terminals.
Definition 1. Finally, a graph is called series-parallel (sp-graph), if it is a TTSPG with some two its vertices being source and sink.
In a similar way one may define series-parallel digraphs, constructed from copies of single-arc graphs, with arcs directed from the source to the sink.
[edit] Alternative definition
The following definition specifies the same class of graphs[2]
Definition 2. A graph is an sp-graph, if it may be turned into K2 by a sequence of the following operations:
- Replacement of a pair of parallel edges with a single edge that connects their common endpoints
- Replacement of a pair of edges incident to a vertex of degree 2 with a single edge that connects the two other endpoints of the original edges.
[edit] Research involving series-parallel graphs
SPGs may be recognized in linear time[2] and their series-parallel decomposition may be constructed in linear time as well.
Besides being a model of certain types of electric networks, these graphs are of interest in computational complexity theory, because a number of standard problems on graphs are solvable in linear time,[3] inluding finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion. Some of these problems are NP-complete for general graphs. The solution capitalize on the fact that if the answers for one of these problems are known for two SP-graphs, then one can quickly find the answer for their series and parallel compositions.
The series-parallel networks problem refers to a graph enumeration problem which asks for the number of series-parallel graphs that can be formed using a given number of edges.
[edit] Generalization
The generalized series-parallel graphs (GSP-graphs) are an extension of the SPGs[4] with the same algorithmic efficiency for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and outerplanar graphs.
GSP graphs may be specified by the Definition 2 augmented with the third operation of deletion of a dangling vertex (vertex of degree 1). Alternatively, Definition 1 may be augmented with the following operation.
- The source merge S = M(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the source of X with the source of Y. The source and sink of X become the source and sink of P respectively.
[edit] References
- ^ David Eppstein, "Parallel Recognition of Series-Parallel Graphs", Information and Computation 98(1):41–55, May 1992
- ^ a b Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler, The Recognition of Series Parallel Digraphs, SIAM J. Comput. 11 (1982), 289–313.
- ^ K. Takamizawa, T. Nishizeki, and N. Saito, Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs, J. ACM 29 (1982) 623–641.
- ^ N. M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Applied Mathematics, v.54 n.2-3, p.215-217, 1994, translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 (Russian)
