Multidigrafo

In matematica e in particolare in teoria dei grafi, per multidigrafo intendiamo una struttura discreta che generalizza quella di digrafo: come questa è costituita da vertici e collegamenti tra vertici, archi, tra due vertici si possono avere più archi distinti (e un vertice può possedere più cappi).

I multidigrafi si possono considerare i corrispondenti dei multigrafi con i collegamenti orientati; viceversa i multigrafi si possono considerare multidigrafi simmetrici.

Applicazioni

Un multidigrafo può servire per definire un modello di un sistema di collegamenti direzionati, ad es. di strade a senso unico oppure organigramma di persone che in un'attività collaborativa si scambiano informazioni o messaggi. I multidigrafi si possono anche considerare i tipi più semplici di macchine formali, interpretando i loro vertici come stati e i loro archi come transizioni tra stati. Essi in effetti sono chiamati anche semiautomi o semiautomi a stati finiti.

Definizioni

Un multidigrafo è una struttura relazionale della forma ${\displaystyle M=\langle Q,A,\tau \rangle }$, dove Q è un insieme finito chiamato insieme dei vertici o insieme dei nodi di M, A è un insieme finito chiamato alfabeto di M e ${\displaystyle \tau :A\mapsto Q\times Q}$. Ad ogni lettera ${\displaystyle \,a\in A}$ la funzione ${\displaystyle \,\tau }$ fa corrispondere una coppia di elementi di Q che si dice arco del multidigrafo relativo all'etichetta a. Se le due componenti di una coppia coincidono si parla di cappio del multidigrafo. Due archi corrispondenti alla stessa coppia di vertici e a due etichette diversa si dicono archi paralleli; questa relazione di parallelismo è una equivalenza. Due archi relativi a due coppie l'una riflessa dell'altra si dicono archi opposti.

Quando si studiano le proprietà generali dei multidigrafi le lettere a dell'alfabeto A non hanno molta importanza e servono solo per distinguere i singoli archi.

Esempi e raffigurazioni

Consideriamo il multidigrafo ${\displaystyle \,M_{1}=\langle Q,A,\tau \rangle }$ corrispondente a

${\displaystyle \,Q=\{1,2,3,4,5,6\}\qquad A=\{a,b,c,...,l\}}$,

${\displaystyle \qquad \tau ={\begin{vmatrix}{\begin{matrix}a&b&c&d&e&f\\12&22&23&23&33&33\end{matrix}}\quad {\begin{matrix}g&h&i&j&k&l\\34&14&15&15&51&56\end{matrix}}\end{vmatrix}}}$

Nella indicazione tabellare della funzione abbiamo abbreviato ${\displaystyle \,\langle i,j\rangle }$ con ${\displaystyle \,ij}$.

Una struttura come questa si esamina agevolmente attraverso una sua raffigurazione, ovvero attraverso una sua immersione nel piano.

Si trova che gli archi etichettati da c e d sono paralleli; vi sono altre due classi di parallelismo di archi del multidigrafo: quella relativa alle etichette e ed f (formata da cappi paralleli), quella relativa a i e j e le classi relative ai singoli spigoli rimanenti. Gli archi relativi alle etichette j e k sono opposti.

Sottomultidigrafi e omomorfismi fra multidigrafi

Dati due multidigrafi ${\displaystyle \,M=\langle Q,A,\tau \rangle }$ ed ${\displaystyle \,N=\langle R,B,\rho \rangle }$ si dice che il secondo è sottomultidigrafo del primo e si scrive ${\displaystyle \,N\subseteq M}$ se e solo se

${\displaystyle R\subseteq Q\quad B\subseteq A\quad {\mbox{ e }}\quad \rho \subseteq \tau _{|B}}$ ;

qui ${\displaystyle \,\tau _{|B}}$ denota la restrizione della funzione ${\displaystyle \,\sigma }$ al suo sottodominio ${\displaystyle \,B}$.

Un sottomultidigrafo del precedente è

${\displaystyle \left\langle \{1,2,3,5\},\{a,b,c,d,e,k\},{\begin{vmatrix}a&b&c&d&e&k\\12&22&23&23&33&51\end{vmatrix}}\right\rangle }$

Si dice omomorfismo di un multigrafo in un secondo multigrafo una funzione ${\displaystyle \,m}$ dall'insieme dei vertici del primo nell'insieme dei vertici del secondo tale che l'insieme degli archi del secondo si ottiene trasformando con ${\displaystyle \,m}$ l'insieme degli spigoli del primo.

Digrafo di un multidigrafo

Ad ogni multidigrafo si associa facilmente un digrafo confondendo i suoi archi paralleli.

Più formalmente si dice digrafo sottostante a un multidigrafo ${\displaystyle M=\langle Q,A,\tau \rangle }$ il digrafo

${\displaystyle G=\langle Q,{\mbox{cdm}}(\tau )\rangle }$ ,

dove cdm(f) denota il codominio della funzione f. Questo è il digrafo i cui archi sono le possibili coppie di vertici o i possibili cappi forniti dalla ${\displaystyle \,\tau }$.

Ad esempio il digrafo sottostante al multidigrafo ${\displaystyle \,M_{1}}$ dell'esempio iniziale è

${\displaystyle \left\langle \{1,2,3,4,5,6\},\{12,22,23,33,34,14,15,51,56\}\right\rangle }$.

Molte caratteristiche di un multidigrafo si possono introdurre a partire da caratteristiche del suo digrafo sottostante, oppure con costruzioni analoghe a quelle adottate per i digrafi. Talora queste costruzioni sono un po' più complesse di quelle relative ai digrafi.

Cammini di un multigrafo

Su un multidigrafo si possono definire cammini e percorsi come per i digrafi, con la possibilità di scegliere tra più archi quando si collegano talune coppie di vertici o taluni vertici con se stessi.

Anche per le coppie di archi dei multidigrafi si può stabilire se il secondo è raggiungibile dal primo o meno. Si possono quindi distinguere i multidigrafi connessi dai non connessi e si possono introdurre le componenti connesse dei multidigrafi.

Si possono inoltre distinguere i cammini chiusi, i cicli, i cammini euleriani ovvero i cammini iniettivi sugli spigoli e i cammini hamiltoniani ovvero i cammini iniettivi sui vertici.

Di conseguenza si possono introdurre nozioni come quelle di multidigrafo connesso, multidigrafo aciclico, regolare. Similmente a quanto si fa per i digrafi, anche per i multidigrafi si definiscono le sottoarborescenze e le sottoarborescenze massimali.

Altre caratteristiche di base dei multidigrafi

Per grado uscente di un vertice di un multidigrafo si intende il numero degli archi distinti che escono da tale vertice; per grado entrante di un vertice di un multidigrafo si intende il numero degli archi distinti che entrano in tale vertice.

Ad es. per il multigrafo ${\displaystyle \,M_{1}}$ privato dei cappi le funzioni che associano ai vertici grado uscente e grado entrante sono

${\displaystyle {\begin{vmatrix}1&2&3&4&5&6\\5&3&3&2&4&1\end{vmatrix}}\qquad {\begin{vmatrix}1&2&3&4&5&6\\5&3&3&2&4&1\end{vmatrix}}}$

Voci correlate

• Digrafo
• Grafo arricchito
  • Multigrafo
  • Pluridigrafo
  • Plurigrafo
• Semigruppo

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica