Calcolatore di Matrice di Adiacenza
Converti tra matrice di adiacenza, lista di archi e lista di adiacenza. Rileva automaticamente grafi diretti/non diretti, calcola sequenza dei gradi, densità, componenti connesse e potenze della matrice.
Il tuo ad blocker ci impedisce di mostrare annunci
MiniWebtool resta gratuito grazie agli annunci. Se questo strumento ti è stato utile, sostienici facendo l’upgrade per navigare senza annunci e avere più utilizzi giornalieri, oppure consenti MiniWebtool.com e ricarica.
- Consenti gli annunci per MiniWebtool.com, poi ricarica
- Oppure fai l’upgrade per niente annunci e limiti giornalieri più alti
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
| Rappresentazione | Spazio | Ricerca Arco | Elenco Vicini | Ideale per |
|---|---|---|---|---|
| Matrice di adiacenza | Θ(n²) | O(1) | Θ(n) | Grafi densi; algebra matriciale (potenze, autovalori) |
| Elenco di adiacenza | Θ(n + m) | O(deg v) | Θ(deg v) | Grafi sparsi; algoritmi BFS/DFS e percorso minimo |
| Elenco di archi | Θ(m) | Θ(m) | Θ(m) | Input/output, MST di Kruskal, algoritmi incentrati sugli archi |
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 Ak è 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 An−1 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
- Scegli un formato di input usando il selettore a schede: elenco archi, elenco adiacenza o matrice di adiacenza.
- Incolla o digita il tuo grafo nell'area di testo. Per l'input della matrice, aggiungi etichette opzionali nel campo Etichette della matrice.
- 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. - 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.
- 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 AT.
- 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
Cita questo contenuto, pagina o strumento come:
"Calcolatore di Matrice di Adiacenza" su https://MiniWebtool.com/it/calcolatore-di-matrice-di-adiacenza/ di MiniWebtool, https://MiniWebtool.com/
dal team di miniwebtool. Aggiornato: 20 aprile 2026
Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.
Operazioni matematiche avanzate:
- Calcolatore di Matrice di Adiacenza Nuovo
- Calcolatore di Antilogaritmo
- Calcolatore di funzione Beta
- Calcolatore del Coefficiente Binomiale
- Calcolatrice di distribuzione binomiale
- Calcolatore Bitwise
- Semplificatore di Algebra Booleana Nuovo
- Calcolatore del Teorema Centrale del Limite
- Calcolatore del Teorema Cinese del Resto
- Calcolatore di combinazione
- Calcolatore di Funzione di Errore Complementare
- Calcolatrice di Numeri Complessi
- Calcolatore di Frazioni Continue Popolare
- Calcolatore di Derangement (Sottofattoriale)
- Calcolatore del Percorso più Breve di Dijkstra
- Calcolatore di Entropia
- Calcolatore della funzione di errore
- Calcolatore della Funzione Toziente di Eulero
- Calcolatore di decadimento esponenziale
- Calcolatore della crescita esponenziale
- Calcolatore dell'Integrale Esponenziale
- Calcolatore di Esponenti (Alta Precisione) Popolare
- Calcolatore dell'Algoritmo Euclideo Esteso
- Calcolatrice del Fattoriale Popolare
- Calcolatore della Funzione Gamma
- Calcolatore del Rapporto Aureo
- Calcolatore di Colorazione di Grafi Nuovo
- Validatore di Sequenza di Gradi di Grafo
- Calcolatore Ordine Teoria dei Gruppi Nuovo
- Calcolatore del tempo di dimezzamento
- Verificatore di Cammino Hamiltoniano Nuovo
- Calcolatore Inclusione-Esclusione Nuovo
- Risolutore di Mappa di Karnaugh (K-Map) Nuovo
- Risolutore di Programmazione Lineare Nuovo
- Calcolatore Distribuzione Stazionaria Catena di Markov
- Calcolatore dell'Albero Ricoprente Minimo
- Calcolatore Esponenziazione Modulare Nuovo
- Calcolatore dell'Inverso Moltiplicativo Modulare
- Calcolatore Distribuzione Binomiale Negativa Nuovo
- Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
- Calcolatore del Tasso di Crescita Percentuale
- Calcolatore di Permutazione
- Calcolatore Permutazioni con Ripetizione Nuovo
- Calcolatore del Principio dei Cassetti
- Verificatore di Grafo Planare Nuovo
- Calcolatrice della Distribuzione di Poisson
- Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
- Calcolatore Radice Primitiva
- Calcolatrice delle probabilità
- Calcolatrice di Distribuzione di Probabilità
- Calcolatore di Proporzioni
- Calcolatore di formula quadratica
- Calcolatore di Anelli e Campi Nuovo
- Calcolatore di Arrotondamento Nuovo
- Calcolatrice Scientifica
- Calcolatore di notazioni scientifiche Popolare
- Calcolatore di Teoria degli Insiemi
- Calcolatore di Cifre Significative Nuovo
- Risolutore del Problema del Matrimonio Stabile Nuovo
- Calcolatore di Numeri di Stirling
- Calcolatore di Somme di Cubi
- Calcolatore di somme di numeri interi positivi
- Calcolatore di Somme di Quadrati
- Calcolatore di Ordinamento Topologico Nuovo
- Risolutore del Commesso Viaggiatore (TSP) Nuovo
- Generatore di Tabella di Verità
- Generatore di Diagramma di Venn (3 Insiemi)