bridge e articulation point

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

bridge e articulation point

Messaggio da pa » 16 mar 2008, 18:40

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? :)
paolo

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Re: bridge e articulation point

Messaggio da Tibor Gallai » 16 mar 2008, 18:54

pa ha scritto:Sapete se ne esistono altri? :?:
C'è anche il caso in cui sono entrambi foglie.

Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa » 16 mar 2008, 19:01

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?
paolo

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 16 mar 2008, 19:05

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.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite