Komponente povezanosti (teorija grafova)
U teoriji grafova, povezana komponenta neusmerenog grafa je podgraf u kom su bilo koja dva čvora međusobno povezana putevima, i koji nije povezan sa dodatnim čvorovima u supergrafu. Na primer, u grafu prikazanom na ilustraciji sa desne strane se nalaze tri povezane komponente. Graf koje je povezan sam sa sobom, ima tačno jednu povezanu komponentu, čineći ceo graf.
Relacija ekvivalencije[uredi | uredi izvor]
Alternativni način da se definiše povezana komponenta uključuje klase ekvivalencije od relacije ekvivalencije koja je definisana na čvorovima grafa. U neusmerenom grafu, čvor v je dostižan od čvora u ako postoji put od u do v. U ovoj definiciji, jedan čvor se računa kao put dužine nula, a isti čvor može da se pojavi više od jednog puta u obilasku. Dostizanje je relacija ekvivalencije, pošto:
- Je refleksivna: Postoji trivijalni put od dužine nula od bilo kog čvora do samog sebe.
- Je simetrična: Ako postoji put od u do v, sama grana formira put od v do u.
- Je tranzitivna: Ako postoji put od u do v i put od v do w, ova dva puta mogu biti spojena zajedno tako da formiraju put od u do w.
Povezane komponente su onda indukovani podgrafi koje formiraju klase ekvivalencije u ovoj relaciji.
Broj komponenti povezanosti[uredi | uredi izvor]
Broj komponenti povezanosti je važna topološka invarijanta grafa. U topološkoj teoriji grafova, broj komponenti povezanosti može da se interpretira kao nulti Betijev broj grafa. U algebarskoj teoriji grafova broj komponenti povezanosti je jednak višestrukosti 0 kao sopstveni vektor od grafa Laplasove matrice. Takođe je i indeks prvog koeficijenta različitog od nule od hromatskog polinoma grafa. Broj komponenti povezanosti igraju ključnu ulogu u Tutovoj teoremi karakterišući grafove koji imaju savršeno poklapanje, i u definiciji težine grafova.
Algoritmi[uredi | uredi izvor]
Jednostavno je da se izračunaju komponente povezanosti grafa u linearnom vremenu (u pogledu broja čvorova i puteva grafa) korišćenjem bilo pretrage u širinu ili pretrage u dubinu. U bilo kom slučaju, pretraga koja počinje u nekom određenom čvoru v pronaći će celokupnu povezanu komponentu koja sadrži v (i ne više) pre povratka. Da bismo pronašli sve povezane komponente grafa, idemo petljom kroz čvorove, započinjući novu pretragu u širinu ili dubinu kad god petlja dostigne čvor koji već nije uključen u prethodno pronađenoj komponenti povezanosti. Hopkroft i Tardžan (1973))[1] opisuju ovaj algoritam u suštini, i navode da je u tom trenutku bilo „dobro poznato“.
Postoje i efikasni algoritmi za dinamičko praćenje povezanih komponenti grafa dok se čvorovi i grane dodaju, kao jednostavna primena sistema disjunktnih struktura podataka. Ovi algoritmi zahtevaju amortizovano O(α(n)) vreme operacije, kod kojih dodajući čvorove i puteve, i određivanje povezane komponente, gde su obe operacija, i α(n) je vrlo sporo rastuća inverzna, od vrlo brzo rastuće Akermanove funkcije. Sličan problem predstavlja praćenje povezanih komponenti dok se sve grane brišu iz grafa, jedna po jedna; postoji algoritam za rešavanje ovog konstantnog vremena po upitu, i O(|V||E|) vreme da se održi struktura podataka; ovo je amortizovana cena od O(|V|) po brisanju puta. Za drveta, cena može da se smanji do O(q + |V| log |V|), ili O(log |V|) amortizovana cena po obrisanom putu.[2]
Istraživači su takođe proučavali algoritme za pronalaženje povezujućih komponenti u više ograničenim modelima računanja, kao što su programi u kojima je radna memorija ograničena na logaritamski broj bitova (definisana kompleksnom klasom L). Levis i Papadimitrou (1982) su se pitali da li je moguće da se testira u logaritamskom prostoru da li dva čvora pripadaju istoj komponenti povezanosti nekog neusmerenog grafa, i definisali su kompleksnost SL klase problema gde je logaritamski prostor jednak povezanosti. Konačno je Reingold (2008) uspeo da pronađe algoritam za rešavanje ovog problema povezivanja u logaritamskog prostoru, pokazujući da je L = SL.
Reference[uredi | uredi izvor]
- ^ Hopcroft, J.; Tarjan, R. (1973). „Efficient algorithms for graph manipulation”. Communications of the ACM. 16 (6): 372—378. doi:10.1145/362248.362272.
- ^ Shiloach, Y. and Even, S. 1981. An On-Line Edge-Deletion Problem. Journal of the ACM: 28, 1 (Jan. 1981), pp.1-4.
Literatura[uredi | uredi izvor]
- Lewis, Harry R.; Papadimitriou, Christos H. (1982), „Symmetric space-bounded computation”, Theoretical Computer Science, 19 (2): 161—187, doi:10.1016/0304-3975(82)90058-5.
- Reingold, Omer (2008), „Undirected connectivity in log-space”, Journal of the ACM, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291.
Spoljašnje veze[uredi | uredi izvor]
- Connected components, Steven Skiena, The Stony Brook Algorithm Repository