Multigraf

Multigraf je v matematiki graf, ki lahko ima večkratne povezave (ali vzporedne povezave), ki potekajo med posameznimi točkami. To pomeni, da sta dve točki povezani z več kot samo eno povezavo.

Multigraf ${\displaystyle G\,}$ je urejeni par ${\displaystyle G:=(V,E)\,}$, kjer je:

• ${\displaystyle V\,}$ množica točk
• ${\displaystyle E\,}$ večkratna množica neurejenih parov povezav

Nekateri ne ločujejo pojma multigraf in psevdograf. Za druge je psevdograf multigraf z zankami.

Posebna oblika je multidigraf, ki je usmerjeni graf, ki lahko vsebuje večkratne povezave od točke nazaj do iste točke (zanka). Multidigraf ${\displaystyle G\,}$ je urejeni par ${\displaystyle G:=(V,A)\,}$ za katerega velja:

• ${\displaystyle V\,}$ je množica točk
• ${\displaystyle A\,}$ je večkratna množica parov točk, ki se imenujejo usmerjene povezave ali loki ali puščice.