[scienze.unimo] Re: Verifica aciclicità in un grafo
- From: Valerio Bigiani <vbigiani@xxxxxxxx>
- To: scienze.unimo@xxxxxxxxxxxxx
- Date: Mon, 29 May 2006 23:00:28 +0200
Emanuele Bardelli wrote:
Ecco il mio problema:
Dopo una visita in profondità viene creata una foresta di visita. Ora
posso studiare i nodi del grafo in funzione di quelli appartenenti alla
foresta, e se il grafo è aciclico, non esistono archi all'indietro.
Ora, c'è un modo più veloce per la verifica di questa proprietà diverso
dall'applicare la definizione? (Cioè, confronto ogni arco del grafo con
quelli della foresta, e se trovo un arco all'indietro allora il grafo
contiene un ciclo.)
Ciao,
Emanuele
Beh, tutti i cicli che stai facendo sono O(m) (la visita richiede O(m) se usi
liste di adiacenza, e per ogni arco puoi vedere se e' nella foresta di visita
con tempo costante se usi il vettore dei padri, ripetuto per ogni arco). Se
riesci a svolgere il problema in meno di O(m), non puoi vedere tutti gli archi,
il che, in base al criterio 'a naso', significa che potresti trascurare proprio
quello che causa il ciclo.
Cavicchioli domani dimostrera' che si riesce a fare in tempo
O(log(log(log(log(m)))), CMQ la mia mente ridimensionata dall'alcol non riesce a
fare di meglio.
Per quanto riguarda i libri, prima di uploadarli aspetto che qualcuno dalla
Normale scannerizzi i capitoli sulle proiezioni del loro libro.
Other related posts:
