Pages: [1]   Go Down
Print
Author Topic: Domanda di esame sui grafi  (Read 1098 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
3ntropy
Matricola
*
Offline Offline

Posts: 11


« on: 15-06-2010, 14:56:52 »

Salve a tutti, mi spiegate perché la risposta corretta a questa domanda è la A?

Sia G=(V,E) un grafo orientato. Sia v un vertice del grafo. Supponiamo di voler rimuovere dal grafo il vertice v e tutti gli archi ad esso incidenti. Allora:
a) Conviene sempre usare una matrice di adiacenza per rappresentare il grafo.
b) Conviene sempre usare una rappresentazione del grafo con liste di adiacenza.
c) Conviene usare una rappresentazione del grafo con liste di adiacenza se il grafo ha meno di n log n archi.
d) La complessità del problema è indipendente dalla rappresentazione usata.

In termini di memoria, converrebbe usare la rappresentazione con liste di adiacenza, poiché è necessaria O(max(V,E))=O(V+E), mentre la rappresentazione tramite matrice di adiacenza richiede memoria Θ(V2). Quindi perché la A è la risposta corretta?

Grazie anticipatamente per una vostra risposta.
« Last Edit: 15-06-2010, 15:48:38 by 3ntropy » Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #1 on: 15-06-2010, 15:18:06 »

Poniti la domanda in questo modo: se dovessi cancellare un elemento dal grafo è meglio (punto di vista del costo) cancellarlo da una matrice di adiacenza o da una lista di adiacenza ?
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #2 on: 18-06-2010, 08:28:20 »

la cancellazione di un nodo da un grafo con matrice di adiacenza e' O(V) mentre se lo volessimo cancellare da un grafo con lista di adiacenza il costo e' O(V+E).
In termini di memoria, converrebbe usare la rappresentazione con liste di adiacenza, poiché è necessaria O(max(V,E))=O(V+E), mentre la rappresentazione tramite matrice di adiacenza richiede memoria Θ(V2).
scusa ma se il grafo e' fortemente connesso (cioe' E=\theta(V^2)) le operazioni su lista in termini di memoria hanno un costo O(V+E)=O(V+V^2)=O(V^2). Quindi quello che hai scritto te non e' vero per niente ^^
Logged
3ntropy
Matricola
*
Offline Offline

Posts: 11


« Reply #3 on: 18-06-2010, 11:14:50 »

Beh, di sicuro non l'ho inventato, ma l'ho letto a pag. 448 e pag. 449 del libro di testo.
Logged
Pages: [1]   Go Up
Print
Jump to: