Multigrafo

Da Wikipedia, l'enciclopedia libera.

In matematica e in particolare in teoria dei grafi, per multigrafo si intende una struttura che può dirsi costituita da un insieme finito di vertici e da spigoli che collegano due vertici o un vertice con sé stesso (in tal caso lo spigolo si dice cappio), con la possibilità che due vertici siano collegati da più spigoli distinti (e che un vertice presenti più cappi distinti).

Un multigrafo

I multigrafi servono come modelli di sistemi di località e di strade che li collegano per trattare problemi di trasporto; in tali modelli i cappi potrebbero essere inutili, oppure potrebbero indicare strade che da una località maggiore portano a località minori e tornano al centro di partenza. Nelle applicazioni effettive i multigrafi vengono arricchiti con parametri che potrebbero indicare lunghezze di strade o importanza delle località.

Le formule di struttura delle molecole, in particolare di quelle organiche, sono dei multigrafi con i vertici muniti di etichette che sono simboli di elementi chimici o di gruppi di atomi.

Definizioni[modifica | modifica sorgente]

Formalmente definiamo multigrafo una struttura relazionale della forma

M = \langle Q,A,\sigma\rangle

dove Q è un insieme finito chiamato insieme dei vertici di M, A è un insieme finito chiamato insieme delle etichette degli spigoli di M, e \sigma : A \mapsto \mathcal{B}_{1,2}(Q); qui con \mathcal{B}_{1,2}(Q) denotiamo la collezione dei sottoinsiemi di Q costituiti da uno o due vertici.

Quando si studiano i multigrafi per le loro proprietà generali, gli elementi di A sono oggetti semplici che servono solo per distinguere i diversi spigoli. Non così nelle applicazioni.

Le coppie \langle a,\sigma(a)\rangle si dicono spigoli del multigrafo; due spigoli \langle a,\sigma(a)\rangle e \langle b,\sigma(b)\rangle con \sigma(a)=\sigma(b) si dicono spigoli paralleli del multigrafo; questa relazione di parallelismo è chiaramente una relazione di equivalenza; uno spigolo \langle c,\sigma(c)\rangle con \,|\sigma(c)|= 1 si dice cappio del multigrafo. Uno spigolo privo di altri spigoli paralleli si dice spigolo semplice.

Esempi e raffigurazioni[modifica | modifica sorgente]

Consideriamo il multigrafo \,M_1=\langle Q,A,\sigma\rangle corrispondente a

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

\qquad \sigma = \begin{vmatrix} 
\begin{matrix} a & b & c & d & e & f \\ 12 & 2 & 23 & 23 & 3 & 3 \end{matrix} \quad 
\begin{matrix} g & h & i & j & k & l \\ 34 & 14 & 15 & 15 & 15 & 56 \end{matrix}
\end{vmatrix}

Nella indicazione tabellare della funzione abbiamo abbreviato \,\{i,j\} con \,ij e \,\{i\} con \,i.

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

EsempioMultigrafo.png

Si trova che gli spigoli etichettati da c e d sono paralleli; le altre classi di parallelismo di spigoli del multigrafo sono quella relativa alle etichette e ed f (formata da cappi paralleli, quella relativa a i, j e k e le classi relative ai singoli spigoli rimanenti.

Sottomultigrafi e omomorfismi fra multigrafi[modifica | modifica sorgente]

Dati due multigrafi \,M = \langle Q,A,\sigma\rangle ed \,N = \langle R,B,\tau\rangle si dice che il secondo è sottomultigrafo del primo e si scrive \,N \subseteq M se e solo se

 R\subseteq Q \quad B \subseteq A \quad \mbox{ e } \quad \tau \subseteq \sigma|_B  ;

qui \,\sigma|_B denota la restrizione della funzione \,\sigma al suo sottodominio \,B.

Un sottomultigrafo del precedente è

\langle \{1,2,3,5\}, \{a,b,c,d,e,k\}, \begin{vmatrix} a & b & c & d & e & k \\ 12 & 2 & 23 & 23 & 3 & 15 \end{vmatrix} \rangle

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

Grafo di un multigrafo[modifica | modifica sorgente]

Ad ogni multigrafo si associa facilmente un grafo non orientato confondendo i suoi spigoli paralleli.

Più formalmente si dice grafo sottostante a un multigrafo M = \langle Q,A,\sigma\rangle il grafo

G = \langle Q, \mbox{cdm}(\sigma)\rangle ,

dove cdm(f) denota il codominio della funzione f. Questo è il grafo i cui spigoli sono le possibili coppie di vertici o i possibili cappi forniti dalla \,\sigma.

Ad esempio il grafo sottostante al multigrafo \,M_1 dell'esempio iniziale è

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

Si introduce inoltre il grafo semplice sottostante a un multigrafo, grafo ottenuto eliminando i cappi del suo grafo sottostante.

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

Cammini di un multigrafo[modifica | modifica sorgente]

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

Anche per le coppie di vertici dei multigrafi si può stabilire se sono connessi o meno. Si possono quindi distinguere i multigrafi connessi dai non connessi e si possono introdurre le componenti connesse dei multigrafi.

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.

Si possono quindi introdurre nozioni come quelle di multigrafo connesso, multigrafo aciclico, multigrafo regolare. Similmente a quanto si fa per i grafi, anche per i multigrafi si definiscono i sottoalberi e i sottoalberi massimali.

Altre caratteristiche di base dei multigrafi[modifica | modifica sorgente]

Anche per i multigrafi può servire distinguere i vertici con colori diversi. Per ogni k intero positivo si dice multigrafo k-colorabile un multigrafo ai cui vertici si assegnano k colori in modo tale che due vertici collegati presentino due colori diversi.

Si osserva che tutte le proprietà di colorabilità di un multigrafo si riducono alle proprietà di colorabilità del suo grafo semplice sottostante. Quindi i problemi di colorabilità vanno posti sostanzialmente solo per i grafi semplici connessi.

Per grado di un vertice di un multigrafo privo di cappi si intende il numero degli spigoli distinti che incidono su tale vertice. Ad es. per il multigrafo \,M_1 privato dei cappi la funzione che associa i gradi ai vertici è

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

Si dice multigrafo regolare un multigrafo i cui vertici hanno lo stesso grado. Più specificamente di dice multigrafo k-regolare, con k intero positivo, un multigrafo i cui vertici hanno tutti grado k. Ciascuno dei due "cicloesatrieni" riguardanti la struttura del benzene si può rappresentare con un multigrafo 3-regolare.

Multigrafi planari[modifica | modifica sorgente]

Si introduce anche la nozione di immersione di un multigrafo su una superficie di un qualsiasi genere e in particolare nel piano e nella sfera. Si hanno in particolare le immersioni planari e si definiscono multigrafoi planari quelli che posseggono tali immersioni.

Si dimostra abbastanza facilmente che un multigrafo è planare se e solo se lo è il grafo semplice sottostante. Quindi i problemi di planarità vanno posti sostanzialmente solo per i grafi semplici connessi.

Osservazioni su termini e notazioni[modifica | modifica sorgente]

Si deve osservare che sull'uso del termine multigrafo si ha un accordo generale e vengono utilizzate anche varie alternative: sembra però opportuno per ragioni di chiarezza complessiva fare preciso riferimento a questo termine e ad altri presenti tra le Voci correlate.

Voci correlate[modifica | modifica sorgente]


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