multigraph

A multigraph is a graph in which we allow more than one edge to join a pair of vertices. Two or more edges that join a pair of vertices are called parallel edges. Every graph, then, is a multigraph, but not all multigraphs are graphs. Some authors define the concept of a graph by excluding graphs with multiple edges or loops. Then if they want to consider more general graphs the multigraph is introduced. Usually, such graphs have no loops. Formally, a multigraph $G=(V,E)$ is a pair, where $E=(V^{(2)},f)$ is a multiset for which $f(x,x)=0$ and $V^{(2)}$ is the set of unordered pairs of $V$.

A multigraph can be used to a matrix whose entries are nonnegative integers. To do this, suppose that $A=(a_{ij})$ is an $m\times n$ matrix of nonnegative integers. Let $V=S\cup T$, where $S=\{1,\mathrm{\dots },m\}$ and $T=\{1^{\prime },\mathrm{\dots },n^{\prime }\}$ and connect vertex $i\in S$ to vertex $j^{\prime }\in T$ with $a_{ij}$ edges.

Title	multigraph
Canonical name	Multigraph
Date of creation	2013-03-22 11:57:57
Last modified on	2013-03-22 11:57:57
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	8
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 05C75
Synonym	parallel edge
Related topic	Graph
Related topic	Subgraph
Related topic	GraphHomomorphism
Related topic	Pseudograph
Related topic	Quiver
Related topic	AxiomsOfMetacategoriesAndSupercategories