Multigrafo

Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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).

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.

Formalmente definiamo multigrafo una struttura relazionale della forma

M = ⟨ Q , A , σ ⟩ {\displaystyle 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 σ : A ↦ B 1 , 2 ( Q ) {\displaystyle \sigma :A\mapsto {\mathcal {B}}_{1,2}(Q)} ; qui con B 1 , 2 ( Q ) {\displaystyle {\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 ⟨ a , σ ( a ) ⟩ {\displaystyle \langle a,\sigma (a)\rangle } si dicono spigoli del multigrafo; due spigoli ⟨ a , σ ( a ) ⟩ {\displaystyle \langle a,\sigma (a)\rangle } e ⟨ b , σ ( b ) ⟩ {\displaystyle \langle b,\sigma (b)\rangle } con σ ( a ) = σ ( b ) {\displaystyle \sigma (a)=\sigma (b)} si dicono spigoli paralleli del multigrafo; questa relazione di parallelismo è chiaramente una relazione di equivalenza; uno spigolo ⟨ c , σ ( c ) ⟩ {\displaystyle \langle c,\sigma (c)\rangle } con | σ ( c ) | = 1 {\displaystyle \,|\sigma (c)|=1} si dice cappio del multigrafo. Uno spigolo privo di altri spigoli paralleli si dice spigolo semplice.

Consideriamo il multigrafo M 1 = ⟨ Q , A , σ ⟩ {\displaystyle \,M_{1}=\langle Q,A,\sigma \rangle } corrispondente a

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

σ = | a b c d e f 12 2 23 23 3 3 g h i j k l 34 14 15 15 15 56 | {\displaystyle \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 } {\displaystyle \,\{i,j\}} con i j {\displaystyle \,ij} e { i } {\displaystyle \,\{i\}} con i {\displaystyle \,i} .

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

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

Dati due multigrafi M = ⟨ Q , A , σ ⟩ {\displaystyle \,M=\langle Q,A,\sigma \rangle } ed N = ⟨ R , B , τ ⟩ {\displaystyle \,N=\langle R,B,\tau \rangle } si dice che il secondo è sottomultigrafo del primo e si scrive N ⊆ M {\displaystyle \,N\subseteq M} se e solo se

R ⊆ Q B ⊆ A  e  τ ⊆ σ | B {\displaystyle R\subseteq Q\quad B\subseteq A\quad {\mbox{ e }}\quad \tau \subseteq \sigma |_{B}}  ;

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

Un sottomultigrafo del precedente è

⟨ { 1 , 2 , 3 , 5 } , { a , b , c , d , e , k } , | a b c d e k 12 2 23 23 3 15 | ⟩ {\displaystyle \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 {\displaystyle \,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 {\displaystyle \,m} l'insieme degli spigoli del primo.

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 = ⟨ Q , A , σ ⟩ {\displaystyle M=\langle Q,A,\sigma \rangle } il grafo

G = ⟨ Q , cdm ( σ ) ⟩ {\displaystyle 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 σ {\displaystyle \,\sigma } .

Ad esempio il grafo sottostante al multigrafo M 1 {\displaystyle \,M_{1}} dell'esempio iniziale è

⟨ { 1 , 2 , 3 , 4 , 5 , 6 } , { 12 , 2 , 23 , 3 , 34 , 14 , 15 , 56 } ⟩ {\displaystyle \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.

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.

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 {\displaystyle \,M_{1}} privato dei cappi la funzione che associa i gradi ai vertici è

| 1 2 3 4 5 6 5 3 3 2 4 1 | {\displaystyle {\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 si 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.

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.

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.

• Multigrafo duale
• Multigrafo euleriano
• Problema dei ponti di Königsberg
• Grafo
• Grafo arricchito
• Multidigrafo
• Pluridigrafo

• Wikimedia Commons contiene immagini o altri file su multigrafo

• (EN) multigraph, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Multigraph, su MathWorld, Wolfram Research.

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