Multigrafen

Multigrafen, eller multigraphen, är ett begrepp inom grafteori som beskriver en graf där flera kanter kan sammanbindas mellan samma par av noder. I många definitioner tillåts parallella kanter mellan två noder, medan loopar (kanter som börjar och slutar i samma nod) kan vara tillåtna eller förbjudna beroende på convention. Om loopar är tillåtna används ofta termen pseudograf.

En multigraf består av en mängd noder (vertices) och en mängd kanter (edges). En kant mellan två olika noder u och v kan finnas i flera kopior, vilket kallas parallella kanter. En kant kan också vara en loop som kopplar en nod till sig själv.

Representation och mått

- Adjacens: i en adjacency-matris A uppfyller A[i][j] antalet kanter mellan noderna i och j (för i ≠ j). För loopar används vanligtvis A[i][i] för antalet loopar vid noden i.

- Grad: nodens grad är antalet kanter som är incidenta på noden. Om en loop räknas som två incidencer, är graden d(i) = sum_j A[i][j] + A[i][i].

- Egna egenskaper: multigrafen kan vara sammanlänkad eller inte, och den kan ha olika antal kanter mellan olika par av noder.

Relation till andra grafklasser

- Simple graf: ingen kant är parallell, inga loopar.

- Multigraf: tillåter parallella kanter (och ofta loopar).

- Pseudograf: tillåter både parallella kanter och loopar.

Användning och tillämpningar

Multigrafer används för att modellera nätverk där flera relationer mellan samma par av enheter är meningsfulla, till exempel transportnät med flera olika rutter mellan städer, kommunikationsnät med flera länkar, eller sociala nätverk med flera typer av relationer mellan samma personer.

Exempel: Ett multigraf med noderna A, B, C kan ha tre parallella kanter mellan A och B, en kant mellan B och C, och två loopar vid A.