stavo facendo un po' di ripasso in vista delle oii e mi sono detto: diamo una ricontrollata alle componenti biconnesse!
http://www.cs.umd.edu/~samir/451/bc.ps
Solo che a pagina quattro in fondo si legge "Notice that if {u, v} is a bridge it does not follow that u and v are both articulation point".
L'unico caso in cui questo sia vero che mi e' venuto in mente e' quello in cui u e' una foglia e v un articulation point... Sapete se ne esistono altri? Se non ne esistessero potrei trovare tutti i bridge vedendo se o sono tra due articulation point o sono tra un articulation point e una foglia no?
bridge e articulation point
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Re: bridge e articulation point
C'è anche il caso in cui sono entrambi foglie.pa ha scritto:Sapete se ne esistono altri?
no scusa come e' possibile che in un albero di una DFS ci sia un arco tra due foglie? Prendiamo il momento in cui una foglia e' appena stata scoperta ed e' grigia mentre l'altra e' ancora bianca (questa momento esiste di sicuro siccome una foglia viene scoperta sicuramente prima dell'altra), se esistesse un arco tra le due, la prima foglia diventerebbe padre della seconda e non sarebbe piu' una foglia no?C'è anche il caso in cui sono entrambi foglie.
paolo
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12