СПQР стабло

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Тровезне компотенте двовезног графа у грани математике, званој теорија графова, представљају систем мањих графова који описују све дво-темене разрезе графа. СПQР стабло је структура података стабла која се користи у компјутерској науци, или још прецизније у графовским алгоритмима, за представљање тровезних компонената графа. СПQР стабло може бити конструисано у линеарном времену и има неколико примена у динамичним графовским алгоритмима и визуализацији графова.

Саундерс Меклејн (1937) је први истражио основну структуру СПQР стабла – тровезне компоненте графа и везу између ове врсте декомпозиције и планарног уграђивања планарних графова. Ди Батиста анд Тамасиа (1989, 1990, 1996) су користили ове структуре у ефикасним графовима пре него што су се оне развиле у СПQР стабло.

Структура[уреди | уреди извор]

СПQР стабло има неукорењену структуру у којој свако x чвориште одговара једном неукорењеном графу или мултиграфу Г_x. Само чвориште и његов граф могу припадати једном од четири типа, за које се користе иницијали СПQР:

Граф чворишта С је кружни граф са три или више темена и ивица. Овај случај је аналоган са случајем серијске композиције серијско-паралелних графова. С овде представља “серију”.
Граф чворишта П је диполни граф – мултиграф са два темена и три или више ивица, планарни двојник кружног графа. Овај случај је аналоган са паралелном композицијом серијско-паралелних графова. П овде представља “паралелу”.
Граф чворишта Q има само једну ивицу. Мада се не јавља у СПQР стаблима комплекснијих графова, овај тривијални случај је неопходан за објашњавање графова који имају само једну ивицу.
Граф чворишта Р је тровезни граф који није ни круг ни дипол. Р овде представља “ригидност”: у примени СПQР стабала у планарном уграђивању графова, граф чворишта Р има јединствено планарно место уграђивања.

Свака ивица xy између два чворишта СПQР стабла повезана је са две усмерене виртуелне ивице, где је једна ивица у Г_x , а друга ивица у Г_y. Свака ивица у графу Г_x може представљати виртуелну ивицу за највише једну ивицу СПQР стабла.

СПQР стабло Т представља двовезни граф Г_Т који се формира на следећи начин: када ивица xy СПQР стабла повеже виртуелну ивицу аб графа Г_x са виртуелном ивицом цд графа Г_y, чиме се формира већи граф повезивањем а и ц у јединствено супертеме и уклањањем две виртуелне ивице. Другим речима, тај већи граф представља комбинацију структура Г_x и Г_y. Оваквим спајањем на свакој ивици СПQР стабла ствара се граф Г_Т, а редослед корака у спајању не утиче на резултат. Свако теме у једном од графова Г_x може на овај начин бити повезано са јединственим теменом у Г_Т, то јест са супертеменом којем је припојено.

По правилу није дозвољено да у једном СПQР стаблу два С чворишта буду једно до другог, нити два П чворишта да буду једно до другог, јер би у том случају два чворишта могла да се споје у једно веће чвориште. На основу ове претпоставке, СПQР стабло је на јединствен начин одређено својим графовима. Када је граф Г представљен СПQР стаблом у коме не постоји оближње П чвориште и С чвориште, онда графови Г_x повезани са чвориштима СПQР стабла представљају тровезне компоненте Г.

Налажење дво-темених разреда[уреди | уреди извор]

Прилично је једноставно у СПQР стаблу графа Г (без Q чворишта) пронаћи све парове темена у и в, будући да се уклањањем у и в из графа Г добија неповезан граф, као и повезане компоненте преосталих графова:

Темена у и в могу представљати две крајње тачке виртуелне ивице графа повезаног са Р чвориштем. У таквом случају ове две компоненте су представљене у два под-стабла СПQР стабла и формирају се уклањањем одговарајуће ивице СПQР стабла.
Темена у и в могу представљати два темена графа повезаног са П чвориштем који има две или више ивица. У овом случају, компоненте добијене уклањањем у и в су представљене под-стаблом СПQР стабла – једно под-стабло за сваку виртуелну ивицу у чворишту.
Темена у и в могу представљати два темена у графу повезаном са С чвориштем у смислу да у и в или нису једно другом у непосредној близини, или да је ивица ув виртуелна. Уколико је ивица виртуелна, онда овај пар (у,в) такође припада чворишту типа П и Р и компоненте су као у горепоменутом случају. Уколико ова два темена нису у непосредној близини, онда су две компоненте представљене двема путањама кружног графа повезаног са С чвориштем, где су чворишта СПQР стабла повезана са тим двема путањама.

Уграђивање планарних графова[уреди | уреди извор]

Уколико је планарни граф тровезни, он онда има јединствено планарно место уграђивања условљено избором спољног правца и оријентације уграђивања: правци уграђивања су заправо нераздвајајући кругови графа. Међутим, у случају планарног графа (са обележеним теменима и ивицама) који је двоезни али не и тровезни, може постојати већа слобода приликом проналажења планарног уграђивања. Тачније, кад год су два чворишта у СПQР стаблу графа повезана паром виртуелних ивица, могуће је променити оријентацију једног чворишта у односу на оријентацију другог. Такође, у П чворишту СПQР стабла, различити делови графа повезаног са виртуелним ивицама П чворишта могу бити арбитрарно пермутовани. Све планарне репрезентације је могуће објаснити на овај начин.

Референце[уреди | уреди извор]

Биенстоцк, Даниел; Монма, Цлyде L. (1988), „Он тхе цомплеxитy оф цоверинг вертицес бy фацес ин а планар грапх”, СИАМ Јоурнал он Цомпутинг, 17 (1): 53—76, дои:10.1137/0217004 .
Ди Баттиста, Гиусеппе; Тамассиа, Роберто (1989), „Инцрементал планаритy тестинг”, Сyмпосиум он Фоундатионс оф Цомпутер Сциенце, стр. 436—441, дои:10.1109/СФЦС.1989.63515 Текст „Проц. 30тх Аннуал Сyмпосиум он Фоундатионс оф Цомпутер Сциенце” игнорисан (помоћ).
Ди Баттиста, Гиусеппе; Тамассиа, Роберто (1990), „Он-лине грапх алгоритхмс wитх СПQР-треес”, Интернатионал Цоллоqуиум он Аутомата, Лангуагес анд Программинг, Лецтуре Нотес ин Цомпутер Сциенце, 443, Спрингер-Верлаг, стр. 598—611, дои:10.1007/БФб0032061 Текст „Проц. 17тх Интернатионал Цоллоqуиум он Аутомата, Лангуагес анд Программинг

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

Ди Баттиста, Гиусеппе; Тамассиа, Роберто (1996), „Он-лине планаритy тестинг” (ПДФ), СИАМ Јоурнал он Цомпутинг, 25 (5): 956—997, дои:10.1137/С0097539794280736 .
Гутwенгер, Царстен; Мутзел, Петра (2001), „А линеар тиме имплементатион оф СПQР-треес”, Интернатионал Сyмпосиум он Грапх Драwинг, Лецтуре Нотес ин Цомпутер Сциенце, 1984, Спрингер-Верлаг, стр. 77—90, дои:10.1007/3-540-44541-2_8 Текст „Проц. 8тх Интернатионал Сyмпосиум он Грапх Драwинг (ГД 2000)

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

Хопцрофт, Јохн; Тарјан, Роберт (1973), „Дивидинг а грапх инто трицоннецтед цомпонентс”, СИАМ Јоурнал он Цомпутинг, 2 (3): 135—158, дои:10.1137/0202012 .
Мац Лане, Саундерс (1937), „А струцтурал цхарацтеризатион оф планар цомбинаториал грапхс”, Дуке Матхематицал Јоурнал, 3 (3): 460—472, дои:10.1215/С0012-7094-37-00336-3 .

Спољашње везе[уреди | уреди извор]

Имплементација СПQР стабла у Опен Грапх Драwинг Фрамеwорк.
Тхе трее оф тхе трицоннецтед цомпонентс Јава имплементатион ин тхе јБПТ либрарy (сее ТЦТрее цласс).