SPQR stablo

Graf i njegovo SPQR stablo. Isprekidane crne linije povezuju parove virtualnih ivica, prikazane crno; ostale ivice su obojene u skladu sa troveznim komponentama kojima pripadaju.

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 G_x. 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 G_x , a druga ivica u G_y. Svaka ivica u grafu G_x može predstavljati virtuelnu ivicu za najviše jednu ivicu SPQR stabla.

SPQR stablo T predstavlja dvovezni graf G_T koji se formira na sledeći način: kada ivica xy SPQR stabla poveže virtuelnu ivicu ab grafa G_x sa virtuelnom ivicom cd grafa G_y, č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 G_x i G_y. Ovakvim spajanjem na svakoj ivici SPQR stabla stvara se graf G_T, a redosled koraka u spajanju ne utiče na rezultat. Svako teme u jednom od grafova G_x može na ovaj način biti povezano sa jedinstvenim temenom u G_T, 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 G_x 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  .
• 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 

” игнорисан (помоћ).

• 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 

” игнорисан (помоћ).

• 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).