Tranzitivna redukcija

U matematici, tranzitivna redukcija usmerenog grafa je graf sa nekoliko grana koliko je moguće tako da imaju isti odnos dosega kao dati graf. Podjednako, dati graf i njegova tranzitivna redukcija trebalo bi da imaju ista tranzitivna zatvorenja, i njihove tranzitivne redukcije bi trebalo da imaju nekoliko grana koliko je to moguće među svim grafovima ovih osobina. Tranzitivne redukcije je uveo Aho, Garey & Ullman 1972, koji je uveo tanke granice pri njihovom složenom računarskom konstruisanju.

Ako je dati graf konačan usmeren acikličan garaf, njegova tranzitivna redukcija je jedinstvena, i podgraf je datog grafa. Međutim jedinstvenost nije garancija za ciklične grafove, i za beskonačne grafove postojanje uopšte nije ni garantovano.Blisko povezani koncepti minimalnog ekvivalentnog grafa je podgraf datog grafa koji ima istu relaciju dosega i što je moguće manje konačne usmerene aciklične grafove, minimalni ekvivalentni graf je isti kao i tranzitivna redukcija. Međutim, za ciklične grafove, minimalni ekvivalentan graf se NP-teško konstruiše, dok se tranzitivna redukcija i dalje može konstruisati u polinomijalnom vremenu.Tranzitivna redukcija se takođe može definisati za abstraktnije binarne relacije skupova, pretstavljanjem parova relacija kao grana grafa.

Kod direktnih acikličnih grafova

Tranzitivna redukcija konačnog usmerenog grafa G je graf sa sto je moguće manje grana koji ima istu relaciju dosega kao originalan graf. To jest ako postoji put od čvora x do čvora y u grafu G, mora postojati i put od x ka y i u tranzitivnoj redukciji G-a, i obrnuto. Slika koja sledi nam prikazuje graf koji odgovara ne-tranzitivnoj binarnoj relaciji (levo) i svojoj tranzitivnoj redukciji (desno).

Tranzitivna redukcija konačnog usmerenog acikličnog grafa G je je jedinstvena, i sastoji se od grana grafa G koje formiraju jedini put izmedju svojih krajnjih tačaka.Konkretno, to je uvek podgraf datog grafa.Zbog ovoga, tranzitivna redukcija odgovara minimalnom ekvivalentnom grafu u ovom slučaju.

U matematičkoj teoriji binarnih relacija, svaka relacija R na skupu X može biti protumačena kao usmereni graf koji ima skup X kao svoje čvorove i ima granu xy za svaki uređeni par elemenata koji su povezani u R.Konkretno, ova metoda dozvoljava da parcijalno uređene skupove posmatramo kao usmerene aciklične grafove, gde postoji grana xy u grafu kad god postoji relacija poretka 'x < y između datih parova elemenata parcijalnog uređenja.Kada se upotrebi operacija tranzitivne redukcije na usmerenom aciklinom grafu koji je konstruisan na ovaj način, dobija se covering relacija parcijalnog uređenja, koja se često daje kao vizuelni izraz putem Hasse diagrama.

Kod cikličnih grafova

Kod konačnog grafa koji mozda ima ciklus,tranzitivna redukcija nije jedinstveno definisana:mozda postoji više od jednog grafa sa istim skupom čvorova kao i minimalim brojem grana i ima istu relaciju dosega kao dati graf.Pored toga,postoji i slučaj kada niti jedan od ovih minimalnih grafova nije podgraf datog grafa.Ipak,ispravno je da minimalne grafove sa istim relacijam dosega obeležavamo kao dati graf G.Ako je G proizvoljan usmeren graf, i ako je H graf sa minimalnim mogućim brojem grana koji ima istu relaciju dosega kao G, onda se H sastoji od:

• Usmerenog ciklusa za svaku čvrsto povezanu komponentu iz G, koja spaja cvorove u ovu komponentu
• Grane xy za svaku granu XY tranzitivne redukcije kondenzacije od G,gde su X i Y dve čvrsto povezane komponente od G koje su spojene granama u kondenzaciji,x je bilo koji čvor komponente X, a y je bilo koji čvor komponente Y.Kondenzacija od G je usmren acikličan graf koji ima čvor za svaku čvrsto povezanu komponentu iz G.Posebno, zato što je acikličan, njegova tranzitivna redukcija se definiše kao u prethodnom delu.

Ukupan broj grana u ovom tipu tranzitivne redukcije je jednak broju čvorova u tranzitivnoj redukciji kondenzacije, plus broj čvorova u netrivijalnom čvrsto povezanim komponentama (komponente koje se sastoje od više od jednog čvora).

Grane tranzitivne redukcije koja odgovara kondenzaciji grana se uvek može odabrati da bude podgraf datog grafa G.Međutim,ciklis unutar svake čvrsto povezane komponente se može izabrati da bude podgraf grafa G jedino ako ta komponenta ima Hamiltonov ciklus, nešto sto nije uvek tačno, i teško se proverava. Zbog ove poteskoće, NP je teško naći najmanji podgraf datof grafa G sa istim dosegom (minimalni ekvivalentni graf).

Složenost izračunavanja

Kako je Ahi et al. pokazao, kada se vremenska složenost grafovskih algoritama meri funkcijom po broju n, broju čvorova grafa, a ne po broju grana, tranzitivno zatvorenje i tranzitivna redukcija imaju istu složenost. Već je pokazano da tranzitivno zatvorenje i množenje Logičkih matrica veličine n × n imaju istu složenost, pa prema tome i tranzitivna redukcija pripada istoj klasi.Najbrzi poznati algoritam za množenje matrica ima složenost O(n^2.3727) i tranzitivnia redukcija ima istu ovu složenost.

Da bi dokazali da je tranzitivna redukcija laka kao tranzitivno zatvorenje , Aho et al. je od datog usmerenog acikličnog grafa G konstruisao drugi graf H, u kojem je svaki čvor iz G zamenjen putem od tri čvora, i svaka grana grafa G odgovara grani grafa H koja spaja odgovarajuće srednje čvorove ovih puteva.Pored toga, u grafu H, Aho et al. dodaje granu iz svakog početka puta u svaki kraj puta. U tranzitivnoj redukciji grafa H, postoji grana od od početka puta u do kraja puta v ako i samo ako grana uv ne pripada tranzitivnom zatvorenju grafa G.Dakle, ako se tranzitivna redukcija grafa H moze efikasno izračunati, tranzitivno zatvorenje grafa G se moze pročitati direktno odatle.

Da bi dokazao da je tranzitivna redukcija iste lakoće kao i tranzitivno zatvorenje, Aho et al. se oslanja na već poznatu ekvivalenciju množenja Logičkih matrica.Neka A bude matrica susedstva datog grafa, a B matrica susedstva tranzitivnog zatvaranja(koja se izracunava pomoću bilo kog standardnog algoritma tranzitivnog završetka).Zatim, grana uv pripada tranzitivnoj redukciji ako i samo ako postoji ne-nula ulaz u redu u i koloni v matrice A, i ne postoji ne-nula ulaz na istim pozicijama matrice proizvoda AB.U ovoj konstrukciji, ne-nula elementi matrice AB predstavljaju parove čvorova povezanih putevima dužine veće ili jednake dvojci.

Kada ih merimo u na osnovu broja čvorova n i broja grana m kod usmerenih acikličnih grafova, tranzitivna redukcija se izračunava u vremenskoj složenosti O (nm), sto je garantovano brže od metoda množenja matrica kod retkih grafova. Da bi smo to uradili, prikupljamo grane (u,v) tako da je rastojanje najdužeg puta od u do v jedan, izračunavajuci ta rastojanja, tragamo u linearnom vremenu za mogućim početnim čvrom ,u. Ova vremenska granica od O (nm) se poklapa sa kompleksnošću konstruisanja tranzitivnog zatvorenja korišcenjem pretraživanja u dubinu ili pretraživanja u širinu za pronalaženje čvorova dosežnih iz bilo kog početnog čvora, tako da opet pomoću ovih pretpostavki tranzitivna redukcija se može naći za isti vremenski period.

Reference

• Aho, A. V.; Garey, M. R.; Ullman, J. D. (1972), „The transitive reduction of a directed graph”, SIAM Journal on Computing, 1 (2): 131—137, MR 0306032, doi:10.1137/0201008 .
• Moyles, Dennis M.; Thompson, Gerald L. (1969), „An Algorithm for Finding a Minimum Equivalent Graph of a Digraph”, Journal of the ACM, 16 (3): 455—460, doi:10.1145/321526.321534 .
• Williams, Virginia Vassilevska (2012), „Multiplying matrices faster than Coppersmith–Winograd”, Proc. 44th ACM Symposium on Theory of Computing (STOC '12), стр. 887—898, doi:10.1145/2213977.2214056 .

Spoljašnje veze

• Weisstein, Eric W. „Transitive Reduction”. MathWorld.