Динамичко повезивање

У рачунарству и теорији графова, структура динамичког повезивања је структура података која динамички одржава информације о компонентама повезаности графа.

Скуп чворова V графа је непроменљив, а скуп грана Е се може мењати. Три случаја за промену скупа Е, поређана по тежини, су:

• Додавање грана у граф (може се називати инкрементно повезивање);
• Брисање грана из графа (може се називати декрементно повезивање);
• Додавање или брисање грана из графа (може се називати потпуно динамичко повезивање).

Након сваког додавања/брисања гране, структура динамичког повезивања би требало да се адаптира тако да може давати брзе одговоре на упите типа "да ли постоји пут између чворова x и y?" (еквивалентно: "да ли чворови x и y припадају истој компоненти повезаности?").

Инкрементно повезивање

Ако се гране могу само додавати, проблем динамичког повезивања се може решити помоћу структуре дисјунктног скупа података. Сваки скуп представља компоненту повезаности; постоји пут између чворова x и y ако и само ако припадају истом скупу. Временска сложеност операције је $O(\alpha (n))$, где је н број чворова, а α инверзна Акерманова функција, која је приближно константна.

Декрементно повезивање

Проблем у случају у коме се гране могу само брисати су решили Схимон Евен и Yосси Схилоацх.

Структура користи табелу која одређује, за сваки чвор, име сваке компоненте којој припада. Дакле, упит повезивања захтева константно време. Изазов је ажурирати табелу када је грана обрисана.

Ациклични графови (шуме)

Када је грана у-в обрисана из шуме, стабло, које је садржало ту грану, је подељено на два стабла: једно од њих садржи чвор у, а друго садржи чвор в. Табела се ажурира на следећи начин.

• Претражи стабло почевши од чвора у (користећи било који алгоритам за претрагу, као што је ДФС).
• Претражи стабло почевши од чвора в.
• Изврши горе наведене кораке паралелно, било помоћу два паралелна процеса или преплитањем њихових корака (направи корак прве претраге, затим корак друге претраге, затим корак прве претраге и тако даље).
• Претпоставимо да је прва претрага која се заустави претрага из чвора у (тако да знамо да је стабло које садржи чвор у мање). Додели ново име компоненте сваком чвору у подстаблу у.

Пошто се сваки пут мањој поткомпоненти мења име, временска сложеност за операцију брисања је $O(\log(n))$.

Општи графови

Када је грана избрисана из општег графа, не знамо да ли граф остаје повезан (једна компонента повезаности) или неповезан (подељен на две компоненте). Користимо два процеса која раде паралелно (или на испреплитан начин). Процес А проверава да ли брисање дели компоненту повезаности и ако дели, оба процеса се заустављају. Процес Б проверава да ли брисање гране не дели компоненту којој грана припада и ако не дели, оба процеса се заустављају.

Процес А је сличан случају ацикличних графова: постоје два потпроцеса која обилазе граф са оба краја обрисане гране. Ако један од потпроцеса заврши пре него што дође до другог краја, ово значи да је компонента подељена на две поткомпоненте и назив мање поткомпоненте је ажуриран, као и раније. Дакле, временска сложеност операције брисања је опет $O(\log(n))$.

Процес Б користи структуру обиласка у ширину (БФС) која је иницијализована на следећи начин. Изабран је чвор р и БФС обилазак креће од њега. Једини чвор у нивоу 0 је р. . Сви чворови удаљени од корена за дужину и су у нивоу и. Ако граф Г није повезан, почиње се нови обилазак из неког непосећеног чвора в, в се ставља у ниво 1 и нова, вештачка грана повезује в са кореном р; сви чворови на растојању дужине и од чвора в су сада на нивоу и+1, итд. Вештачке гране се уводе како би све компоненте повезаности биле присутне у БФС стаблу и користе се искључиво у ову сврху. Очигледно, вештачке гране се користе само у процесу Б.

Структура има следеће карактеристике. Чвор в који је у нивоу и, и>0, има три врсте грана: повратне гране, које га повезују са нивоом и-1 (постоји бар једна таква грана и може бити вештачка), попречне гране, које га повезују са другим гранама у нивоу и (постоји нула или више таквих грана) или директне гране, које га повезују са гранама у нивоу и+1 (постоји нула или више таквих грана). За сваки чвор в, одржавамо три типа грана (повратне, попречне и директне).

Када је грана у-в обрисана, постоје две опције: или су чворови у и в у истом нивоу или су у нивоима који се разликују за 1.

Случај 1: чворови у и в су у истом нивоу. У овом случају брисање не може да промени компоненте. Грана је једноставно обрисана из скупа попречних грана, и процес Б се зауставља (и процес А се зауставља). Структура обиласка у ширину је и даље валидна.

Случај 2: чворови у и в су на различитим нивоима. Без губитка општости претпостављамо да је чвор у на нивоу и-1, а чвор в на нивоу и; отуда, требало би уклонити по грану из скупа диретних грана из чвора у и из скупа повратних грана из чвора в.

Случај 2.1: Ако нови скуп повратних грана из чвора в није празан, онда се компоненте повезаности нису промениле: постоје друге гране које повезују в повратно. Процес Б се зауставља, као и процес А.

Случај 2.2: Ако нови скуп повратних грана из чвора в' јесте празан, онда в није више повезан са нивоом и-1, тако да његова удаљеност од корена није више и; мора бити најмање и+1. Додатно, морају постојати и други чворови повезани са в, чије се удаљености од корена увећавају као последица брисања. Да бисмо израчунали ажуриране удаљености, користимо ред Q, који иницијално садржи само чвор в.

Wхиле Q није празан:

1. w := деqуеуе(Q)
2. Избаци w са његовог нивоа (нпр. ј), и стави га на следећи ниво (ј+1).
3. Ажурирај локалне суседе:
   • За сваку грану w-x из скупа попречних грана из чвора w, обриши је из скупа попречних грана из чвора x и стави у скуп директних грана из x.
   • Скупу повратних грана из w додели вредност скупа попречних грана из w.
4. Ажурирај директне суседе:
   • За сваку грану w-x из скупа директних грана из w, обриши је из скупа повратних грана из чвора x и стави у скуп попречних грана из x; ако је нови скуп повратних грана из x празан, стави x на ред Q.
   • Скупу попречних грана из w додели вредност скупа директних грана из w.
   • Скупу директних грана из w додели празан скуп.
5. Ако је нови скуп повратних грана из w празан, опет стави w на ред Q.

Ако брисање гране не сломи ни једну компоненту и ми смо у случају 2.2, онда се временом процедура зауставља. У овом случају је лако видети да БФС структура остаје правилно одржавана. Ако њено брисање сломи компоненту, онда се процедура неће зауставити сама од себе. Ипак, процес А, препознајући ломљење, ће се зауставити и оба процеса ће се зауставити. У овом случају све измене направљене у БФС структури се игноришу и враћамо се на БФС структуру коју смо имали пред брисање, осим сто је обрисана грана замењена вештачком. Очигледно је да је у овом случају в корен стабла који садржи нову компоненту и можда додатне компоненте, или неке друге вештачке гране. Такође, нема грана које повезују претке чвора в са било којим чворовима који нису преци чвора в, осим вештачке гране у-в.

Кад год је грана обрађена у процедури, ниво једног од њених крајева опадне за један. Како је најнижи ниво који чвор може достићи у покретањима које зауставља процес Б |V|-1, цена по грани је ограничена са 2|V|. Стога је временска сложеност по операцији брисања $O(n)$.

Потпуно динамичко повезивање

Ациклични графови (шуме)

Шума може бити представљена или колекцијом линк-цут стабала или стабала Ојлеровог обиласка. Тада проблем динамичког повезивања може бити решен лако, пошто за свака два чвора x, y, x је повезан са y ако и само ако ПронађиКорен(x) = ПронађиКорен(y). Временска сложеност ажурирања и време упита су О(лог(н)).

Општи графови

Општи граф може бити представљен својим разапињућим стаблом – стаблом које садржи подстабло за сваку компоненту повезаности графа. Ово називамо разапињућим стаблом Ф. Ф може бити представљен шумом стабала Ојлеровог обиласка.

Операције упита и додавања су имплементиране коришћењем одговарајућих операција над ЕТ стаблима које представљају Ф. Операција које је највећи изазов је брисање, конкретније, брисање гране која је садржана у једном од разапињућих стабала од Ф. Ово ломи разапињуће стабло на два стабла, али је могуће да постоји друга грана која их повезује. Изазов је брзо наћи такву грану, ако она постоји. Ово захтева комплекснију структуру података. Неколико оваквих структура су описане испод.

Ниво структура

Свакој грани графа се додељује ниво. Нека је L=лг н. Ниво сваке гране додате у графу је иницијализован на L и може опадати ка 0 током операција брисања.

За свако и између 0 и L, дефиниши Ги као подграф, садржан од грана које су на нивоима и или ниже, и Фи као разапињуће стабло Ги. Наша шума Ф од раније се сад назива ФЛ. Наставићемо да умањујемо секвенцу шума ФЛ ⊆ ... ⊆ Ф0.

Операције

Операције упита и убацивања користе само највеће шуме ФЛ.Мањи подграфови се користе само при операцији брисања, конкретно, брисањем гране која је садржана у једном од разапињућих стабала од ФЛ.

Када је таква грана е = x-y обрисана, прво је уклоњена из ФЛ ФЛ и из свих мањих разапињућих стабала којима припада, на пример из сваког Фи где је и веће или једнако нивоу гране е. Онда тражимо грану којом ћемо је заменити.

Почињемо од најмањег разапињућег стабла шуме која је садржала е, наиме, Фи где је и једнако нивоу гране е. Грана е припада одређеном стаблу Т⊆Фи. Након брисања гране е, стабло Т је подељено на два мања стабла: Тx које садржи чвор x и Тy које садржи чвор y. Грана из Ги је грана коју ћемо узети као замену ако и само ако она повезује чвор у Тx са чвором у Тy. Претпоставимо, без губитка општости, да је Тx мање стабло (нпр. садржи највише пола чворова из Т; можемо увидети величину сваког подстабла преко белешке додате у Ојлерова стабла).

Итерирамо преко свих чворова ε са нивоом и и са бар једним чвором у Тx:

• Ако је други чвор ε у Тy, онда је грана за замену нађена. Додај ову грану у Фи и са свима који садрже шуме до ФЛ заврши. Разапињуће шуме су поправљене.
• Ако је други чвор ε у Тx, онда ово није грана за замену и, како би је "казнили" због утрошеног времена, смањимо јој ниво за један.

Анализа

Ниво сваке гране ће се смањити највише лг н Зашто? Зато што сваким смањењем, стабло постаје дупло мање од стабла у претходном кораку. Тако је број чворова на нивоу и, у свакој компоненти повезаности, највише 2^и. Отуда је ниво сваке гране бар 0.

Потребно је $O(lgn)$ времена да се пронађе грана чији ниво треба бити умањен (користећи ЕТ операције стабла). Укупно, за сваку уметнуту грану троши се $O(lg^{2}n)$ времена за брисање, па је просечно време брисања гране $O(lg^{2}n)$. Преостали део брисања грана, такође има временску сложеност $O(lg^{2}n)$, јер треба да обришемо гране са највише $O(lgn)$ нивоа, а брисање на сваком нивоу има временску сложеност $O(lgn)$ (поново користећи ЕТ операције стабла).

Укупно, просечна временска сложеност ажурирања је $O(lg^{2}n)$. Временска сложеност по упиту се може побољшати до $O(lgn/lglgn)$.

Међутим, у најгорем случају временска сложеност ажурирања може бити $O(n)$. Проблем побољшања временске сложености најгорег случаја је било отворено питање све док се није појавио бипартитни граф као решење.

Бипартитни граф

Нека је дат граф Г(V, Е) и подскуп чворова Т ⊆ V, бипартитни граф(Т) дефинишемо као скуп грана које повезују скуп чворова Т са скупом чворова V\Т. Бипартитни граф је структура података, која, без чувања целог графа у меморији, брзо проналази грану у бипартитном графу, ако таква грана постоји.

Сваком чвору графа се додељује број. Претпоставимо да има н чворова; онда ћемо сваки чвор обележити бројем који је записан у бинарном систему дужине лг(н). Затим ћемо доделити број свакој грани; број гране се добија спајањем бројева својих темена, записан је у бинарном систему дужине 2лг(н).

За сваки чвор все рачуна и чува резултат функције xор(в), који се добија примењивањем функције xор на све бројеве грана суседних чвору в.

За сваки подскуп чворова Т ⊆ V је сада могуће израчунати xор(Т) = резултат је број који се добија примењивањем функције xор на све бројеве чворова скупа Т. Размотримо сада грану е = у-в која је унутрашња грана скупа Т (у и в припадају скупу Т). Број гране е је два пута био укључен у функцију xор(Т) – једном за чвор у, а други пут за чвор в. Како је резултат операције xор примењене на било који број са самим собом 0, онда грана е нестаје и не утиче на xор(Т). Дакле, xор(Т) је заправо xор примењен на све гране у бипартитном графу(Т). Постоји неколико опција:

• Ако је xор(Т)=0, онда можемо потврдити да је бипартитни граф (Т) празан скуп.
• Ако је xор(Т) број који одговара некој стварној грани е, вероватно је онда грана е једина у бипартитном графу(Т) и онда можемо вратити е. Такође, можемо прочитати крајње чворове гране е, тако што ћемо број гране е поделити на два броја дужине лг(н).
• Трећа опција је када xор(Т) не представља број ниједне постојеће гране стабла. Ово се може десити само ако се у бипартитном графу(Т) налази две или више грана, јер у том случају xор(Т) је xор од неколико бројева различитих грана. Тада се пријављује "грешка" пошто знамо да у структури постоји неколико грана, али не можемо да идентификујемо тачно једну.

Сада нам је циљ да решимо трећу опцију.

Прво се креира секвенца, од бипартитног графа, која има лг(н) нивоа, где сваки ниво садржи половину грана у односу на ниво изнад (тј. за сваки ниво се бира грана са нивоа изнад са вероватноћом 1/2). Ако на првом нивоу xор(Т) врати неважећу вредност, то значи да бипартитни граф (Т) има две или више грана, и постоји шанса да на следећем нивоу, који има мање грана, xор(Т) врати важећу вредност пошто ће бипартитни граф (Т) имати само једну грану. Ако xор(Т) и даље враћа неважећу вредност прелазимо на следећи ниво, итд. Пошто се број грана смањује, постоји два случаја:

• Добар случај је када нађемо ниво у коме бипартитни граф (Т) садржи само једну грану; тада вратимо ту грану и завршавамо.
• Лош случај је када пронађемо ниво у коме бипартитни граф (Т) не садржи ниједну грану; тада пријављујемо "грешку" пошто знамо да постоји више грана у бипартитном графу, али не можемо да идентификујемо тачно једну.

Могуће је доказати да је вероватноћа успеха бар 1/9.

Потом креирамо колекцију C*лг(н) независних верзија нивоа структуре, где је C константа. У свакој верзији, урадити независно, случајно уклањање грана по нивоима. Пробати сваки упит на свакој верзији све док једна не успе. Вероватноћа да ће све верзије бити неуспешне је највише: $(1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}$ Правилним одабиром константе C можемо вероватноћу неуспеха сманњити до 0.

Операције

Можемо додати бипартитни граф у структуру динамичког повезивања.

Операције додавања и брисања у бипартитни граф се обављају на исти начин: додата/обрисана грана је XОР-ована у оба њена чвора.

Када се нека грана обрише из разапињућег стабла који се користи у структури динамичког повезивања, бипартитни граф се користи како би се нашла грана која ће заменити обрисану грану.

Анализа

Један бипартитни граф захтева само О(н*лг(н)) просторне сложености – само један број, дужине 2*лг(н) бита, за сваки од н чворова. За густе графове, ово је много јефтиније него чувати читав граф у меморији.

Морамо чувати лг(н) верзије, од којих свака садржи лг(н) нивоа. Отуда, укупна просторна сложеност је О(н лг^3 н).

Временска сложеност упита је О(полyлог(н)) у најгорем случају. Ово је супротно од структуре по нивоима, где је просечна временска сложеност упита О(полyлог(н)), а у најгорем случају О(н).

Види још

• Дyнамиц проблем (алгоритхмс)
• Партитион рефинемент