Cosa sono le matrici di adiacenza?
Immagina di avere una mappa di città collegate tra loro da strade. Una matrice di adiacenza è come una tabella che ti dice quali città sono direttamente collegate e, a volte, quanto è “distante” un collegamento.
Più formalmente, una matrice di adiacenza è un modo per rappresentare un grafo (un insieme di nodi collegati da archi) usando una tabella quadrata. Le righe e le colonne della tabella corrispondono ai nodi del grafo, e il valore in una cella della tabella indica se esiste un arco tra i due nodi corrispondenti.
Come funziona?
-
Costruzione della matrice:
- Se il tuo grafo ha n nodi, la matrice di adiacenza sarà una tabella n x n.
- Etichetta le righe e le colonne della matrice con i nomi dei tuoi nodi.
- Metti un valore nella cella corrispondente alla riga i e colonna j per indicare se c’è un arco dal nodo i al nodo j.
-
Valori nelle celle:
- Grafi non pesati:
- 1: indica che c’è un arco tra i due nodi.
- 0: indica che non c’è un arco.
- Grafi pesati:
- Un numero: indica il “peso” dell’arco (potrebbe essere la distanza, il costo, ecc.).
- Infinito (∞) o un valore speciale: indica che non c’è un arco.
- Grafi non pesati:
Esempio
Considera un grafo con 4 nodi (A, B, C, D) e alcuni collegamenti:
- A è collegato a B e C.
- B è collegato a C e D.
- C è collegato a D.
La matrice di adiacenza per questo grafo sarebbe:
A B C D
A 0 1 1 0
B 0 0 1 1
C 0 0 0 1
D 0 0 0 0
Tipi di grafi
- Grafi diretti: Gli archi hanno una direzione (ad esempio, una strada a senso unico). La matrice di adiacenza può non essere simmetrica.
- Grafi non diretti: Gli archi non hanno una direzione (ad esempio, una strada a doppio senso). La matrice di adiacenza è sempre simmetrica.
Tipi di Grafi e loro Rappresentazione
Grafo Non Diretto Non Pesato
Esempio di un grafo semplice con 4 vertici:
Grafo:
0 -- 1 -- 2
| \ |
3 ------ 2
Matrice di Adiacenza:
0 1 2 3
0 | 0 1 0 1 |
1 | 1 0 1 0 |
2 | 0 1 0 1 |
3 | 1 0 1 0 |
Grafo Diretto Pesato
Grafo:
0 -3→ 1 -2→ 2
↑ ↓ ↓
5 4 1
3 ←1- 4 ←3- 5
Matrice di Adiacenza:
0 1 2 3 4 5
0 | 0 3 ∞ ∞ ∞ ∞ |
1 | ∞ 0 2 ∞ 4 ∞ |
2 | ∞ ∞ 0 ∞ ∞ 1 |
3 | 5 ∞ ∞ 0 ∞ ∞ |
4 | ∞ ∞ ∞ 1 0 ∞ |
5 | ∞ ∞ ∞ ∞ 3 0 |
Operazioni sulle Matrici di Adiacenza
Calcolo del Grado dei Vertici
- In un grafo non diretto: somma degli elementi della riga/colonna
- In un grafo diretto:
- Grado in entrata: somma della colonna
- Grado in uscita: somma della riga
Verifica dell’Esistenza di un Percorso
- Se A[i][j] ≠ 0, esiste un percorso diretto da i a j
- Se (A²)[i][j] ≠ 0, esiste un percorso di lunghezza 2 da i a j
- Se (A^k)[i][j] ≠ 0, esiste un percorso di lunghezza k da i a j
Verifica dell’esistenza di un percorso
La potenza delle matrici di adiacenza risiede anche nella loro capacità di rivelare l’esistenza di percorsi tra nodi, non solo collegamenti diretti.
Percorso diretto (lunghezza 1)
Se A[i][j] ≠ 0, esiste un percorso diretto da i a j
Questo è il caso più semplice. Se il valore nella cella (i, j) della matrice è diverso da zero, significa che c’è un arco che va direttamente dal nodo i al nodo j.
Percorso di lunghezza 2
Se (A²)[i][j] ≠ 0, esiste un percorso di lunghezza 2 da i a j
Qui entriamo nel vivo. A² rappresenta il prodotto matriciale di A con se stessa. L’elemento (i, j) di A² è ottenuto moltiplicando la riga i di A per la colonna j di A. Se questo risultato è diverso da zero, significa che esiste almeno un percorso di lunghezza 2 che parte dal nodo i e arriva al nodo j. In altre parole, c’è un nodo intermedio k tale che esiste un arco da i a k e un arco da k a j.
Percorso di lunghezza k
Se (A^k)[i][j] ≠ 0, esiste un percorso di lunghezza k da i a j
Generalizzando, A^k (A elevato alla potenza k) rappresenta il prodotto matriciale di A con se stessa k volte. Se l’elemento (i, j) di A^k è diverso da zero, significa che esiste almeno un percorso di lunghezza k che parte dal nodo i e arriva al nodo j.
Esempio
Consideriamo un grafo con 4 nodi (A, B, C, D) e la seguente matrice di adiacenza:
A B C D A 0 1 0 0 B 0 0 1 0 C 0 0 0 1 D 1 0 0 0
A[A][B] = 1: esiste un percorso diretto da A a B.A²[A][C] = 1: esiste un percorso di lunghezza 2 da A a C (passando per B).A³[A][D] = 1: esiste un percorso di lunghezza 3 da A a D (passando per B e C).A⁴[A][A] = 1: esiste un percorso di lunghezza 4 da A ad A (passando per B, C e D).
Calcolare A², A³, ecc. può essere fatto manualmente per matrici piccole, ma per grafi più grandi è preferibile utilizzare un computer o una calcolatrice in grado di eseguire operazioni matriciali.
Osservazioni importanti
- L’esistenza di un percorso di lunghezza k non implica che non esistano percorsi più brevi tra gli stessi nodi.
- Se
(A^k)[i][j] = 0, significa che non esistono percorsi di lunghezza k tra i e j, ma potrebbero esserci percorsi di lunghezza diversa.
Un codice Python per calcolare la potenza di una matrice
Come abbiamo visto, le potenze della matrice di adiacenza ci forniscono informazioni preziose sull’esistenza di percorsi in un grafo. Per aiutarci in questi calcoli, possiamo utilizzare il seguente codice Python:
import numpy as np
def matrix_power():
try:
rows = int(input("Inserisci il numero di righe: "))
cols = int(input("Inserisci il numero di colonne: "))
matrix = []
for i in range(rows):
row = []
for j in range(cols):
while True:
try:
element = float(input(f"Inserisci l'elemento in posizione [{i+1},{j+1}]: "))
row.append(element)
break
except ValueError:
print("Errore: inserisci un numero valido.")
matrix.append(row)
matrix = np.array(matrix)
n = int(input("\nInserisci la potenza a cui vuoi elevare la matrice: "))
result = np.linalg.matrix_power(matrix, n)
print("\nLa matrice originale è:")
print(matrix)
print(f"\nLa matrice elevata alla {n} è:")
print(result)
except ValueError:
print("Errore: inserisci dimensioni di matrice valide (numeri interi).")
except np.linalg.LinAlgError:
print("Errore: la matrice deve essere quadrata per essere elevata a potenza.")
# Eseguiamo la funzione
matrix_power()
Obiettivi del codice
- Ricevere in input una matrice: L’utente fornisce le dimensioni (righe e colonne) e gli elementi di una matrice.
- Calcolare la potenza di una matrice: L’utente specifica un numero intero n, e il codice calcola la matrice elevata alla potenza n (ovvero, la matrice moltiplicata per se stessa n volte).
- Visualizzare i risultati: Vengono stampate sia la matrice originale che la matrice risultante dopo l’elevamento a potenza.
Modalità di utilizzo
-
Inserimento delle dimensioni della matrice: Il programma chiederà di inserire il numero di righe e il numero di colonne della matrice. Assicurarsi di inserire numeri interi validi.
-
Inserimento degli elementi della matrice: Successivamente, il programma chiederà di inserire gli elementi della matrice uno per volta, specificando la posizione (riga e colonna). Inserire un numero valido per ogni elemento.
-
Inserimento della potenza: Il programma chiederà di inserire la potenza a cui elevare la matrice. Inserire un numero intero.
-
Visualizzazione dei risultati: Il programma stamperà la matrice originale e la matrice elevata alla potenza specificata.
Ora che abbiamo visto come funzionano le matrici di adiacenza e quali sono le loro proprietà, passiamo a un esempio pratico di come implementarle in Python. Il seguente codice definisce una classe GrafoMatriceAdiacenza che permette di creare un grafo, aggiungere e rimuovere archi, calcolare il grado di un vertice e visualizzare la matrice di adiacenza corrispondente.
Esempio : Implementazione in Python
class GrafoMatriceAdiacenza:
def __init__(self, num_vertici):
self.V = num_vertici
self.grafo = [[0 for colonna in range(num_vertici)]
for riga in range(num_vertici)]
def aggiungi_arco(self, v1, v2, peso=1):
self.grafo[v1][v2] = peso
# Per grafi non diretti, decommentare la linea seguente:
# self.grafo[v2][v1] = peso
def rimuovi_arco(self, v1, v2):
self.grafo[v1][v2] = 0
# Per grafi non diretti, decommentare la linea seguente:
# self.grafo[v2][v1] = 0
def get_grado(self, vertice):
return sum(1 for i in range(self.V) if self.grafo[vertice][i] > 0)
def visualizza_matrice(self):
print("Matrice di adiacenza:")
for riga in self.grafo:
print(riga)
# Esempio di utilizzo
g = GrafoMatriceAdiacenza(4)
g.aggiungi_arco(0, 1)
g.aggiungi_arco(1, 2)
g.aggiungi_arco(2, 3)
g.visualizza_matrice() # Visualizza la matrice
print(f"Grado del vertice 1: {g.get_grado(1)}") #Stampa il grado del vertice 1
Questo output mostra la matrice di adiacenza che rappresenta il grafo creato. Puoi vedere chiaramente quali nodi sono collegati e, in questo caso, il peso predefinito (1) indica la presenza di un arco. Se avessi un grafo pesato, al posto di 1 vedresti il peso specifico dell’arco.
Utilizzo
Le matrici di adiacenza sono utili per:
- Rappresentare grafi in modo compatto.
- Implementare algoritmi sui grafi (ad esempio, ricerca di percorsi, calcolo di distanze).
- Analizzare le proprietà dei grafi.
Casi specifici e proprietà
- Grafi non diretti: La matrice di adiacenza di un grafo non diretto è sempre simmetrica. Questo significa che l’elemento nella riga i e colonna j (M[i][j]) è uguale all’elemento nella riga j e colonna i (M[j][i]). Questo perché se esiste un arco da un nodo i a un nodo j, esiste anche un arco dal nodo j al nodo i.
- Grafi non pesati: In un grafo non pesato, la matrice di adiacenza contiene solo valori 0 e 1. 1 indica la presenza di un arco tra due nodi, mentre 0 indica l’assenza di un arco.
- Grafi densi: Un grafo denso è un grafo in cui il numero di archi è vicino al massimo possibile (ogni nodo è connesso a quasi tutti gli altri nodi). La matrice di adiacenza di un grafo denso sarà “piena” di valori diversi da zero.
- Grafi sparsi: Un grafo sparso è un grafo in cui il numero di archi è molto inferiore al massimo possibile. La matrice di adiacenza di un grafo sparso conterrà molti zeri.
Esempi di Grafi Complessi e Matrici di Adiacenza
Grafi con pesi negativi
Consideriamo un grafo diretto con 4 nodi (A, B, C, D) e alcuni collegamenti, inclusi alcuni con peso negativo:
- A → B (peso: 2)
- A → C (peso: -1)
- B → C (peso: 3)
- B → D (peso: 1)
- C → D (peso: -2)
- D → A (peso: 4)
La matrice di adiacenza per questo grafo sarebbe:
A B C D
A 0 2 -1 0
B 0 0 3 1
C 0 0 0 -2
D 4 0 0 0
Questi grafi sono fondamentali per modellare scenari in cui le relazioni tra elementi possono avere un valore negativo. Ad esempio:
- Costi/Perdite: In una rete logistica, un peso negativo può rappresentare uno sconto, un guadagno o una riduzione di costo. In un circuito elettrico, può indicare una caduta di tensione.
- Penalità: In un gioco o in un sistema di valutazione, un peso negativo può rappresentare una penalità per una determinata azione o scelta.
- Flusso negativo: In una rete di distribuzione di liquidi, un peso negativo può indicare una direzione di flusso opposta a quella “standard”.
Grafi misti (con archi diretti e non diretti)
Rappresentare grafi misti con matrici di adiacenza richiede una convenzione. Possiamo usare:
- 1 per archi non diretti
- Il peso specifico per archi diretti
- 0 per l’assenza di un arco
Consideriamo un grafo con 4 nodi (A, B, C, D):
- A — B (non diretto)
- A → C (diretto, peso: 2)
- B → D (diretto, peso: 3)
- C — D (non diretto)
La matrice di adiacenza sarebbe:
A B C D
A 0 1 2 0
B 1 0 0 3
C 0 0 0 1
D 0 0 1 0
Questi grafi sono utili per modellare sistemi in cui le relazioni tra elementi possono essere sia unidirezionali che bidirezionali. Ad esempio:
Reti stradali: Alcune strade sono a senso unico (dirette), mentre altre sono a doppio senso (non dirette).
Reti sociali: Un’amicizia su Facebook è bidirezionale (non diretta), mentre un “follow” su Twitter è unidirezionale (diretto).
Relazioni commerciali: Un contratto di fornitura può essere unidirezionale (un’azienda fornisce beni a un’altra), mentre una partnership è bidirezionale.
Grafi con self-loop (archi che collegano un nodo a se stesso)
I self-loop sono semplici da rappresentare: basta inserire il peso (o 1 per grafi non pesati) nella cella corrispondente al nodo.
Consideriamo un grafo con 3 nodi (A, B, C):
- A → A (self-loop, peso: 2)
- A → B (peso: 3)
- B → C (peso: 1)
La matrice di adiacenza sarebbe:
A B C
A 2 3 0
B 0 0 1
C 0 0 0
Questi grafi sono utili per modellare situazioni in cui un elemento può avere una relazione con se stesso. Ad esempio:
- Dipendenze software: Un modulo software può dipendere da un altro modulo, ma anche da se stesso (self-loop).
- Processi iterativi: Un’attività in un processo può avere un ciclo di feedback che la influenza (self-loop).
- Stati di un sistema: Un sistema può transitare da uno stato a un altro, incluso se stesso (self-loop).
Esempio di grafo complesso
Consideriamo una rete stradale semplificata con città e strade a doppio senso (non dirette) e alcune strade a senso unico (dirette):
- Milano — Torino (non diretto)
- Torino → Lione (diretto, peso: 3)
- Lione — Parigi (non diretto)
- Parigi → Londra (diretto, peso: 2)
- Londra — Amsterdam (non diretto)
La matrice di adiacenza (usando 1 per strade non dirette e il peso per dirette) sarebbe:
Milano Torino Lione Parigi Londra Amsterdam Milano 0 1 0 0 0 0 Torino 1 0 3 0 0 0 Lione 0 0 0 1 0 0 Parigi 0 0 1 0 2 0 Londra 0 0 0 0 0 1 Amsterdam 0 0 0 0 1 0
Milano
|
1
Torino
/ \
3 |
/ \
Lione --- Parigi
|
2
|
Londra
|
1
|
Amsterdam
Utilizzodelle matrici di adiacenza in algoritmi sui grafi
Le matrici di adiacenza sono fondamentali in molti algoritmi sui grafi, tra cui:
- Algoritmo di Floyd-Warshall: Come hai detto, questo algoritmo utilizza una matrice di adiacenza per trovare i cammini minimi tra tutte le coppie di nodi in un grafo pesato, anche in presenza di archi con peso negativo (a differenza dell’algoritmo di Dijkstra). La matrice di adiacenza iniziale viene iterativamente aggiornata per includere informazioni sui percorsi minimi attraverso nodi intermedi.
- Algoritmo di Dijkstra: Anche se l’algoritmo di Dijkstra può essere implementato usando altre rappresentazioni del grafo (come le liste di adiacenza), una matrice di adiacenza può essere utile per grafi densi.
- Algoritmi di visita (BFS, DFS): Le matrici di adiacenza possono essere usate per implementare sia la visita in ampiezza (BFS) che la visita in profondità (DFS) di un grafo.
Vantaggi e svantaggi
- Vantaggi:
- Semplici da capire e implementare.
- Efficienti per verificare l’esistenza di un arco.
- Svantaggi:
- Richiedono molta memoria per grafi grandi.
- Inefficienti per grafi con pochi archi (grafi sparsi).
Esercizi Risolti
Esercizio 1
Problema:
Data la seguente matrice di adiacenza di un grafo non diretto,
0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0
determinare: a) Il numero di vertici b) Il numero di archi c) Il grado di ciascun vertice d) Se il grafo è connesso
Soluzione
a) Il numero di vertici è 4 (dimensione della matrice)
b) Il numero di archi è 5 (somma degli elementi della matrice diviso 2)
c) Gradi dei vertici:
- Vertice 0: grado 2
- Vertice 1: grado 3
- Vertice 2: grado 2
- Vertice 3: grado 3
- d) Il grafo è connesso poiché da ogni vertice è possibile raggiungere tutti gli altri
Esercizio 2
Problema: Costruire la matrice di adiacenza del seguente grafo pesato e diretto:
- Arco da 0 a 1 con peso 5
- Arco da 1 a 2 con peso 3
- Arco da 2 a 0 con peso 4
- Arco da 1 a 3 con peso 2
- Arco da 3 a 2 con peso 1
Soluzione:
0 1 2 3 0 | 0 5 0 0 | 1 | 0 0 3 2 | 2 | 4 0 0 0 | 3 | 0 0 1 0 |
🔗Matrici di Adiacenza in Python: Analisi e Applicazioni Pratiche per Reti Sociali e IoT
🔗Matrice di Adiacenza: Guida Completa con Esercizi Svolti Passo Passo
Bibliografia e Risorse Aggiuntive
- Introduction to Algorithms – Cormen, Leiserson, Rivest, Stein
- Graph Theory and Its Applications – Jonathan L. Gross, Jay Yellen
- Discrete Mathematics and Its Applications – Kenneth H. Rosen
