thumb|360px|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. 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е . . . . . . .
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).
Категорија:Стабла (структуре података) Категорија:Структуре података графа