[scienze.unimo] Re: Verifica aciclicità in un grafo
- From: Roberto Cavicchioli <trebor86it@xxxxxxxx>
- To: scienze.unimo@xxxxxxxxxxxxx
- Date: Tue, 30 May 2006 10:22:53 +0200 (CEST)
In O(log(log(log(log(m)))) no, ma forse un algoritmo
decente potrebbe essere:
Mentre costruisco gli alberi di ricerca mi tengo da
parte tutti gli archi che non fanno parte della
foresta (tipo con una struttura UF) e alla fine della
costruzione controllo i rimanenti se sono archi
all'indietro o trasversali.
Dovrei stare a calcolare la effettiva efficienza di
ciò, ma ora non ne ho ne tempo ne voglia.... :-)
ps. Fare un uscita alcolica al sabato sera non sarebbe
male in comunità matematica-informatica (LOL)
--- Valerio Bigiani <vbigiani@xxxxxxxx> ha scritto:
> 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.
>
>
___________________________________
Yahoo! Mail: gratis 1GB per i messaggi e allegati da 10MB
http://mail.yahoo.it
Other related posts:
