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 is a pair, where is a multiset for which and is the set of unordered pairs of .
A multigraph can be used to a matrix whose entries are nonnegative integers. To do this, suppose that is an matrix of nonnegative integers. Let , where and and connect vertex to vertex with edges.
|Date of creation||2013-03-22 11:57:57|
|Last modified on||2013-03-22 11:57:57|
|Last modified by||Mathprof (13753)|