Calcolatore di Matrice di Adiacenza

Calcolatore di Matrice di Adiacenza

Il Calcolatore di Matrice di Adiacenza è un'utilità di teoria dei grafi che converte tra le tre rappresentazioni canoniche dei grafi — matrice di adiacenza, elenco archi e elenco adiacenza — e arricchisce il risultato con l'analisi strutturale: sequenza dei gradi, densità del grafo, componenti connesse e potenze della matrice. Rileva automaticamente se l'input descrive un grafo orientato o non orientato e genera una visualizzazione SVG interattiva per ogni risultato.

Cos'è una Matrice di Adiacenza?

Dato un grafo G = (V, E) con n vertici, la sua matrice di adiacenza è la matrice quadrata n × n A il cui elemento A[i][j] è 1 se esiste un arco dal vertice i al vertice j, e 0 altrimenti.

Per un grafo non orientato, la matrice di adiacenza è sempre simmetrica: ogni arco {u, v} contribuisce sia ad A[u][v] = 1 che ad A[v][u] = 1. Per un grafo orientato (digrafo), la matrice può essere asimmetrica, riflettendo la direzione di ogni arco.

Tre Rappresentazioni — Scegli Quella Adatta al Tuo Problema

Metriche Chiave Calcolate

Sequenza dei Gradi

Per i grafi non orientati, il grado di un vertice è il numero di archi incidenti ad esso (con i self-loop che contano due volte). Per i grafi orientati, ogni vertice ha un grado in entrata (archi entranti) e un grado in uscita (archi uscenti). L'elenco ordinato dei gradi è un classico invariante del grafo utilizzato nei test di isomorfismo e nel teorema di realizzabilità di Erdős–Gallai.

Densità del Grafo

La densità misura quanto un grafo sia "pieno" rispetto al numero massimo di archi possibili su n vertici.

Una densità pari a 0 significa assenza di archi, 1 significa che il grafo è completo e valori inferiori a 0,1 indicano tipicamente un grafo sparso dove un elenco di adiacenza è più efficiente in termini di spazio rispetto a una matrice.

Componenti Connesse

Una componente connessa è un sottoinsieme massimale di vertici tale che ogni coppia sia unita da un cammino. Per i grafi orientati, questo calcolatore riporta le componenti debolmente connesse (ignorando la direzione delle frecce) — gli stessi sottoinsiemi che si otterrebbero trattando ogni arco come un arco non orientato.

Potenze della Matrice (A², A³ ... )

Un teorema fondamentale della teoria dei grafi algebrici afferma che l'elemento (i, j) di A^k è uguale al numero di cammini di lunghezza esattamente k dal vertice i al vertice j. Di conseguenza:

• A²[i][i] è uguale al grado del vertice i (non orientato), poiché un cammino di lunghezza 2 da i a se stesso è "vai verso un vicino e torna indietro".
• La traccia di A³ divisa per 6 conta i triangoli in un grafo non orientato.
• Se Aⁿ⁻¹ non ha elementi nulli, il grafo è connesso.

Formati di Input Accettati

1. Elenco archi

Un arco per riga o separati da virgola. Funziona con qualsiasi separatore: A-B, A B, A,B, A->B, A--B. Usa -> se desideri forzare l'interpretazione orientata.

2. Elenco adiacenza

Una riga per vertice, nella forma vertice: vicino1, vicino2, .... L'ordine non conta; i vertici mancanti vengono aggiunti automaticamente dagli elenchi dei vicini.

3. Matrice di adiacenza

Una riga per riga con valori 0/1 separati da spazi o virgole. La matrice deve essere quadrata. Opzionalmente, fornisci etichette personalizzate nel campo Etichette della matrice (altrimenti verranno usate A, B, C…).

Come Usare Questo Calcolatore

1. Scegli un formato di input usando il selettore a schede: elenco archi, elenco adiacenza o matrice di adiacenza.
2. Incolla o digita il tuo grafo nell'area di testo. Per l'input della matrice, aggiungi etichette opzionali nel campo Etichette della matrice.
3. Seleziona il tipo di grafo — lascia su Rilevamento automatico e il calcolatore dedurrà l'orientamento dalle frecce (->) o dalla simmetria della matrice. Forza su Orientato o Non orientato se desideri ignorare il rilevamento.
4. Clicca su Converti e Analizza Grafo. La pagina dei risultati mostra la matrice di adiacenza, un rendering SVG interattivo, le altre due rappresentazioni testuali, le statistiche sui gradi, le componenti connesse e le matrici dei cammini A² e A³ quando il grafo è abbastanza piccolo.
5. Passa il mouse su una riga della matrice o su un nodo del grafo per illuminare la riga/colonna corrispondente e gli archi incidenti — una prova visiva istantanea che ogni formato codifica le stesse informazioni.

Esempio Svolto

Considera un grafo non orientato sui vertici {A, B, C, D} con archi AB, BC, CA, CD. La matrice di adiacenza è:

Fatti chiave derivati dal calcolatore:

• Simmetrica? Sì — conferma che non è orientato.
• Sequenza dei gradi: (3, 2, 2, 1) — il vertice C è l'hub.
• Densità: 2·4 / (4·3) = 0.667 — un grafo moderatamente denso.
• Connesso? Sì, singola componente.
• Triangoli: esattamente uno (A–B–C), come confermato da tr(A³) = 6.

Applicazioni Comuni

• Analisi delle reti sociali — grafi di amicizia/follower, centralità.
• Grafi del Web e citazioni — PageRank e HITS lavorano direttamente su A e A^T.
• Routing e reti — percorso minimo, taglio minimo, flusso massimo.
• Chimica — grafi molecolari con atomi come vertici e legami come archi.
• Pianificazione e risoluzione delle dipendenze — grafi aciclici orientati (DAG) nei sistemi di build.
• Catene di Markov — matrici stocastiche per riga derivate da grafi codificano probabilità di transizione.

Domande Frequenti

Cos'è una matrice di adiacenza?

Una matrice di adiacenza è una matrice quadrata n × n utilizzata per rappresentare un grafo finito. Ogni cella A[i][j] è 1 se esiste un arco dal vertice i al vertice j, e 0 altrimenti. Per i grafi non orientati la matrice è simmetrica, quindi A[i][j] = A[j][i]. La matrice rende facile verificare se due vertici sono connessi in tempo costante, e le potenze della matrice codificano il numero di cammini tra i vertici.

Come posso capire se un grafo è orientato dalla sua matrice di adiacenza?

Se la matrice di adiacenza è simmetrica, ovvero A[i][j] è uguale ad A[j][i] per ogni coppia di indici, il grafo non è orientato. Se esiste almeno una coppia in cui A[i][j] differisce da A[j][i], il grafo è orientato. Questo calcolatore esegue automaticamente il controllo di simmetria quando si sceglie l'opzione Rilevamento automatico.

Cosa rappresenta la k-esima potenza di una matrice di adiacenza?

L'elemento (i, j) di A^k conta il numero di cammini di lunghezza esattamente k dal vertice i al vertice j. Ad esempio, A²[i][j] è il numero di percorsi in 2 passaggi, che equivale al numero di vicini comuni tra i e j nei grafi non orientati. Questa proprietà viene utilizzata negli algoritmi per il conteggio dei triangoli, la raggiungibilità e i calcoli di tipo PageRank.

Cos'è la densità del grafo?

La densità del grafo è il rapporto tra il numero di archi presenti e il numero massimo possibile di archi. Per un grafo semplice non orientato con n vertici, densità = 2m / (n(n-1)). Per un grafo orientato, densità = m / (n(n-1)). Una densità prossima a 0 indica un grafo sparso; una densità di 1 indica un grafo completo.

In che modo una matrice di adiacenza differisce da un elenco di adiacenza?

Una matrice di adiacenza memorizza la connettività per ogni coppia di vertici utilizzando n² bit, rendendo la ricerca del vicino O(1) ma l'uso della memoria O(n²). Un elenco di adiacenza memorizza solo i vicini effettivi di ciascun vertice, fornendo una memoria O(n + m), che è molto più piccola per i grafi sparsi, ma la ricerca del vicino richiede una scansione lineare. Le matrici sono migliori per i grafi densi e le operazioni di algebra matriciale; gli elenchi sono migliori per i grafi sparsi e gli algoritmi di attraversamento come BFS/DFS.

Questo strumento può gestire grafi pesati?

L'attuale calcolatore si concentra su matrici di adiacenza non pesate con voci 0/1. Se si incolla una matrice con pesi numerici diversi da zero, ogni cella diversa da zero viene trattata come 1 per l'analisi strutturale. Per i calcoli sui grafi pesati come il percorso minimo, considera uno strumento specifico per grafi pesati.

Ulteriori Letture

• Matrice di adiacenza — Wikipedia
• Grado di un vertice — Wikipedia
• Graph density — Wikipedia (Inglese)
• Componenti connesse — Wikipedia