nLab
multigraph

Contents

Idea

In graph theory a multigraph a particular type of graph. A multigraph is a set of vertices and for each unordered pair of distinct vertices a set of edges between these.

The terminology is used in distinction to

  1. simple graphs, which are multigraphs with at most one edge between any unordered pair of distinct vertices;

  2. pseudographs, which are like multigraphs but admitted to have “loops” in the sense of edges between a vertex and itself.

Beware that the terminology is not completely consistent across different authors. Some authors may allows loops when they speak of multigraphs.

Definition

More formally this means that a multigraph is

  1. a set VV (“of vertices”);

  2. a set EE (“of edges”);

  3. a function E{{v 1,v 2}={v 2,v 1}|v 1,v 2V,v 1v 2}E \to \left\{ {\,\atop \,} \{v_1, v_2\} = \{v_2, v_1\} \;\vert\; v_1, v_2 \in V \,,\; v_1 \neq v_2 {\, \atop \,} \right\} (sending any edge to the unordered pair of distinct vertices that it goes between).

Specifically a finite multigraph is, after choosing a linear order on its set of vertices, the same as

  1. a natural number vv \in \mathbb{N} (the number of vertices);

  2. for each i<j{1,,v}i \lt j \in \{1, \cdots, v\} a natural number e i,je_{i,j} \in \mathbb{N} (the number of edges between the iith and the jjth vertex)

Examples

References

Discussion with an eye towards Feynman diagrams includes

  • Michael Borinsky, section 2.1.1 of Algorithmization of the Hopf algebra of Feynman graphs (pdf)

See also

Last revised on August 2, 2018 at 03:11:43. See the history of this page for a list of all contributions to it.