Series-parallel graph

Series-parallel graph

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.

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 incite journal|author=Eppstein, David|authorlink=David Eppstein|url=http://www.ics.uci.edu/~eppstein/pubs/Epp-IC-92.pdf|title=Parallel recognition of series-parallel graphs|journal=Information and Computation|volume=98|issue=1|pages=41–55|year=1992|doi=10.1016/0890-5401(92)90041-D]

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 when some two of its vertices are regarded as 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.

Alternative definition

The following definition specifies the same class of graphscite journal|author=Duffin, R. J.|title=Topology of Series-Parallel Networks|journal=Journal of Mathematical Analysis and Applications|volume=10|year=1965|pages=303–313|doi=10.1016/0022-247X(65)90125-3] .

"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 other than s or t with a single edge.

Research involving series-parallel graphs

SPGs may be recognized in linear timecite journal|author=Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L.|title=The recognition of series parallel digraphs|journal=SIAM Journal on Computing|volume=11|year=1982|pages=289–313|doi=10.1137/0211023] 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, [cite journal|author=Takamizawa, K.; Nishizeki, T.; Saito, N.|title=Linear-time computability of combinatorial problems on series-parallel graphs|journal=Journal of the ACM|volume=29|year=1982|pages=623–641|doi=10.1145/322326.322328] including 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 capitalizes 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.

Generalization

The generalized series-parallel graphs (GSP-graphs) are an extension of the SPGs [cite journal|author=Korneyenko, N. M.|title=Combinatorial algorithms on a class of graphs|journal=Discrete Applied Mathematics|volume=54|issue=2–3|pages=215–217|year=1994|doi=10.1016/0166-218X(94)90022-1 Translated from "Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci.", (1984) no. 3, pp. 109-111 ru icon] 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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • Outerplanar graph — A maximal outerplanar graph and its 3 coloring. In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing.… …   Wikipedia

  • Hadwiger conjecture (graph theory) — In graph theory, the Hadwiger conjecture (or Hadwiger s conjecture) states that, if an undirected graph G requires k or more colors in any vertex coloring, then one can find k disjoint connected subgraphs of G such that each subgraph is connected …   Wikipedia

  • Cactus graph — A cactus graph (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph may belong to at most one cycle.Cactus graphs were first studied under …   Wikipedia

  • graph — /graf, grahf/, n. 1. a diagram representing a system of connections or interrelations among two or more things by a number of distinctive dots, lines, bars, etc. 2. Math. a. a series of points, discrete or continuous, as in forming a curve or… …   Universalium

  • Parallel computing — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Comparability graph — In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable… …   Wikipedia

  • Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… …   Wikipedia

  • Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

  • Hypohamiltonian graph — In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.HistoryHypohamiltonian graphs were first… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”