Odredjivanje artikulacionih tacaka (kao dopuna definicijama pojmova u teoriji grafova)
U datom povezanom grafu G = (V,E), cvor
u predstavlja artikulacionu tacku ako brisanjem tog cvora i svih ivica koje polaze od tog cvora graf postaje nepovezan. Funkciju za odredjivanje artikulacionih tacaka mozemo dobiti modifikacijama na funkciji za obilazak grafa u dubinu.
Neka je G
a = (V, E
a) drvo dobijeno od grafa G obilaskom u dubinu. Tada je:
1. Koren drveta G
a artikulaciona tacka ako ima barem dva naslednika (odnosno povezan je sa dva cvora u drvetu G
a);
2. Ako je
v cvor koji nije koren drveta G
a onda je
v artikulaciona tacka akko ne postoji povratna ivica (
u,w) takva da je
u naslednik cvora
v, a
w prethodnik cvora
v u drvetu G
a.
Ovo se moze iskoristiti da se odrede artikulacione tacke. Neka je:
l[v] = min( {d[v]} U {d[w]});
...gde je (
u,w) povratna ivica i cvor u je naslednik cvora v;
d[v] je niz veza cvora
v (predstavljen nulama i jedinicama).
Cvor
v je artikulaciona tacka akko postoji njegov direktni naslednik
u takav da je
l[ u ] >= d[v]. Tako dobijamo funkciju za odredjivanje artikulacionih tacaka...
http://cgm.cs.mcgill.ca/~msude.../articulation/articulation.pdf
http://www.student.cs.uwaterlo...ourses/W03/section1/Unit17.pdf
[Ovu poruku je menjao maricn dana 13.05.2008. u 17:18 GMT+1]
Re: [Teorija algoritama] Skup poznatih algoritama i struktura podataka