mercoledì 3 marzo 2010
Lezione del 3/3/2010
Operatori su grafi; Rappresentazione dei grafi con lista di archi, liste di adiacenza e matrice di adiacenza; Complessita' computazionale degli operatori nelle tre rappresentazioni; Esercizi sulle proprieta' dei grafi: un grafo connesso di n nodi ha almeno n-1 archi; un grafo aciclico di n nodi ha massimo n-1 archi; un albero di n nodi ha n-1 archi; Il quadrato della matrice di adiacenza di un grafo rappresenta cammini di lunghezza due: come estendere il risultato.
Iscriviti a:
Commenti sul post (Atom)
Post
5 commenti:
Ho notato che abbiamo introdotto le funzioni su aggiungere ed eliminare gli archi, ma non le operazioni sui singoli nodi
come mai abbiamo introdotto solamente operazioni su archi e non su nodi?
AddEdge, DelEdge ecc
Possono essere anche introdotti operatori di inserimento e cancellazione di nodi ma nell'introdurli bisogna tener presente che aggiungere (o eliminare) un nodo da un grafo rappresentato mediante matrice di adiacenza o vettore delle liste di adiacenza comporterebbe l'introduzione di costosi meccanismi per alterare strutture dati di dimensione costante. Alternativamente potrebbero essere utilizzate strutture piu' elaborate (tipo array associativi) che pero' non garantiscono accesso in tempo costante.
Prevalentemente non avremo bisogno di operazioni del genere. Quando questo succedera' introdurremo di volta in volta soluzioni ad-hoc.
Dato G=(V,E), M^n è la matrice di adiacenza, dei cammini P(u,v) di lunghezza n.
Dim |--> procediamo per induzione:
BASE: n=2, M^n[i,j]=1 SSE sum(k=1 to n){ M[i,k]*M[k,j] }>0
SSE esiste M[i,k]=M[k,j]=1 SSE esistono (i,k)apprt E, (k,j)apprt E ,{k=1...n}
SSE esiste P(i,j)=P(i=x0,x1,x2=j) di lunghezza 2. (x1=k)
Vera la base, supponiamo vera la tesi per n e verifichiamo per n+1
Passo induttivo: M^n; M^n+1 matrice di adiacenza di cammini P(u,v) di lunghezza n+1
M^n+1[i,j]=1 SSE sum(k=1 to n){ M[i,k]^n * M[k,j]}>0 SSE esist M^n[i,k]=M[k,j]=1
SSE esist P(i,k), (k,j)apprt E, con P(i,k)=P(i=x0,x1,...,xn=k), (xi,xi+1)apprt E
SSE P(i,j)=P(i=x0,x1,.....,xn,j) di lunghezza n+1
END.
La dimostrazione è corretta?
si, direi che e' corretta.
Posta un commento