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
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
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
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
- ^ 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
- 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
- Connected components, Steven Skiena, The Stony Brook Algorithm Repository