Multigraph

From AoPSWiki

Revision as of 13:21, 27 May 2008 by 1=2 (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

A multigraph is a graph in which we allow multiple edges between two fixed vertices. Formally, a multigraph $M$ is a pair $M = (V, E)$ where $V$ is a (usually finite) set of vertices and $E$ is a (also usually finite) multiset of pairs of elements of $V$ . Frequently in the context of multigraphs one considers graphs where loops are allowed, i.e. $E$ is allowed to contain (possibly several copies of) the pair $\{v, v\}$ for some $v \in V$ .

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 $E$ . 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.

Personal tools

Navigation

Search

Toolbox

Multigraph

From AoPSWiki

Generalizations