Komponente povezanosti (teorija grafova)

Iz Vikipedije, slobodne enciklopedije
Idi na: navigaciju, pretragu
Graf sa tri povezane komponente.

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]

  1. Hopcroft, J.; Tarjan, R. (1973). „Efficient algorithms for graph manipulation”. Communications of the ACM. 16 (6): 372—378. doi:10.1145/362248.362272. 
  2. 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]

Spoljašnje veze[uredi]