Multigrafi

In Teoria dei Grafi, un multigrafo è una struttura caratterizzata da un insieme finito di nodi e archi che collegano due o più nodi, oppure un nodo con se stesso (cappio).

Un multigrafo $G$ è una tripla $G=(V, E, \Psi_{G})$, dove $V$ è l'insieme dei nodi, $E$ quello di coppie di elementi non ordinati di $V$ e $\Psi_{G} : E \rightarrow \{\{u,v\} : u, v \epsilon V\}$ è una mappa che assegna ad ogni arco una coppia di nodi $V$.

Abbiamo che $\Psi_{G} (e) = \Psi_{G} (f)$ per due distinti archi $\{e, f \epsilon E\}$, nel caso di $e$ e $f$ hanno la stessa fine e sono detti paralleli.

Un cappio o loop è un elemento $e$ di $E$ tale che $\Psi_{G} (e) = \{i, j\}$ per alcuni nodi $i$. Nella rappresentazione di un multigrafo, i cappi sono rappresentati da linee chiuse.

Il diagramma del multigrafo (in figura) $G = (V, E)$ dove $V = \{1, 2, 3, 4, 5\}$
$E = \{e j : J = 1, 2, 3, 4, 5, 6, 7, 8\}$

$$\Psi_{G} (e_{1}) = \{1, 3\}, \Psi_{G} (e_{2}) = \{1, 3\},$$
$$\Psi_{G} (e_{3}) = \{1, 2\}, \Psi_{G} (e_{4}) = \{2, 2\},$$
$$\Psi_{G} (e_{5}) = \{2, 5\}, \Psi_{G} (e_{6}) = \{3, 5\},$$
$$\Psi_{G} (e_{7}) = \{3, 4\}, \Psi_{G} (e_{8}) = \{3, 4\}$$