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 by David Eppstein.
A two-terminal graph (TTG) is a graph with two distinguished vertices, s and t called source and sink, respectively.
The parallel composition Pc = Pc(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 Pc and merging the sinks of X and Y to create the sink of Pc.
The series composition Sc = Sc(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 the source of Sc and the sink of Y becomes the sink of Sc.
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.
Read more about this topic: Series-parallel Graph
Famous quotes containing the word definition:
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)