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 costruire le affermazioni contronominali

Ognuno di noi fa ragionamenti pratici particolari, tutti i giorni. In molte circostanze, specialmente nel corso delle sessioni di studio della logica classica, abbiamo a che fare con sottili argomentazioni dalla validità garantita. Infatti, esse scaturiscono...
Università e Master

Come costruire un termometro atmosferico ad aria

Considerati i prezzi più che elevati degli strumenti di misura in commercio, è utile tenere presente che nell'ambito del fai da te, è possibile cimentarsi nella realizzazione di vari tipi di strumenti, tra cui i termometri. Quello che ti suggerisco...
Università e Master

Come Costruire Una Rappresentazione Gerarchica Delle Probabilità

Se vogliamo sapere il verificarsi di un determinato evento dobbiamo far ricorso alla probabilità; infatti, grazie ad un apposito grafico è possibile determinarla. La probabilità ad esempio di una vincita al gioco si calcola in base ad una successione...
Università e Master

Come costruire un grafico

Costruire un grafico può essere abbastanza utile per presentare i dati di una determinata ricerca e per effettuare un confronto fra quest'ultima ed una eseguita precedentemente; nella seguente semplice e rapida guida che enuncerò nei passaggi successivi,...
Università e Master

Come costruire il diagramma di Bruckner

In questa guida affronteremo un argomento ostico per molti studenti universitari, ovvero il diagramma di Bruckner, utile nell'analisi matematica e per la rappresentazione grafica dei volumi: ne potete osservare un esempio illustrato nell'immagine. La...
Università e Master

Come costruire una diga

All'interno di questa specifica guida, andremo a occuparci di un tema molto interessante, che ha contraddistinto lo sviluppo stesso della civiltà avanzata: la diga. Nello specifico, come avrete avuto l'opportunità di comprendere attraverso la lettura...
Università e Master

Come costruire un Quadrato Di Punnet Con 2 Caratteri

Questa guida vi aiuterà a costruire un quadrato di Punnett per l'analisi di 2 geni che si incrociano per comprendere quali saranno i caratteri dominanti e recessivi nel susseguirsi delle varie generazioni; ovvero permette di "predire" la generazione...
Università e Master

Come Costruire Verbi Parasintetici

La lingua italiana presenta una grammatica abbastanza ricca, infatti sono molte le parti del discorso presenti nel linguaggio, come ad esempio: sostantivi, nomi, aggettivi, articoli, preposizioni, verbi, congiunzioni e avverbi e tutti devono essere analizzati...
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 »”.