Pages: [1]   Go Down
Print
Author Topic: dubbio sui grafi  (Read 1079 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Neds
Matricola
*
Offline Offline

Gender: Male
Posts: 36


« on: 25-02-2010, 13:03:25 »

sia G un grafo orientato aciclico con V=n vertici, sia dato con matrice di adiacenza.
qual'è la complessità del miglior algoritmo possibile che inserisca un solo arco creando un ciclo nel grafo?
1- O(n)
b- O(n^2)
c- O(n^3)
d- O(n^4)

la risposta esatta è la a, giusto?perchè la complessità dell'algoritmo per le operazioni sul grafo è O(n) no?

quindi se dato G un grafo non orientato e connesso,supponiamo che esiste un vertice/arco che se rimosso disconnette il grafo, sia dato con matrice di adiacenza, qual'è la complessità del miglior algoritmo possibile per trovare tale arco?
a-O(V)
b-O(V+E)
c-O(V^2)
d-O(E V^2)

è la a o la c? e se fosse con lista di adiacenza potrebbe essere (V+E)?

saranno domande stupide ma come al solito il giorno prima dell'esame crollano tutte le certezze e anche le cose più ovvie sembrano sbagliate(ansia/panico pre esame) 
Logged
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #1 on: 25-02-2010, 15:50:05 »

Ragionandoci un pò, alla prima domanda risponderei con la lettera b.
Se il grafo è orientato e aciclico, per creare un ciclo mi che, una volta trovato l'arco x->y aggiunga anche l'arco y->x.
Per trovare l'arco x->y mi basta scorrere la matrice del grafo finchè non trovo il valore 1 (se gli archi son privi di pesi) nella posizione Matrice(i,j) e successivamente impostare ad 1 la cella Matrice(j,i).
Nel caso peggiore devo esaminarla tutta, quindi O(n^2).
Non so se c'è un metodo più efficiente, al  momento non mi viene in mente nulla.

Il secondo problema mi sembra più complesso: si deve trovare un modo per "eliminare" i cicli di un grafo. Di fatti se eliminassi un arco appartenente ad un ciclo, esso manterrebbe comunque la connessione fra i due vertici.
Una soluzione potrebbe essere quella di effettuare una visita DFS memorizzando anche gli archi all'indietro (tipici di quando si incontra un ciclo) e usano quell'informazione trovare il giusto arco/nodo da eliminare. Continuo a pensarci sopra e se ricevo un'illuminazione ti scrivo un altro post XD
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Daniele
Matricola
*
Offline Offline

Posts: 81


« Reply #2 on: 25-02-2010, 19:07:19 »

Premetto che in questa materia sono tutt'altro che brillante  , ma proverò ugualmente a rispondere alle due domande.

Per il primo esercizio credo proprio che la b sia la risposta giusta proprio per il motivo esposto da eleirgab. Anche se a voler essere precisi l'algoritmo più efficente per creare un ciclo potrebbe avere complessità costante, poiché dovrebbe bastare  aggiungere un cappio per creare un ciclo nel grafo.

Per quanto riguarda il secondo esercizio ad occhio e croce direi che, dato che esiste un arco (u,v) che se rimosso disconnette il grafo, allora u o v hanno al massimo un arco che fuoriesce da essi, nello specifico quello che se rimosso disconnette il grafo. Nella matrice di adiacenza questo vertice si contraddistingue dagli altri perché la somma dei valori nella sua colonna o riga sono pari a 1, per ottenere questo risultato dovremmo scorrere tutta la matrice, ottenendo una complessità O(v^2).
Spero di non avere detto stupidaggini.
Logged
Pages: [1]   Go Up
Print
Jump to: