Vettori Matrici Grafi - unimi.itmainetti.di.unimi.it/teaching/ailab/lessons/L4/L4.pdf · GRAFO: Un...

Vettori – MatriciGrafi

Renato Mainetti

Vettore

Vettori Matrici Grafi e Fuzzy - Lezione 4 2

Un vettore è un elemento di uno spazio vettoriale. I vettori sono quindi elementi che possono essere sommati fra loro e moltiplicati per dei numeri, detti scalari.

I vettori sono comunemente usati in fisica per indicare grandezze che sono completamente definite solo quando sono specificati sia una magnitudine (o modulo) che una direzione ed un verso rispetto ad un altro vettore o un sistema di vettori. Le grandezze che possono essere descritte in questo modo sono chiamate grandezze vettoriali, in contrapposizione alle grandezze scalari che sono caratterizzate unicamente dallo loro magnitudine. (wikipedia)

In Matematica:

https://it.wikipedia.org/wiki/Vettore_(matematica)

Vettore


Si può immaginare un vettore(array) come una sorta di contenitore , le cui caselle sono dette celle dell'array stesso. Ciascuna delle celle si comporta come una variabile tradizionale che rappresenta un elemento dell'array; tutte le celle sono variabili di uno stesso tipo preesistente, detto tipo base dell'array. Si parlerà perciò di tipi come "array di interi", "array di stringhe", "array di caratteri" . (wikipedia)

In informatica:

4 2 9 7 1

https://it.wikipedia.org/wiki/Array

Vettori in Matlab:Possono essere inseriti come righe o come colonne:Riga:

vetRiga = [1 2 3 4 5];

vetRiga = [1,2,3,4,5];Colonna:

vetColonna = [1;2;3;4;5];

Proviamo ora ad inserire un array da 1 a 20.

Ci vuole tempo vero?

E se vi dicessi che ci serve un array di 1000 elementi?


Inserimento tramite intervalli:

Possono essere inseriti specificando un intervallo:

Operatore -> :vetRiga = [1:5];

In questo caso gli elementi vengono distanziati con granularità 1.

Può inoltre essere specificata la granularità della suddivisione dell’intervallo:

vetRiga = [1:0.1:5];


Esercizio:

Proviamo a creare due array:

- Numeri pari tra 0 e 20

- Numeri dispari tra 1 e 21

La strada giusta è quella di utilizzare una granularità adeguata.


Trasposizione:

Vettore da riga a colonna: operatore ’ (apostrofo)

vetColonna = vetRiga’;


Matrici:

In matematica, in particolare in algebra lineare, una matrice è una tabella ordinata di elementi.

Le matrici sono ampiamente usate in matematica e in tutte le scienze per la loro capacità di rappresentare in maniera utile e concisa diversi oggetti matematici, come valori che dipendono da due parametri o anche sistemi lineari, cosa, quest'ultima, che le rende uno strumento centrale dell'analisi matematica. (wikipedia)


https://it.wikipedia.org/wiki/Matrice

Matrici:

Sono fondamentalmente vettori bidimensionali


a1,1 a1,2 a1,3

a2,1 a2,2 a2,3

a3,1 a3,2 a3,3

am,n

Matrice m x n

m r

igh

e

N colonne

Matrici in matlab:

Inseriamo una matrice in matlab:

mat = [1 2 3; 4 5 6; 7 8 9];

Stiamo sfruttando le due tecniche usate prima, ovvero inserimento righe e inserimento colonne contemporaneamente.


Zeros – Ones - Eye

Attraverso i comandi Zeros, Ones e Eye possiamo creare matrici inizializzando i valori a zero, uno e a zero con diagonale ad uno.

zeroMat = zeros(3,3);

onesMat = ones(4,3);

eyeMat = eye(10,10);


Accedere agli elementi

Vettore:

Si specifica l’elemento dell’array a cui si vuole accedere (lettura/scrittura)

Es. vetRiga(3); (lettura: il valore viene messo in ans)

vetRiga(3) = 0; (assegniamo valore zero al terzo elemento)

Matrice:

Si specifica la riga e la colonna che identificano univocamente un elemento della matrice a cui si vuole accedere(lettura/scrittura)


Selezione elementi

Selezionare parte degli elementi da un array o da una matrice:

vetRiga(1:3) restituisce in ans i valori delle celle 1-2-3

vetRiga(:) restituisce in ans tutti i valori dell’array

mat(:,2) restituisce tutti gli elementi della seconda colonna


Aggiungere Rimuovere elementi

Array:

vetRiga = (1:5);

vetRiga(6) = 0;

vetRiga(3) = [] rimuove il terzo elemento dell’array

Matrici:

mat = (1 2 3; 4 5 6; 7 8 9);

mat(4,:) = (10:12);

mat(:,3) = [] rimuove la terza colonna della matrice


Plot - Creare grafici -

Esempio per creare grafici in matlab: La funzione Coseno

• Creo un array da 0 a 2-Pigreco: >> x = [0:0.1:2*pi]

• Creo un array valutando il coseno dei valori di x:>> y = cos(x)

• Disegno del grafico:>>plot(x,y)

(Guardare help matlab per opzioni di line-spec)Vettori Matrici Grafi e Fuzzy - Lezione 4 15

GRAFO:Un grafo è un insieme di elementi detti nodi o vertici che possono essere collegati fra loro da linee chiamate archi o lati o spigoli. (wiki)


Si distinguono due tipi basilari di grafi, i grafi orientati (o grafi diretti) e i grafi non orientati (o grafi indiretti).Un "grafo non orientato" è un insieme di vertici e archi dove la connessione A - B ha lo stesso significato della connessione B – A (non è importante la direzione)

https://it.wikipedia.org/wiki/Grafo

ALBERO:Un albero è un grafo: non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino (grafo non orientato, connesso e privo di cicli). (wiki)


https://it.wikipedia.org/wiki/Albero_(grafo)

Matrice delle adiacenze

• La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi (wikipedia)

• Dato un qualsiasi grafo la sua matrice delle adiacenze è costituita da una matrice binaria quadrata che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto (i,j) della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice i al vertice j, altrimenti si trova uno 0.


https://it.wikipedia.org/wiki/Matrice_delle_adiacenze

Costruiamo un Albero di prova:


1

2 3

4 5

Matrice delle adiacenze• Definiamo una matrice delle adiacenze per 5 nodi:

• adMat = zeros(5,5);

• Apriamo l’editor delle variabili facendo doppio click su adMat nel WorkSpace e completiamo con 1 la matrice in caso di connessione tra i vari nodi.


Matrice delle coordinate dei nodi

• Creiamo una matrice che contenga le coordinate dei nodi di questo albero (serve solo a matlab per posizionarli sul piano)

coordinate = [3 5; 2 3; 4 3; 1 1; 3 1];


Visualizzare l’albero con gplot

• La funzione gplot(g,c,lineSpec) prende in input una matrice delle adiacenze e una matrice di coordinate. Disegna poi l’albero congiungendo i nodi con gli archi.

• Il parametro lineSpec permette di specificare l’aspetto grafico degli archi e dei nodi.

• Es. ‘-*’ linea continua e asterischi

• Per variare aspetto grafico consultare il manuale di lineSpec.


Risultato del plot:


Per avere il plot esattamente quadrato possiamo usare il comando:

axis square

Esploriamo gli strumenti che matlab

offre nell’analisi dei grafi dalla versione 2015b.


Questa lezione viene fornita con in allegato il file: GrafoRomania.mche contiene un tutorial sulle prove che ora vi mostrerò dal vivo.Ricordo che sui pc del laboratorio è presente la versione di matlab 2015a che non contiene ancora queste funzionalità.

Mappa semplificata della Romania


Con lo script indicato e Matlab 2015b o 2016a

Otteniamo un grafo così:


Possiamo ricercare la strada più breve tra due nodi ed evidenziarla.

Algoritmi di ricerca:


Da approfondire se volete fare un progetto su questi argomenti:http://it.mathworks.com/help/matlab/ref/graph.shortestpath.html

Vettori Matrici Grafi - unimi.itmainetti.di.unimi.it/teaching/ailab/lessons/L4/L4.pdf · GRAFO: Un...

Documents

Transcript of Vettori Matrici Grafi - unimi.itmainetti.di.unimi.it/teaching/ailab/lessons/L4/L4.pdf · GRAFO: Un...