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=(aij) is an m×nmatrix of nonnegative integers. Let V=S∪T, where S={1,…,m} andT={1′,…,n′} and connect vertex i∈S to vertex j′∈T with aijedges.