Nel vasto e interconnesso mondo che ci circonda, dalle reti sociali alle infrastrutture di trasporto, dai circuiti elettronici alle relazioni biologiche, i grafi sono uno strumento matematico fondamentale per modellare le connessioni e le relazioni tra entità. Ma come possiamo rappresentare e analizzare in modo efficiente queste strutture complesse?
È qui che entrano in gioco le matrici di adiacenza. Una matrice di adiacenza è una potente rappresentazione tabellare di un grafo, capace di codificare la presenza (o l’assenza) e, in alcuni casi, il “costo” o la “forza” delle connessioni tra i nodi. Lavorare con le matrici di adiacenza non è solo una competenza teorica; è essenziale per chiunque voglia implementare algoritmi su grafi, risolvere problemi di ottimizzazione o comprendere a fondo le proprietà strutturali delle reti.
Comprendere il legame tra la rappresentazione matriciale e la struttura visiva o le proprietà algoritmiche di un grafo richiede pratica. Questo articolo è pensato proprio per offrirti la pratica necessaria. Abbiamo raccolto 6 esercizi sulle matrici di adiacenza, selezionati con cura per guidarti attraverso concetti di base e avanzati.
Gli esercizi sono presentati in ordine di difficoltà crescente e, cosa fondamentale, ciascuno è accompagnato dalla sua soluzione completa e da una spiegazione dettagliata passo passo. Non ci limiteremo a mostrarti il risultato, ma approfondiremo sia l’aspetto matematico dietro i calcoli (come la moltiplicazione di matrici o l’interpretazione dei valori) sia il fondamento teorico che collega la matrice alle proprietà del grafo (come gradi, cammini, connettività, bipartizione e persino gli autovalori).
👉Matrici di Adiacenza: Guida Completa e 10 Applicazioni Chiave (Informatica, Business e oltre)
Esercizio 1 (Base)
Testo:
Data la matrice di adiacenza [math]A[/math] di un grafo non orientato:
[math]A=\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 0
\end{bmatrix}[/math]
a) Disegna il grafo corrispondente.
b) Determina il grado di ogni nodo.
Soluzione:
La matrice è [math]3 \times 3[/math], quindi il grafo ha 3 nodi. Chiamiamoli 1, 2, e 3, corrispondenti alle righe/colonne.
a) Grafo corrispondente:
La matrice è simmetrica ([math]A_{ij} = A_{ji}[/math]), il che conferma che il grafo non è orientato (gli archi non hanno direzione).
Interpretiamo i valori:
- [math]A_{11}=0[/math]: nessun cappio sul nodo 1.
- [math]A_{12}=1[/math]: c’è un arco tra il nodo 1 e il nodo 2. ([math]A_{21}=1[/math] conferma questo per un grafo non orientato).
- [math]A_{13}=0[/math]: nessun arco tra il nodo 1 e il nodo 3.
- [math]A_{22}=0[/math]: nessun cappio sul nodo 2.
- [math]A_{23}=1[/math]: c’è un arco tra il nodo 2 e il nodo 3. ([math]A_{32}=1[/math] conferma questo).
- [math]A_{33}=0[/math]: nessun cappio sul nodo 3.
Descrizione testuale del grafo: Tre nodi (1, 2, 3) con un arco tra 1 e 2 e un arco tra 2 e 3. Il nodo 1 e 3 non sono direttamente connessi.
1 — 2 — 3
b) Grado dei nodi:
In un grafo non orientato, il grado di un nodo è il numero di archi incidenti su di esso. Questo corrisponde alla somma degli 1 nella sua riga (o colonna) nella matrice di adiacenza.
- Nodo 1: Somma riga 1 = [math]0+1+0 = 1[/math]. Grado 1 (solo arco con 2).
- Nodo 2: Somma riga 2 = [math]1+0+1 = 2[/math]. Grado 2 (archi con 1 e 3).
- Nodo 3: Somma riga 3 = [math]0+1+0 = 1[/math]. Grado 1 (solo arco con 2).
Risposta: Il grafo è una catena di 3 nodi. I gradi sono: Grado(1)=1, Grado(2)=2, Grado(3)=1.
👉Introduzione alla Teoria dei Grafi: Concetti e Applicazioni
Esercizio 2 (Base)
Testo:
Data la matrice di adiacenza [math]B[/math] di un grafo orientato:
[math]B=\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}[/math]
a) Disegna il grafo.
b) Determina i gradi uscenti e entranti di ogni nodo.
Soluzione:
La matrice è [math]3 \times 3[/math], quindi il grafo ha 3 nodi (1, 2, 3). Poiché è un grafo orientato, [math]B_{ij}=1[/math] significa un arco diretto da [math]i[/math] a [math]j[/math].
a) Grafo corrispondente:
Interpretiamo i valori [math]B_{ij}=1[/math]:
- [math]B_{12}=1[/math]: arco orientato da 1 a 2 (1 → 2).
- [math]B_{23}=1[/math]: arco orientato da 2 a 3 (2 → 3).
- [math]B_{31}=1[/math]: arco orientato da 3 a 1 (3 → 1).
Gli altri valori sono 0, indicando l’assenza di altri archi diretti tra queste coppie di nodi.
Descrizione testuale del grafo: Tre nodi (1, 2, 3) con un arco da 1 a 2, un arco da 2 a 3, e un arco da 3 a 1. Formano un ciclo orientato.
1 → 2 → 3 → 1
b) Gradi:
In un grafo orientato, distinguiamo tra grado uscente e grado entrante.
- Grado uscente: Somma degli 1 nella riga del nodo (archi che partono dal nodo).
- Grado entrante: Somma degli 1 nella colonna del nodo (archi che arrivano al nodo).
Gradi uscenti:
- Nodo 1: Somma riga 1 = [math]0+1+0 = 1[/math]. Grado uscente 1 (solo 1→2).
- Nodo 2: Somma riga 2 = [math]0+0+1 = 1[/math]. Grado uscente 1 (solo 2→3).
- Nodo 3: Somma riga 3 = [math]1+0+0 = 1[/math]. Grado uscente 1 (solo 3→1).
Gradi entranti:
- Nodo 1: Somma colonna 1 = [math]0+0+1 = 1[/math]. Grado entrante 1 (da 3→1).
- Nodo 2: Somma colonna 2 = [math]1+0+0 = 1[/math]. Grado entrante 1 (da 1→2).
- Nodo 3: Somma colonna 3 = [math]0+1+0 = 1[/math]. Grado entrante 1 (da 2→3).
Risposta: Il grafo è un ciclo orientato 1 → 2 → 3 → 1. Grado uscente per ogni nodo = 1. Grado entrante per ogni nodo = 1.
Esercizio 3 (Intermedio)
Testo:
Data la matrice di adiacenza [math]C[/math] di un grafo non orientato:
[math]C=\begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}[/math]
a) Verifica se il grafo è connesso.
b) Trova il numero di cammini di lunghezza 2 tra i nodi 1 e 4.
Soluzione:
La matrice è [math]4 \times 4[/math], quindi il grafo ha 4 nodi (1, 2, 3, 4). È non orientato (matrice simmetrica).
a) Connessione:
Un grafo non orientato è connesso se per ogni coppia di nodi distinti [math]i[/math] e [math]j[/math], esiste un cammino che li collega. Possiamo analizzare le connessioni dalla matrice:
- Nodo 1 è connesso a 2 e 3.
- Nodo 2 è connesso a 1, 3 e 4.
- Nodo 3 è connesso a 1 e 2.
- Nodo 4 è connesso solo a 2.
Dato che il nodo 4 è connesso al nodo 2, e il nodo 2 è connesso a 1 e 3, il nodo 4 può “raggiungere” i nodi 1 e 3 passando per il nodo 2 (4 — 2 — 1 e 4 — 2 — 3). Poiché tutti i nodi possono raggiungere tutti gli altri (direttamente o indirettamente), il grafo è connesso.
Descrizione testuale del grafo: Nodi 1, 2, 3, 4. Archi tra 1-2, 1-3, 2-3, 2-4.
1 — 2 — 4
| /
3 —/
Conclusione: Il grafo è connesso.
b) Cammini di lunghezza 2:
Il numero di cammini di lunghezza [math]k[/math] tra il nodo [math]i[/math] e il nodo [math]j[/math] in un grafo (orientato o non orientato) è dato dall’elemento [math](i,j)[/math] della matrice di adiacenza elevata alla potenza [math]k[/math] ([math]C^k[/math]).
Vogliamo il numero di cammini di lunghezza 2 tra il nodo 1 e il nodo 4, quindi dobbiamo calcolare l’elemento [math](1,4)[/math] della matrice [math]C^2 = C \times C[/math].
L’elemento [math](C^2)_{14}[/math] si ottiene moltiplicando la prima riga di [math]C[/math] per la quarta colonna di [math]C[/math]:
[math]
(C^2)_{14} = \sum_{k=1}^{4} C_{1k} \cdot C_{k4} \\
= C_{11} \cdot C_{14} + C_{12} \cdot C_{24} + C_{13} \cdot C_{34} + C_{14} \cdot C_{44}
[/math]
Dalla matrice [math]C[/math]: [math]C_{11}=0, C_{12}=1, C_{13}=1, C_{14}=0[/math] (prima riga) e [math]C_{14}=0, C_{24}=1, C_{34}=0, C_{44}=0[/math] (quarta colonna).
[math]
(C^2)_{14} = (0 \cdot 0) + (1 \cdot 1) + (1 \cdot 0) + (0 \cdot 0) \\
= 0 + 1 + 0 + 0 \\
= 1
[/math]
Interpretazione: C’è esattamente [math]1[/math] cammino di lunghezza 2 dal nodo 1 al nodo 4. Questo cammino è [math]1 \to 2 \to 4[/math] (passa per il nodo 2).
Risposta: Il grafo è connesso. C’è 1 cammino di lunghezza 2 tra i nodi 1 e 4.
Esercizio 4 (Intermedio)
Testo:
Data la matrice di adiacenza [math]D[/math] di un grafo pesato (non orientato):
[math]D=\begin{bmatrix}
0 & 3 & 0 & 0 \\
3 & 0 & 2 & 1 \\
0 & 2 & 0 & 4 \\
0 & 1 & 4 & 0
\end{bmatrix}[/math]
a) Rappresenta il grafo.
b) Trova il cammino minimo (con costo totale minimo) tra i nodi 1 e 4 usando l’algoritmo di Dijkstra.
Soluzione:
La matrice è [math]4 \times 4[/math] e simmetrica, rappresentando un grafo non orientato con 4 nodi (1, 2, 3, 4) e archi pesati (i valori diversi da 0 rappresentano i pesi/costi).
a) Grafo pesato:
Archi e pesi ([math]D_{ij}[/math] è il peso dell’arco tra [math]i[/math] e [math]j[/math]):
- 1-2 con peso [math]D_{12} = 3[/math].
- 2-3 con peso [math]D_{23} = 2[/math].
- 2-4 con peso [math]D_{24} = 1[/math].
- 3-4 con peso [math]D_{34} = 4[/math].
Descrizione testuale del grafo: Nodi 1, 2, 3, 4. Arco tra 1 e 2 (peso 3), tra 2 e 3 (peso 2), tra 2 e 4 (peso 1), tra 3 e 4 (peso 4).
1 --(3)-- 2 --(1)-- 4
| /
(2) (4)
| /
3 —/
b) Algoritmo di Dijkstra (per trovare il cammino minimo dal nodo 1 al nodo 4):
Inizializziamo le distanze minime conosciute da nodo 1 a tutti gli altri nodi. Le distanze iniziali sono 0 per il nodo di partenza (1) e infinito ([math]\infty[/math]) per tutti gli altri nodi non ancora visitati.
Distanze = [d(1), d(2), d(3), d(4)] = [0, [math]\infty[/math], [math]\infty[/math], [math]\infty[/math]]. Insieme dei nodi visitati = {}.
Passi:
- Visita nodo 1: È il nodo non visitato con la distanza minima attuale (0). Mark 1 come visitato. Aggiorna le distanze dei suoi vicini (2) se il nuovo cammino è più breve.
- Vicino 2: d(1) + peso(1,2) = [math]0 + 3 = 3[/math]. Siccome 3 < [math]\infty[/math], aggiorna d(2) = 3. Predecessore(2) = 1.
Nodi visitati = {1}. Distanze = [0, 3, [math]\infty[/math], [math]\infty[/math]].
- Visita nodo 2: È il nodo non visitato con la distanza minima attuale (3). Mark 2 come visitato. Aggiorna le distanze dei suoi vicini (1, 3, 4).
- Vicino 1: già visitato. Skip.
- Vicino 3: d(2) + peso(2,3) = [math]3 + 2 = 5[/math]. Siccome 5 < [math]\infty[/math], aggiorna d(3) = 5. Predecessore(3) = 2.
- Vicino 4: d(2) + peso(2,4) = [math]3 + 1 = 4[/math]. Siccome 4 < [math]\infty[/math], aggiorna d(4) = 4. Predecessore(4) = 2.
Nodi visitati = {1, 2}. Distanze = [0, 3, 5, 4].
- Visita nodo 4: È il nodo non visitato con la distanza minima attuale (4). Mark 4 come visitato. Aggiorna le distanze dei suoi vicini (2, 3).
- Vicino 2: già visitato. Skip.
- Vicino 3: d(4) + peso(4,3) = [math]4 + 4 = 8[/math]. Siccome 8 > 5 (la distanza attuale di 3), non aggiornare d(3).
Nodi visitati = {1, 2, 4}. Distanze = [0, 3, 5, 4]. Abbiamo raggiunto il nodo destinazione 4 e la sua distanza minima è stata finalizzata.
- Visita nodo 3: È l’ultimo nodo non visitato con la distanza minima attuale (5). Mark 3 come visitato. Aggiorna i vicini (2, 4). Già visitati, nessun miglioramento.
La distanza minima dal nodo 1 al nodo 4 è la distanza finale registrata per il nodo 4, che è 4.
Il cammino si ricostruisce dai predecessori: Predecessore(4)=2, Predecessore(2)=1. Il cammino è 1 → 2 → 4.
Risposta: Il cammino minimo tra i nodi 1 e 4 ha costo 4. Il cammino è 1 → 2 → 4.
Esercizio 5 (Avanzato)
Testo:
Data la matrice di adiacenza [math]E[/math] di un grafo non orientato:
[math]E=\begin{bmatrix}
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0
\end{bmatrix}[/math]
a) Mostra che il grafo è bipartito.
b) Trova gli autovalori di [math]E[/math] e verifica se il grafo è regolare.
Soluzione:
La matrice è [math]4 \times 4[/math] e simmetrica, rappresentando un grafo non orientato con 4 nodi (1, 2, 3, 4).
a) Grafo bipartito:
Un grafo è bipartito se i suoi nodi possono essere divisi in due insiemi disgiunti ([math]V_1[/math] e [math]V_2[/math]) tali che ogni arco connette un nodo in [math]V_1[/math] a un nodo in [math]V_2[/math] (nessun arco all’interno dello stesso insieme).
Dalla matrice [math]E[/math], vediamo le connessioni:
- Nodo 1 è connesso a 2 e 4.
- Nodo 2 è connesso a 1 e 3.
- Nodo 3 è connesso a 2 e 4.
- Nodo 4 è connesso a 1 e 3.
Proviamo a dividere i nodi in due insiemi: Mettiamo il nodo 1 in [math]V_1[/math]. I suoi vicini (2 e 4) devono andare in [math]V_2[/math].
Set proposto: [math]V_1 = \{1, 3\}[/math], [math]V_2 = \{2, 4\}[/math].
Verifichiamo gli archi:
- Archi da V1: 1 — 2 (ok, 2 in V2), 1 — 4 (ok, 4 in V2), 3 — 2 (ok, 2 in V2), 3 — 4 (ok, 4 in V2).
- Non ci sono archi tra nodi all’interno di V1 (1-3 non connessi).
- Non ci sono archi tra nodi all’interno di V2 (2-4 non connessi).
Descrizione testuale del grafo: Nodi 1, 2, 3, 4. Archi tra 1-2, 1-4, 2-3, 3-4. Forma un ciclo di lunghezza 4 (1-2-3-4-1).
1 — 2
| |
4 — 3
Questo è un ciclo di lunghezza 4. Un grafo (connesso) è bipartito se e solo se non contiene cicli di lunghezza dispari. Questo grafo ha solo un ciclo di lunghezza 4 (pari).
Conclusione: Il grafo è bipartito con partizione [math]V_1 = \{1, 3\}[/math] e [math]V_2 = \{2, 4\}[/math].
b) Autovalori e regolarità:
Un grafo è regolare se tutti i suoi nodi hanno lo stesso grado.
Grado dei nodi dalla matrice E (somma per riga/colonna):
- Grado(1) = [math]0+1+0+1 = 2[/math].
- Grado(2) = [math]1+0+1+0 = 2[/math].
- Grado(3) = [math]0+1+0+1 = 2[/math].
- Grado(4) = [math]1+0+1+0 = 2[/math].
Tutti i nodi hanno grado 2. Quindi, il grafo è regolare.
Gli autovalori di una matrice [math]A[/math] sono i valori [math]\lambda[/math] tali che [math]A\mathbf{v} = \lambda \mathbf{v}[/math] per un vettore [math]\mathbf{v} \neq \mathbf{0}[/math] (autovettore). Si trovano risolvendo l’equazione caratteristica [math]\det(A – \lambda I) = 0[/math], dove [math]I[/math] è la matrice identità.
Per la matrice [math]E[/math]:
[math]
E – \lambda I = \begin{bmatrix}
-\lambda & 1 & 0 & 1 \\
1 & -\lambda & 1 & 0 \\
0 & 1 & -\lambda & 1 \\
1 & 0 & 1 & -\lambda
\end{bmatrix}
[/math]
Calcolare il determinante di questa matrice [math]4 \times 4[/math] porta a un polinomio caratteristico di grado 4. Per questo grafo specifico (un ciclo [math]C_4[/math]), gli autovalori sono noti.
Gli autovalori del ciclo [math]C_n[/math] sono dati da [math]\lambda_k = 2 \cos\left(\frac{2\pi k}{n}\right)[/math] per [math]k = 0, 1, \dots, n-1[/math]. Per [math]n=4[/math]:
- [math]k=0: \lambda_0 = 2 \cos(0) = 2 \cdot 1 = 2[/math].
- [math]k=1: \lambda_1 = 2 \cos(\frac{2\pi}{4}) = 2 \cos(\frac{\pi}{2}) = 2 \cdot 0 = 0[/math].
- [math]k=2: \lambda_2 = 2 \cos(\frac{4\pi}{4}) = 2 \cos(\pi) = 2 \cdot (-1) = -2[/math].
- [math]k=3: \lambda_3 = 2 \cos(\frac{6\pi}{4}) = 2 \cos(\frac{3\pi}{2}) = 2 \cdot 0 = 0[/math].
Gli autovalori sono [math]2, 0, -2, 0[/math]. L’autovalore massimo è [math]2[/math], che è uguale al grado dei nodi, una proprietà dei grafi regolari.
Risposta: Il grafo è bipartito. Il grafo è regolare (grado 2). Gli autovalori della matrice [math]E[/math] sono [math]2, 0, -2[/math] (con 0 di molteplicità 2).
Esercizio 6 (Avanzato)
Testo:
Data la matrice di adiacenza [math]F[/math] di un grafo orientato:
[math]F=\begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{bmatrix}[/math]
a) Determina se il grafo è fortemente connesso.
b) Trova la matrice delle raggiungibilità [math]R[/math].
Soluzione:
La matrice è [math]4 \times 4[/math] e non simmetrica, rappresentando un grafo orientato con 4 nodi (1, 2, 3, 4).
a) Fortemente connesso:
Un grafo orientato è fortemente connesso se per ogni coppia di nodi distinti [math]i[/math] e [math]j[/math], esiste un cammino orientato da [math]i[/math] a [math]j[/math] E un cammino orientato da [math]j[/math] a [math]i[/math].
Dal testo della matrice [math]F_{ij}=1[/math]:
- [math]F_{12}=1[/math]: 1 → 2
- [math]F_{23}=1[/math]: 2 → 3
- [math]F_{34}=1[/math]: 3 → 4
- [math]F_{41}=1[/math]: 4 → 1
Descrizione testuale del grafo: Nodi 1, 2, 3, 4. Archi orientati 1→2, 2→3, 3→4, 4→1. Questo forma un ciclo orientato che include tutti i nodi.
1 → 2 → 3 → 4 → 1
In un ciclo orientato completo, ogni nodo può raggiungere ogni altro nodo (seguendo la direzione degli archi nel ciclo), e ogni altro nodo può raggiungere il nodo di partenza (sempre seguendo il ciclo). Quindi, il grafo è fortemente connesso.
Conclusione: Il grafo è fortemente connesso.
b) Matrice delle raggiungibilità [math]R[/math]:
La matrice delle raggiungibilità (o matrice di connettività) [math]R[/math] è una matrice binaria dove [math]R_{ij}=1[/math] se il nodo [math]i[/math] può raggiungere il nodo [math]j[/math] (esiste un cammino di qualsiasi lunghezza da [math]i[/math] a [math]j[/math]), e [math]R_{ij}=0[/math] altrimenti.
Si può calcolare [math]R[/math] come la somma della matrice identità [math]I[/math] e le potenze della matrice di adiacenza [math]F[/math] fino a [math]F^{n-1}[/math] (dove [math]n[/math] è il numero di nodi), e poi binarizzare la matrice risultante (sostituire i valori positivi con 1). Per [math]n=4[/math]:
[math]R = I + F + F^2 + F^3[/math]
(Se il grafo avesse cicli più lunghi, si potrebbe aver bisogno di potenze maggiori, ma per un grafo fortemente connesso fino a [math]n-1[/math] è sufficiente per i cammini diretti).
Calcoliamo le potenze di [math]F[/math]:
[math]
F^2 = F \times F = \begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{bmatrix}
= \begin{bmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}
[/math]
[math]F^2_{ij}=1[/math] indica un cammino di lunghezza 2 da [math]i[/math] a [math]j[/math]. (1→3, 2→4, 3→1, 4→2).
[math]
F^3 = F^2 \times F = \begin{bmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{bmatrix}
= \begin{bmatrix}
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}
[/math]
[math]F^3_{ij}=1[/math] indica un cammino di lunghezza 3 da [math]i[/math] a [math]j[/math]. (1→4, 2→1, 3→2, 4→3).
Ora sommiamo le matrici [math]I, F, F^2, F^3[/math]:
[math]
I = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}
[/math]
[math]
R = I + F + F^2 + F^3 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}
+ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}
+ \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}
+ \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}
[/math]
[math]
R = \begin{bmatrix}
1+0+0+0 & 0+1+0+0 & 0+0+1+0 & 0+0+0+1 \\
0+0+0+1 & 1+0+0+0 & 0+1+0+0 & 0+0+1+0 \\
0+0+1+0 & 0+0+0+1 & 1+0+0+0 & 0+0+0+1 \\
0+1+0+0 & 0+0+1+0 & 0+0+0+1 & 1+0+0+0
\end{bmatrix}
= \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{bmatrix}
[/math]
La matrice risultante ha tutti 1 (tranne la diagonale per [math]I[/math] se non ci fossero cappi, ma la somma rende tutti 1). Binarizzando (se ci fossero stati valori maggiori di 1, li sostituiremmo con 1), otteniamo:
[math]
R = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{bmatrix}
[/math]
Poiché la matrice [math]R[/math] ha tutti 1, significa che ogni nodo può raggiungere ogni altro nodo (inclusi sé stessi via cammini di lunghezza 0 o cicli). Questo conferma che il grafo è fortemente connesso.
Risposta: Il grafo è fortemente connesso. La matrice delle raggiungibilità [math]R[/math] ha tutti i valori uguali a 1.
(102)
Altri articoli nella categoria "Le matrici"
- Classificazione delle Coniche con Autovalori e Autovettori: Teoria ed Esercizi Svolti
- Diagonalizzazione di una Matrice: Guida Pratica con 6 Esercizi Svolti e Applicazioni
- Matrici non diagonalizzabili: teoria, metodo in 3 passi ed esercizi svolti per riconoscere il punto critico
- Matrici e Microeconomia: Equilibrio, Elasticità e Modello di Leontief (Esercizi Svolti)
- Rango di una Matrice: 7 Esercizi Svolti e Spiegati (da Facile a Difficile)
- Le Trasformazioni Affini spiegate: Geometria, Matrici e Applicazioni Reali
- Trasformazioni Geometriche e Matrici: Guida Pratica al Calcolo dell’Area e Determinanti
- Matrici a Gradini ed Eliminazione di Gauss: Esercizi Svolti e Guida Pratica
- Autovalori e Autovettori: Guida Intuitiva al Cuore dell’Algebra Lineare e dell’IA
- Guida Geometrica alle Trasformazioni Lineari: Visualizzare le Matrici con Python