Pages: 1 [2]   Go Down
Print
Author Topic: Domanda su grafi  (Read 1856 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #15 on: 26-09-2011, 16:17:04 »

DOMANDA 2:

http://img691.imageshack.us/img691/4716/domandagrafi.jpg

Qualcuno conosce la soluzione? A me risultano vere sia la b) che la c)
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #16 on: 26-09-2011, 17:52:15 »

Quella sicuramente corretta é la risposta c puoi trovare anche il teorema sul testo nella parte relativa al grafo delle componenti connesse non so della risposta b....
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #17 on: 26-09-2011, 20:22:17 »

Quella sicuramente corretta é la risposta c puoi trovare anche il teorema sul testo nella parte relativa al grafo delle componenti connesse non so della risposta b....

Veramente? non lo trovo.
Tra l'altro il Cormen accenna a malapena il grafo delle componenti connesse.
Puoi essere piu preciso o rimandarmi al teorema?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #18 on: 26-09-2011, 20:26:32 »

Ho la seconda edizione, dopo l' algoritmo su come trovare le componenti fortemente connesse continuando ci sono lemmi e teoremi, prima degli esercizi c' è questa affermazione. L' esercizio 22.5-4 chiede di dimostrarlo.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #19 on: 26-09-2011, 20:43:53 »

---- NUOVA DOMANDA ----

Le visite sui grafi BFS e DFS, nel caso avessimo implementato i grafi con matrici di adiacenza, richiedono complessita' O(|V|x|V|)?

Quindi l'ordinamento topologico, o la scoperta delle componenti fortemente connesse di un grafo implementato con matrici di adiacenza richiede pure tempo O(|V|x|V|)?

Credo che sia cosi', voi che ne pensate?

La DFS costa \theta(V+E), l' ordinamento topologico viene effettuato usando la DFS, il resto delle operazioni viene eseguito in tempo costante, perciò l' ordinamento topologico viene effettuato in tempo \theta(V+E).
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #20 on: 26-09-2011, 20:47:26 »

mi riferivo all'implementazione con matrici di adiacenza
Logged
Pages: 1 [2]   Go Up
Print
Jump to: