# 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 |