SPQR stablo
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/55/SPQR_tree_2.svg/360px-SPQR_tree_2.svg.png)
Trovezne kompotente dvoveznog grafa u grani matematike, zvanoj teorija grafova, predstavljaju sistem manjih grafova koji opisuju sve dvo-temene razreze grafa. SPQR stablo je struktura podataka stabla koja se koristi u kompjuterskoj nauci, ili još preciznije u grafovskim algoritmima, za predstavljanje troveznih komponenata grafa. SPQR stablo može biti konstruisano u linearnom vremenu i ima nekoliko primena u dinamičnim grafovskim algoritmima i vizualizaciji grafova.
Saunders Meklejn (1937) je prvi istražio osnovnu strukturu SPQR stabla – trovezne komponente grafa i vezu između ove vrste dekompozicije i planarnog ugrađivanja planarnih grafova. Di Batista and Tamasia (1989, 1990, 1996) su koristili ove strukture u efikasnim grafovima pre nego što su se one razvile u SPQR stablo.
Struktura
SPQR stablo ima neukorenjenu strukturu u kojoj svako x čvorište odgovara jednom neukorenjenom grafu ili multigrafu Gx. Samo čvorište i njegov graf mogu pripadati jednom od četiri tipa, za koje se koriste inicijali SPQR:
- Graf čvorišta S je kružni graf sa tri ili više temena i ivica. Ovaj slučaj je analogan sa slučajem serijske kompozicije serijsko-paralelnih grafova. S ovde predstavlja “seriju”.
- Graf čvorišta P je dipolni graf – multigraf sa dva temena i tri ili više ivica, planarni dvojnik kružnog grafa. Ovaj slučaj je analogan sa paralelnom kompozicijom serijsko-paralelnih grafova. P ovde predstavlja “paralelu”.
- Graf čvorišta Q ima samo jednu ivicu. Mada se ne javlja u SPQR stablima kompleksnijih grafova, ovaj trivijalni slučaj je neophodan za objašnjavanje grafova koji imaju samo jednu ivicu.
- Graf čvorišta R je trovezni graf koji nije ni krug ni dipol. R ovde predstavlja “rigidnost”: u primeni SPQR stabala u planarnom ugrađivanju grafova, graf čvorišta R ima jedinstveno planarno mesto ugrađivanja.
Svaka ivica xy između dva čvorišta SPQR stabla povezana je sa dve usmerene virtuelne ivice, gde je jedna ivica u Gx , a druga ivica u Gy. Svaka ivica u grafu Gx može predstavljati virtuelnu ivicu za najviše jednu ivicu SPQR stabla.
SPQR stablo T predstavlja dvovezni graf GT koji se formira na sledeći način: kada ivica xy SPQR stabla poveže virtuelnu ivicu ab grafa Gx sa virtuelnom ivicom cd grafa Gy, čime se formira veći graf povezivanjem a i c u jedinstveno superteme i uklanjanjem dve virtuelne ivice. Drugim rečima, taj veći graf predstavlja kombinaciju struktura Gx i Gy. Ovakvim spajanjem na svakoj ivici SPQR stabla stvara se graf GT, a redosled koraka u spajanju ne utiče na rezultat. Svako teme u jednom od grafova Gx može na ovaj način biti povezano sa jedinstvenim temenom u GT, to jest sa supertemenom kojem je pripojeno.
Po pravilu nije dozvoljeno da u jednom SPQR stablu dva S čvorišta budu jedno do drugog, niti dva P čvorišta da budu jedno do drugog, jer bi u tom slučaju dva čvorišta mogla da se spoje u jedno veće čvorište. Na osnovu ove pretpostavke, SPQR stablo je na jedinstven način određeno svojim grafovima. Kada je graf G predstavljen SPQR stablom u kome ne postoji obližnje P čvorište i S čvorište, onda grafovi Gx povezani sa čvorištima SPQR stabla predstavljaju trovezne komponente G.
Nalaženje dvo-temenih razreda
Prilično je jednostavno u SPQR stablu grafa G (bez Q čvorišta) pronaći sve parove temena u i v, budući da se uklanjanjem u i v iz grafa G dobija nepovezan graf, kao i povezane komponente preostalih grafova:
- Temena u i v mogu predstavljati dve krajnje tačke virtuelne ivice grafa povezanog sa R čvorištem. U takvom slučaju ove dve komponente su predstavljene u dva pod-stabla SPQR stabla i formiraju se uklanjanjem odgovarajuće ivice SPQR stabla.
- Temena u i v mogu predstavljati dva temena grafa povezanog sa P čvorištem koji ima dve ili više ivica. U ovom slučaju, komponente dobijene uklanjanjem u i v su predstavljene pod-stablom SPQR stabla – jedno pod-stablo za svaku virtuelnu ivicu u čvorištu.
- Temena u i v mogu predstavljati dva temena u grafu povezanom sa S čvorištem u smislu da u i v ili nisu jedno drugom u neposrednoj blizini, ili da je ivica uv virtuelna. Ukoliko je ivica virtuelna, onda ovaj par (u,v) takođe pripada čvorištu tipa P i R i komponente su kao u gorepomenutom slučaju. Ukoliko ova dva temena nisu u neposrednoj blizini, onda su dve komponente predstavljene dvema putanjama kružnog grafa povezanog sa S čvorištem, gde su čvorišta SPQR stabla povezana sa tim dvema putanjama.
Ugrađivanje planarnih grafova
Ukoliko je planarni graf trovezni, on onda ima jedinstveno planarno mesto ugrađivanja uslovljeno izborom spoljnog pravca i orijentacije ugrađivanja: pravci ugrađivanja su zapravo nerazdvajajući krugovi grafa. Međutim, u slučaju planarnog grafa (sa obeleženim temenima i ivicama) koji je dvoezni ali ne i trovezni, može postojati veća sloboda prilikom pronalaženja planarnog ugrađivanja. Tačnije, kad god su dva čvorišta u SPQR stablu grafa povezana parom virtuelnih ivica, moguće je promeniti orijentaciju jednog čvorišta u odnosu na orijentaciju drugog. Takođe, u P čvorištu SPQR stabla, različiti delovi grafa povezanog sa virtuelnim ivicama P čvorišta mogu biti arbitrarno permutovani. Sve planarne reprezentacije je moguće objasniti na ovaj način.
Referencе
- Bienstock, Daniel; Monma, Clyde L. (1988), „On the complexity of covering vertices by faces in a planar graph”, SIAM Journal on Computing, 17 (1): 53—76, doi:10.1137/0217004 .
- Di Battista, Giuseppe; Tamassia, Roberto (1989), „Incremental planarity testing”, Symposium on Foundations of Computer Science, стр. 436—441, doi:10.1109/SFCS.1989.63515 Текст „Proc. 30th Annual Symposium on Foundations of Computer Science” игнорисан (помоћ).
- Di Battista, Giuseppe; Tamassia, Roberto (1990), „On-line graph algorithms with SPQR-trees”, International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 443, Springer-Verlag, стр. 598—611, doi:10.1007/BFb0032061 Текст „Proc. 17th International Colloquium on Automata, Languages and Programming
” игнорисан (помоћ).
- Di Battista, Giuseppe; Tamassia, Roberto (1996), „On-line planarity testing” (PDF), SIAM Journal on Computing, 25 (5): 956—997, doi:10.1137/S0097539794280736 .
- Gutwenger, Carsten; Mutzel, Petra (2001), „A linear time implementation of SPQR-trees”, International Symposium on Graph Drawing, Lecture Notes in Computer Science, 1984, Springer-Verlag, стр. 77—90, doi:10.1007/3-540-44541-2_8 Текст „Proc. 8th International Symposium on Graph Drawing (GD 2000)
” игнорисан (помоћ).
- Hopcroft, John; Tarjan, Robert (1973), „Dividing a graph into triconnected components”, SIAM Journal on Computing, 2 (3): 135—158, doi:10.1137/0202012 .
- Mac Lane, Saunders (1937), „A structural characterization of planar combinatorial graphs”, Duke Mathematical Journal, 3 (3): 460—472, doi:10.1215/S0012-7094-37-00336-3 .
Spoljašnje veze
- Implementacija SPQR stabla u Open Graph Drawing Framework.
- The tree of the triconnected components Java implementation in the jBPT library (see TCTree class).