Multigraph

From Wikipedia, the free encyclopedia

A multigraph is a graph which is permitted to have multiple edges, (also called "parallel edges") i.e. edges that have the same end nodes. Formally, a multigraph G is an ordered pair G:=(V, E) with

V a set of vertices or nodes,
E a multiset of unordered pairs of distinct vertices, called edges or lines.

Some authors also allow mutigraphs to have loops, that is, an edge that connects a vertex to itself.^[1]

A multidigraph is a directed graph which is permitted to have multiple arcs, i.e., arcs with the same source and target nodes. A multidigraph G is an ordered pair G:=(V,A) with

V a set of vertices or nodes,
A a multiset of ordered pairs of vertices called directed edges, arcs or arrows.

A mixed multigraph G:=(V,E, A) may be defined in the same way as a mixed graph.

1 Labeling
2 Notes
3 References
4 External links

[edit] Labeling

Multigraphs and multidigraphs also support the notion of graph labeling, in a similar way. However there is no unity in terminology in this case.

The definitions of labeled multigraphs and multidigraphs are similar, and we define only the latter ones here.

Definition 1: A labeled multidigraph is a labeled graph with labeled arcs.

Formally: A labeled multidigraph G is a multigraph with labeled nodes and arcs. Formally it is an 8-tuple $G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A)$ where

V is a set of nodes and A is a multiset of arcs.
$Σ V$ and $Σ A$ are finite alphabets of the available node and arc labels,
$s\colon A\rightarrow\ V$ and $t\colon A\rightarrow\ V$ are two maps indicating the source and target node of an arc,
$\ell_V\colon V\rightarrow\Sigma_V$ and $\ell_A\colon A\rightarrow\Sigma_A$ are two maps describing the labeling of the nodes and edges.

Definition 2: A labeled multidigraph is a labeled graph with multiple labeled edges, i.e. edges with the same end nodes and the same edge label (note that this notion of a labeled graph is different to the notion given by the article graph labeling).

[edit] Notes

^ For example, see. Bollobas, p. 7 and Diestel, p. 25.

[edit] References

Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
Bollobas, Bela; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
Gross, Jonathan L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
Gross, Jonathan L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2.
Harary, Frank; Graph Theory, Addison Wesley Publishing Company (January 1995). ISBN 0-201-41033-8.
Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.