Multigraph
The term multigraph refers to a graph in which multiple edges between nodes are either permitted (Harary 1994, p. 10; Gross and
Yellen 1999, p. 4) or required (Skiena 1990, p. 89, Pemmaraju and Skiena
2003, p. 198; Zwillinger 2003, p. 220). West (2000, p. xiv) recommends
avoiding the term altogether on the grounds of this ambiguity.
Some references require that multigraphs possess no graph loops (Harary 1994, p. 10; Gross and Yellen 1999, p. 4; Zwillinger
2003, p. 220), some explicitly allow them (Hartsfield and Ringel 1994, p. 7;
Cormen et al. 2001, p. 89), and yet others do not include any explicit
allowance or disallowance (Skiena 1990, p. 89; Gross and Yellen 1999, p. 351;
Pemmaraju and Skiena 2003, p. 198). Worse still, Tutte (1998, p. 2) uses
the term "multigraph" to mean a graph containing either loops or
multiple edges.
As a result of these many ambiguities, use of the term "multigraph" should be deprecated, or at the very least used with extreme caution.
SEE ALSO: Edge Multiplicity,
Graph Loop,
Graph Multiplicity,
Hypergraph,
Königsberg
Bridge Problem,
Mixed Graph,
Multiple
Edge,
Pseudograph,
Simple
Graph
REFERENCES:
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; and Stein, C. Introduction
to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2001.
Grimaldi, R. P. Discrete and Combinatorial Mathematics: An Applied Introduction, 4th ed. Longman,
1998.
Gross, J. T. and Yellen, J. Graph
Theory and Its Applications. Boca Raton, FL: CRC Press, 1999.
Harary, F. Graph
Theory. Reading, MA: Addison-Wesley, p. 10, 1994.
Hartsfield, N. and Ringel, G. Pearls in Graph Theory: A Comprehensive Introduction, 2nd ed. San Diego, CA: Academic
Press, 1994.
Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, 2003.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.
Tutte, W. T. Graph
Theory as I Have Known It. Oxford, England: Oxford University Press, 1998.
West, D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
Zwillinger, D. (Ed.). CRC Standard Mathematical Tables and Formulae, 31st ed. Boca Raton, FL: CRC Press,
2003.
Referenced on Wolfram|Alpha:
Multigraph
CITE THIS AS:
Weisstein, Eric W. "Multigraph." From
MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Multigraph.html
Contact the MathWorld Team
{{6, -7, 10}, {0, 3, -1}, {0, 5, -7}}
