Viviamo in un mondo intessuto di connessioni. Dalle amicizie sui social network alle rotte aeree globali, dalle dipendenze tra moduli software ai circuiti elettrici, le relazioni tra entità formano quelle che in matematica e informatica chiamiamo grafi. Un grafo è, in sostanza, un insieme di “nodi” (o vertici) collegati da “archi” (o spigoli).

Ma come possiamo rappresentare queste strutture complesse in un modo che sia rigoroso, efficiente e analizzabile da un computer o un algoritmo? Uno degli strumenti fondamentali, forse il più classico, è la Matrice di Adiacenza.

La matrice di adiacenza è una tabella quadrata che ci dice, a colpo d’occhio, quali nodi sono direttamente collegati tra loro. È una rappresentazione potente perché trasforma la struttura visiva di un grafo in un formato numerico, aprendo la strada a calcoli e analisi approfondite.

Capire come costruire e interpretare una matrice di adiacenza è il primo passo per addentrarsi nell’affascinante mondo della Teoria dei Grafi e delle sue innumerevoli applicazioni. In questo articolo, non ci limiteremo alla teoria. Attraverso una serie di esercizi pratici svolti passo passo, esploreremo come le matrici di adiacenza si adattano a diversi tipi di grafi:

• Grafi non orientati: per rappresentare relazioni simmetriche come le amicizie.
• Grafi orientati: per modellare connessioni unidirezionali, come strade a senso unico o dipendenze.
• Grafi pesati: dove gli archi hanno un valore (come tempi o costi).
• La potenza della matrice ([math]M^2[/math]): per scoprire i cammini di una certa lunghezza nel grafo.
• Grafi bipartiti: per gestire problemi di assegnazione e matching.

👉Matrici di Adiacenza: Guida Completa, Esempi e Utilizzo in Python

Ti guideremo attraverso ogni esempio, spiegando la logica dietro la costruzione della matrice e come interpretare i risultati.

Esercizio 1 (Base): Matrice di Adiacenza per una Rete Sociale

Contesto: Hai creato una piccola rete sociale con 4 amici: Alice (A), Bob (B), Carlo (C) e Daria (D).

• Alice è amica di Bob e Carlo.

• Bob è amico anche di Daria.

• Carlo e Daria non sono direttamente amici.

Richiesta: Costruisci la matrice di adiacenza del grafo non orientato che rappresenta questa rete.

Teoria

Per rappresentare grafi non orientati tramite matrice di adiacenza:

[math]M = (m_{ij})_{N \times N}[/math]

dove:

• N = 4 (numero di vertici/amici)
• m_ij =
  [math]\begin{cases}
  1 & \text{se esiste arco tra } i \text{ e } j \\
  0 & \text{altrimenti}
  \end{cases}[/math]

Proprietà fondamentali:

1. Simmetria: [math]m_{ij} = m_{ji}[/math] (le amicizie sono reciproche)
2. Diagonale nulla: [math]m_{ii} = 0[/math] (nessun auto-loop)

Costruzione Dettagliata

Ordinamento vertici: A (1), B (2), C (3), D (4)

Relazione	Celle Matrice	Valore
A ↔ B	m12, m21	1
A ↔ C	m13, m31	1
B ↔ D	m24, m42	1
Altre combinazioni	m14, m23, m34, diagonali	0

Matrice Risultante

[math]M = \begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}[/math]

Nota: Le etichette A,B,C,D sono mostrate a scopo illustrativo:

[math]\begin{array}{c|cccc}
& A & B & C & D \\
\hline
A & 0 & 1 & 1 & 0 \\
B & 1 & 0 & 0 & 1 \\
C & 1 & 0 & 0 & 0 \\
D & 0 & 1 & 0 & 0
\end{array}[/math]

🔗Matrici di Adiacenza in Python: Analisi e Applicazioni Pratiche per Reti Sociali e IoT

Esercizio 2 (Intermedio): Grafo Orientato per Mappa Cittadina

Contesto: In una città ci sono 4 luoghi collegati da strade a senso unico:

• Piazza (P), Scuola (S), Parco (K), Mercato (M).

• Da P si va a S e K.

• Da S si va a M.

• Da K si va a S e M.

• Da M non partono strade.

Richiesta: Costruisci la matrice di adiacenza per questo grafo orientato.

Teoria

Per rappresentare grafi orientati (digrafi):

[math]M = (m_{ij})_{N \times N} \quad \text{dove } N = 4[/math]

L’elemento m_ij vale:

[math]m_{ij} = \begin{cases}
1 & \text{se esiste arco } i \rightarrow j \\
0 & \text{altrimenti}
\end{cases}[/math]

Proprietà fondamentali:

1. Non-simmetria: [math]m_{ij} \neq m_{ji}[/math] (in generale)
2. Diagonale nulla: [math]m_{ii} = 0[/math] (nessun auto-loop)

Costruzione Dettagliata

Ordinamento vertici: P (1), S (2), K (3), M (4)

Arco Orientato	Cella Matrice	Valore
P → S	m12	1
P → K	m13	1
S → M	m24	1
K → S	m32	1
K → M	m34	1
Altri archi	mij (restanti)	0

Matrice Risultante

[math]M = \begin{bmatrix}
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0
\end{bmatrix}[/math]

Versione annotata con etichette:

[math]\begin{array}{c|cccc}
& P & S & K & M \\
\hline
P & 0 & 1 & 1 & 0 \\
S & 0 & 0 & 0 & 1 \\
K & 0 & 1 & 0 & 1 \\
M & 0 & 0 & 0 & 0
\end{array}[/math]

Verifica Proprietà

• Non-simmetria: Esempio m₁₂ = 1 ≠ m₂₁ = 0
• Grado uscente: Somma righe (P:2, S:1, K:2, M:0)
• Grado entrante: Somma colonne (P:0, S:2, K:1, M:2)

Esercizio 3 (Intermedio-Avanzato): Grafo Pesato per Tempi di Percorrenza

Contesto: In una rete di trasporti tra 3 stazioni (X, Y, Z), i tempi di percorrenza sono:

• X-Y: 5 min, Y-X: 5 min (strada bidirezionale).

• X-Z: 8 min solo in uscita da X.

• Y-Z: 3 min solo in uscita da Y.

Richiesta: Costruisci la matrice di adiacenza pesata, usando $\infty$ dove non esiste connessione.

Teoria

Per grafi pesati, la matrice di adiacenza M diventa una matrice dei pesi:

[math]M = (m_{ij})_{N \times N} \quad \text{dove } N = 3[/math]
[math]m_{ij} = \begin{cases}
w_{ij} & \text{peso dell’arco } i \rightarrow j \\
\infty & \text{se non esiste connessione diretta}
\end{cases}[/math]

Convenzioni speciali:

• ∞ indica assenza di percorso diretto
• Bidirezionale: X↔Y implica due archi orientati con stesso peso
• Diagonale: ∞ (nessun auto-loop)

Costruzione Dettagliata

Ordinamento vertici: X (1), Y (2), Z (3)

Connessione	Tipo	Cella Matrice	Valore
X ↔ Y	bidirezionale	m12, m21	5
X → Z	unidirezionale	m13	8
Y → Z	unidirezionale	m23	3
Auto-loop	diagonale	m11, m22, m33	∞
Connessioni mancanti	–	m31, m32	∞

Matrice Risultante

[math]M = \begin{bmatrix}
\infty & 5 & 8 \\
5 & \infty & 3 \\
\infty & \infty & \infty
\end{bmatrix}[/math]

Versione annotata con etichette:

[math]\begin{array}{c|ccc}
& X & Y & Z \\
\hline
X & \infty & 5 & 8 \\
Y & 5 & \infty & 3 \\
Z & \infty & \infty & \infty
\end{array}[/math]

Interpretazione Pratica

• La cella (1,2)=5 indica 5 min da X a Y
• La cella (1,3)=8 indica 8 min da X a Z
• La cella (3,1)=∞ indica nessun percorso diretto da Z a X
• La diagonale ∞ significa che non si considerano tempi per “restare nella stessa stazione”

Osservazioni

1. Asimmetria: m₁₃=8 ≠ m₃₁=∞

2. Percorsi alternativi: Per andare da X a Z si può:

• Percorso diretto: 8 min (X→Z)
• Percorso alternativo: X→Y→Z = 5+3 = 8 min

Esercizio 4 (Avanzato): Cammini di Lunghezza 2 con M²

Contesto: Usa la matrice dell’Esercizio 2 (città con sensi unici).
Richiesta: Calcola M² e interpreta il significato dell’elemento m₁₄ nella matrice risultante.

Teoria

In un grafo con matrice di adiacenza M, la potenza M² rivela i cammini di lunghezza 2:

[math](M^2)_{ij} = \sum_{k=1}^n M_{ik} \cdot M_{kj}[/math]

Dove:

• Ogni termine M_ik·M_kj verifica l’esistenza del cammino i→k→j
• La somma conta tutti i possibili nodi intermedi k

Calcoli Dettagliati

Elemento (1,4): Cammini P → … → M

[math](M^2)_{14} = \sum_{k=1}^4 M_{1k}M_{k4} = [/math]
[math]M_{11}M_{14} + M_{12}M_{24} + M_{13}M_{34} + M_{14}M_{44} = [/math]
[math](0)(0) + (1)(1) + (1)(1) + (0)(0) = 2[/math]

Interpretazione: Esistono 2 cammini di lunghezza 2 da P a M:

1. P → S → M (via k=2)
2. P → K → M (via k=3)

Elemento (3,4): Cammini K → … → M

[math](M^2)_{34} = M_{31}M_{14} + M_{32}M_{24} + M_{33}M_{34} + M_{34}M_{44} = [/math]
[math](0)(0) + (1)(1) + (0)(1) + (1)(0) = 1[/math]

Interpretazione: 1 cammino di lunghezza 2 da K a M:

• K → S → M (via k=2)
• Nota: K→M diretto è lunghezza 1 (non incluso in M²)

Elemento (2,4): Cammini S → … → M

[math](M^2)_{24} = M_{21}M_{14} + M_{22}M_{24} + M_{23}M_{34} + M_{24}M_{44} = [/math]
[math](0)(0) + (0)(1) + (0)(1) + (1)(0) = 0[/math]

Interpretazione: Nessun cammino di lunghezza 2 da S a M (solo il diretto S→M di lunghezza 1)

Matrice Risultante M²

[math]M^2 = \begin{bmatrix}
0 & 1 & 0 & 2 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0
\end{bmatrix}[/math]

Mappa dei Cammini

Elemento	Valore	Cammini
(1,2)	1	P → K → S
(1,4)	2	P → S → M, P → K → M
(3,4)	1	K → S → M

Osservazioni

• La diagonale nulla indica assenza di cammini di lunghezza 2 che terminano nello stesso nodo
• La riga 4 nulla riflette che M non ha archi uscenti
• M² ≠ M (i cammini di lunghezza 2 sono diversi dai diretti)

Esercizio 5 (Esperto): Grafo Bipartito per Assegnazione Progetti

Contesto: Un gruppo di 3 studenti (E1, E2, E3) può scegliere tra 2 progetti (P1, P2).

• E1 può fare P1 o P2.

• E2 può fare solo P1.

• E3 può fare solo P2.

Richiesta: Rappresenta come matrice di adiacenza il grafo bipartito studenti-progetti, poi verifica se esiste un accoppiamento perfetto (tutti gli studenti assegnati a un progetto senza conflitti).

Teoria

Un grafo bipartito è un grafo i cui vertici sono divisibili in due insiemi disgiunti U e V dove ogni arco connette un vertice di U a uno di V.

In questo caso:

[math]
\begin{aligned}
U &= \{\text{E1}, \text{E2}, \text{E3}\} \quad (\text{studenti}) \\
V &= \{\text{P1}, \text{P2}\} \quad (\text{progetti})
\end{aligned}
[/math]

Un accoppiamento perfetto è un insieme di archi che:

1. Copia tutti i vertici del grafo
2. Non condivide vertici (nessuno studente/progetto condiviso)

Condizione necessaria:
[math]|U| = |V| \quad \text{(numero studenti = numero progetti)}[/math]

Matrice di Adiacenza Bipartita

Rappresentazione 3×2 (studenti × progetti):

[math]
M = \begin{array}{c|cc}
& P1 & P2 \\
\hline
E1 & 1 & 1 \\
E2 & 1 & 0 \\
E3 & 0 & 1 \\
\end{array}
[/math]

Costruzione dettagliata:

Studente	P1	P2	Spiegazione
E1	1	1	Può lavorare a entrambi i progetti
E2	1	0	Solo P1 disponibile
E3	0	1	Solo P2 disponibile

Verifica Accoppiamento Perfetto

Parametri chiave:

[math]
\begin{aligned}
|U| &= 3 \quad \text{(studenti)} \\
|V| &= 2 \quad \text{(progetti)} \\
\end{aligned}
[/math]

Poiché [math]3 \neq 2[/math], non esiste un accoppiamento perfetto che soddisfi tutte queste condizioni contemporaneamente:

1. Tutti e 3 gli studenti assegnati
2. Entrambi i progetti assegnati
3. Nessuna condivisione di progetti/studenti

Miglior accoppiamento possibile:

Possiamo assegnare al massimo 2 studenti a 2 progetti distinti:

• Opzione 1: E2→P1 e E3→P2 (E1 non assegnato)
• Opzione 2: E1→P1 e E3→P2 (E2 non assegnato)
• Opzione 3: E1→P2 e E2→P1 (E3 non assegnato)

Conclusione

Pubblicità