OliForum Matematico

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?

pa ha scritto:Sapete se ne esistono altri?

C'è anche il caso in cui sono entrambi foglie.

C'è anche il caso in cui sono entrambi foglie.

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?

Non so cos'è una DFS, ma se per foglia intendi un nodo con un solo arco, allora questo grafo ha un arco tra 2 foglie:


o----o


Se invece escludi questa configurazione, direi che la tua analisi è giusta.