Come Costruire La Versione Matriciale Di Un Grafo

tramite: O2O
Difficoltà: facile
15

Introduzione

I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce un'importante parte della combinatoria; i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi, funzioni speciali, geometria dei poliedri, algebre di Lie. I grafi si incontrano in vari capitoli dell'informatica (ad esempio per schematizzare programmi, circuiti, reti di computer, mappe di siti). Essi inoltre sono alla base di modelli di sistemi e processi studiati nell'ingegneria, nella chimica, nella biologia molecolare, nella ricerca operativa, nella organizzazione aziendale, nella geografia (sistemi fluviali, reti stradali, trasporti), nella linguistica strutturale, nella storia (alberi genealogici, filologia dei testi). Un grafo è un insieme di elementi detti nodi o vertici che possono essere collegati fra loro da linee chiamate archi o lati o spigoli. Più formalmente, si dice grafo una coppia ordinata G = (V, E) di insiemi, con V insieme dei nodi ed E insieme degli archi, tali che gli elementi di E siano coppie di elementi di V (da E \subseteq V \times V segue in particolare che |E| \leq |V|^2). Nei passi della guida a seguire sarà illustrato come costruire la versione matriciale di un grafo.

25

Costruisci esattamente due matrici per raccogliere tutte le informazioni originariamente contenute nel tuo grafo di partenza, queste sono: la matrice di distanza e la matrice degli archi. Ipotizza adesso di considerare un grafo così strutturato: il nodo 1 collegato al nodo 2 da un arco che riproduce una distanza di 7 unità, il nodo 2 collegato al nodo 3 da un arco che riporta una distanza di 4 unità. Infine il nodo 2 collegato anche al nodo 4 da un arco che definisce una distanza tra i due nodi di 5 unità.

35

Le matrici che ti appresti ora a popolare sono tutte quadrate e dotate di un lato costituito da tanti elementi quanti sono i nodi in totale. Nel tuo caso, avrai due matrici quadrate 4 x 4. Per costruire la matrice di distanza devi semplicemente posizionare nell'elemento (i, j) (cioè riga i-ma e colonna j-ma) della matrice la distanza che separa il nodo i dal nodo j. Secondo il grafo descritto a inizio guida puoi quindi valorizzare l'elemento (1,2) di questa matrice con 7, l'elemento (2,3) con 4 e l'elemento (2,4) con 5. Avrai intuito che questo tipo di matrice è simmetrica, quindi l'elemento (i, j) è uguale a quello (j, i).

Continua la lettura
45

Dedicati ora alla costruzione della matrice degli archi; per farlo è sufficiente che valorizzi ogni suo elemento (i, j) con un valore unitario nel caso in cui puoi verificare la presenza di un arco tra il nodo i e il nodo j e con un valore nullo in caso di relativa assenza. Quindi puoi proporre le seguenti valorizzazioni: elemento (1,2) = 1, elemento (2,3) = 1, elemento (2,4) = 1, data la presenza degli archi tra i nodi indicati. Una volta valorizzati gli elementi simmetrici, tutti i restanti li devi rappresentare con valori nulli. Quindi, ad esempio, è corretto che indichi l'elemento (1,3) = 0 nella tua matrice degli archi, dato che non esiste un arco che colleghi direttamente il nodo 1 al nodo 3.

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Università e Master

Come trovare gli autovalori di una matrice

In questa guida verranno date utili informazioni su alcune nozioni di matematica. L'argomento trattato riguarderà il calcolo matriciale che vi permette di trovare tutti gli autovalori di una matrice specifica. È bene precisare che quest'ultima non è...
Università e Master

Le strategie di management

"Management", il termine che definisce le strategie e le tecniche che garantiscono il funzionamento delle aziende viene dalla lingua inglese. Ed è una cosa fondamentale che queste strategie e tecniche siano efficaci e corrette, o l'azienda in questione...
Università e Master

Teorema di Gauss-Markov: dimostrazione

La matematica è sempre stata la materia più complicata e quindi meno apprezzata sia dai bambini delle scuole elementari, sia dagli studenti delle superiori e delle facoltà universitarie. Questa difficoltà sta soprattutto nel fatto che i concetti sono...
Università e Master

Appunti su matrici e determinanti

La matematica è da sempre la materia più ostica per ri studenti di qualsiasi età partire dalle elementari fino agli studi universitarie. La matrice è un insieme di numeri racchiuso in una tabella formata da righe e colonne, allo scopo di individuare...
Superiori

Come Calcolare il Determinante di Matrici Quadrate con il Teorema Di Laplace

Avete delle difficoltà nel calcolare Il Determinante di Matrici Quadrate? Non sapete proprio come fare? Attraverso i passaggi successivi di questa Guida capirete, in poche e semplici operazioni, come dovete affrontare questa tipologia di problemi di...
Superiori

Come stabilire il rango di una matrice

Tutti gli studenti si sono trovati a far i conti con l'algebra, durante la propria carriera scolastica. Tra gli argomenti più critici che possono mettere in imbarazzo ed anche in difficoltà seria gli studenti maggiormente preparati, ci sono le matrici....
Superiori

Come calcolare la norma di una matrice

Il concetto di norma, nella maggior parte dei casi, si associa ai vettori, ed associa ad ognuno di essi, fatta eccezione per quelli nulli, una lunghezza positiva; ma bisogna sapere che esso si estende anche alle matrici, cioè alle tabelle ordinate di...
Superiori

Operazioni tra matrici

In algebra lineare viene definita come "matrice" un'operazione che assume la forma di una tabella ordinata di elementi. Le operazioni di matrici sono largamente sfruttate nell'algebra lineare ed in tutte le scienze affini, specialmente grazie alla loro...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.