Multigraf

En matemàtiques, i més concretament en teoria de grafs, un multigraf és un graf que pot tenir arestes múltiples^[1] (de vegades anomenades també arestes paral·leles^[2][3]); és a dir, arestes que tenen els mateixos vèrtexs incidents. Així, dos vèrtexs poden estar connectats per més d'una aresta. Per a alguns autors, un multigraf no permet l'existència de bucles, i reserven el terme pseudograf per a multigrafs amb bucles. Altres autors permeten que els multigrafs admetin bucles,^[1] i consideren com a sinònims els termes "pseudograf" i "multigraf".

Existeixen dues nocions diferents d'arestes múltiples:

• Arestes sense identitat pròpia: la identitat d'una aresta queda definida únicament pels dos vèrtexs que connecta. En aquest cas, el terme "arestes múltiples" significa que la mateixa aresta pot aparèixer diverses vegades entre aquests dos vèrtexs.
• Arestes amb identitat pròpia: les arestes són entitats primitives, igual que els vèrtexs. Quan hi ha arestes múltiples que connecten dos vèrtexs, es tracta d'arestes diferents.

Un multigraf és diferent d'un hipergraf, que és un graf en el qual una aresta pot connectar qualsevol nombre de vèrtexs, no només dos.