Pages: [1]   Go Down
Print
Author Topic: Dubbio sul sottografo dei predecessori (DFS)  (Read 581 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Misa
Matricola
*
Offline Offline

Posts: 57



« on: 24-09-2011, 22:58:14 »

Sia un grafo G=(V,E)

Il Cormen, all'inizio della descrizione della visita in profondita' definisce il sottografo dei predecessori come il sottografo G_\pi=(V, E_\pi), dove:

-V sono gli stessi vertici di G
-E_\pi ={(\pi[v] , v) : v \in V e  \pi[v] \neq NIL}}

Ovvero gli archi dell'albero.

Quindi in E_\pi sono esclusi tutti gli altri tipi di arco, perche' non hanno un predecessore. (Ad un vertice viene assegnato un predecessore soltanto quando viene visitato mentre e' bianco. E questo evento genera un arco dell'albero).

Tuttavia, poche pagine dopo al paragrafo "Classificazione degli archi" il Cormen cita:

"Si possono definire quattro tipi di archi in termini della foresta G_\pi prodotta da una visita in profondita' su G."

Mi sembra una discrepanza. Qualcuno puo' aiutarmi a capire?
Gli archi che non sono "dell'albero" fanno parte del sottografo dei predecessori? E allora perche' non sono inclusi in E_\pi?
Forse non ho capito da cosa e' composto E_\pi?
« Last Edit: 24-09-2011, 23:01:40 by Misa » Logged
Pages: [1]   Go Up
Print
Jump to: