Difference between revisions of "Multigraph"
(New page: A '''multigraph''' is a graph in which we allow multiple edges between two fixed vertices. Formally, a multigraph <math>M</math> is a pair <math>M = (V, E)</mat...) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 7: | Line 7: | ||
{{stub}} | {{stub}} | ||
| + | [[Category:Graph theory]] | ||
Latest revision as of 08:21, 27 May 2008
A multigraph is a graph in which we allow multiple edges between two fixed vertices. Formally, a multigraph 
is a pair 
where 
is a (usually finite) set of vertices and 
is a (also usually finite) multiset of pairs of elements of . Frequently in the context of multigraphs one considers graphs where loops are allowed, i.e. is allowed to contain (possibly several copies of) the pair 
for some 
.
Generalizations
Multigraphs may be thought of as special cases of (edge-)weighted graphs, where the weight on each edge is the multiplicity of the edge in . In this interpretation, multigraphs are exactly those weighted graphs for which each edge weight is a positive (or nonnegative) integer.
This article is a stub. Help us out by expanding it.
