UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO ODDELEK ZA MATEMATIKO Matjaž Zaveršnik RAZČLEMBE OMREŽIJ Doktorska disertacija Ljubljana, 2003 Zahvala Mentorju, prof. dr. Vladimirju Batagelju, bi se rad zahvalil za predlagano temo, dragocene napotke, podporo in potrpeˇzljivost pri nastajanju tega dela. Hvala vsem sodelavcem ter ˇclanom sredinega seminarja in seminarja za diskretno matematiko, ki so prisluhnili mojim razlagam in vpraˇsanjem. Zahvaljujem se tudi vsem domaˇcim za vzpodbudo. 3 Povzetek Precej znanih postopkov za analizo omrežij je prepočasnih, da bi jih lahko uporabili na velikih omrežjih. Zato si pogosto pomagamo z razčlembo omrežja na manjše in lažje obvladljive dele. V doktorski disertaciji se ukvarjamo z učinkovitimi (podkva-dratičnimi) postopki za razčlembe velikih omrežij. V uvodnem poglavju so podane osnovne definicije in oznake, ki jih potrebujemo v nadaljevanju. Drugo poglavje je pregled najbolj znanih že obstoječih postopkov za določanje razčlemb. Opisani so postopki za določanje razbitij danega omrežja, požrešni postopek za izboljšanje dobljenega razbitja, in nekaj drugih vrst razčlemb. Tretje, četrto in peto poglavje vsebujejo izvirne prispevke disertacije. V tretjem poglavju definiramo točkovne in povezavne otoke omrežja. Točkovni otok je povezana skupina točk, ki glede na svoje vrednosti izstopa od točk v svoji soseščini. Podobno so definirani tudi povezavni otoki, le da imamo tam vrednosti na povezavah. Opisani so učinkoviti postopki za določanje otokov in dokazanih več njihovih lastnosti. V naslednjih dveh poglavjih sta razvita primera učinkovito izračunljive točkovne in povezavne funkcije. V četrtem poglavju se ukvarjamo s sredicami. Sredica reda k je maksimalen podgraf, v katerem ima vsaka točka vsaj k sosedov. Sredice določajo gnezdeno raz-slojitev grafa, povezane komponente teh slojev pa določajo hierarhijo nad množico točk. Opisan je učinkovit postopek za določanje sredic. Pojem sredic je posplošen tudi na omrežja, kjer namesto stopnje v dani točki opazujemo kakšno drugo točkovno funkcijo. Pokazano je, da obstaja učinkovit postopek za cel razred točkovnih funkcij. V petem poglavju posplošimo pojem povezanosti v grafu. Definiramo različne relacije povezanosti točk (točkovno in povezavno povezanost s kratkimi cikli v neu-smerjenih in usmerjenih grafih). Opazimo, da so nekatere od teh relacij ekvivalenčne relacije na množici točk, druge pa določajo ekvivalenčno relacijo na množici povezav, kar nam spet določa razbitje grafa. Math. Subj. Class. (2000): 05 C 40, 05 C 85, 05 C 90, 68 R10, 68 W 40, 93 A 15. Ključne besede: analiza velikih omrežij, vrednosti točk, uteži povezav, prerezi, otoki, sredice, povezanost, kratki cikli 5 Abstract Several well known algorithms for network analysis are too slow to be used on large networks. Therefore we often decompose the network to smaller parts that are easier to handle. In doctoral dissertation we study efficient (subquadratic) algorithms for large networks decompositions. The preamble contains some basic definitions and notations used in the continuation. The second chapter is overview of the already existent algorithms for determining the network decompositions. Algorithms for determining the partition of a given network, a greedy algorithm for improvement of a given partition, and some other types of decompositions are described. Third, fourth and fifth chapter contain original contribution of the dissertation. In the third chapter the vertex and edge islands of network are defined. Vertex island is connected set of vertices having values greater than the vertices in their neighborhood. Similarly the edge islands for networks with weights on edges are defined. Efficient algorithms for determining the islands were developed and some properties of islands are proved. In the next two chapters examples of efficiently computable vertex and edge functions are developed. In the fourth chapter we study cores. The core of order k is the maximal subgraph in which every vertex has at least k neighbors. The cores form nested layers of a graph, while the set of connected components of these layers is hierarchy on the set of vertices. Efficient algorithms for determining the cores are presented. The concept of cores is also generalized for networks, where we observe some other vertex function instead of degree. It is shown that there exists an efficient algorithm for the whole class of vertex functions. In the fifth chapter the concept of graph connectivity is generalized. We define several different connectivity relations on the set of vertices (vertex and edge short cycles connectivity in undirected and directed graphs). We notice, that some of them are equivalence relations on the set of vertices, while the others determine equivalence relations on the set of lines, which give us another decomposition of a given graph. Math. Subj. Class. (2000): 05C40, 05 C85, 05 C90, 68R10, 68 W40, 93 A 15. Key words: large networks analysis, values of vertices, weights of edges, cuts, islands, cores, connectivity, short cycles 7 Kazalo 1 Uvod 11 1.1 Osnovni pojmi iz teorije grafov ..................... 12 1.2 Osnovni pojmi iz teorije razvrščanja................... 14 2 Postopki za določanje razčlemb 17 2.1 Razpolavljanje............................... 17 2.2 Določanje razbitij z uporabo koordinat................. 18 2.2.1 Koordinatno razpolavljanje ................... 18 2.2.2 Stabilno razpolavljanje...................... 19 2.3 Določanje razbitij brez uporabe koordinat ............... 20 2.3.1 Požrešni postopki......................... 21 2.3.2 Spektralno razpolavljanje .................... 24 2.3.3 Večnivojske metode........................ 26 2.4 Zaporedne modularne razčlembe..................... 27 3 Prerezi in otoki 29 3.1.1 Splošni točkovni otoki ...................... 30 3.1.2 Enostavni točkovni otoki..................... 32 3.1.3 Izvedba.............................. 34 3.1.4 Časovna zahtevnost........................ 38 3.1.5 Primer............................... 38 3.2 Povezavni otoki.............................. 42 3.2.1 Splošni povezavni otoki...................... 43 9 10 Kazalo 3.2.2 Enostavni povezavni otoki .................... 43 3.2.3 Izvedba .............................. 45 ˇ 3.2.4 Casovna zahtevnost ........................ 49 3.2.5 Primer ............................... 49 3.3 Lastnosti otokov ............................. 52 4 Sredice 57 4.1 Postopek za doloˇcanje hierarhije sredic ................. 58 4.2 Izvedba .................................. 59 ˇ 4.2.1 Casovna zahtevnost ........................ 62 4.2.2 Prilagoditev postopka za druge vrste sredic ........... 63 4.3 Primer ................................... 63 4.4 Primer ................................... 64 4.5 Posploˇsitev sredic ............................. 66 4.6 Postopki za doloˇcanje posploˇsenih sredic ................ 70 4.7 Primer ................................... 71 5 Povezanostskratkimi cikli 73 5.1 Trikotniˇska povezanost .......................... 73 5.1.1 Neusmerjeni grafi ......................... 73 5.1.2 Usmerjeni grafi .......................... 78 5.1.3 Tranzitivnost ........................... 80 5.2 k-kotniˇska povezanost ........................... 81 5.2.1 Neusmerjeni grafi ......................... 81 5.2.2 Usmerjeni grafi .......................... 86 5.2.3 Tranzitivnost ........................... 91 5.3 Moˇzne posploˇsitve ............................. 91 5.4 Primeri ................................... 92 6 Zakljuˇcek 97 Prvo poglavje Uvod Pri analizi velikih omrežij se pogosto srečamo s problemom razkrivanja njihove zgradbe. Vpogled v zgradbo omrežja nam omogoča razumevanje njegovega delovanja, lahko pa je tudi osnova za razvoj učinkovitih postopkov za delo z omrežji. Eden od možnih pristopov k problemu razkrivanja zgradbe omrežja je razčlemba omrežja na več manjših in lažje obvladljivih podomrežij. Pogosto zahtevamo, da so ta podomrežja iz izbranih družin ali pa morajo zadoščati kakšnim drugim pogojem. Te razčlembe so lahko osnova za izgradnjo učinkovitih (približnih) postopkov za posamezne probleme na velikih omrežjih. Pri takih postopkih najprej rešimo problem na manjših omrežjih, nato pa poskušamo iz dobljenih rešitev dobiti približno rešitev problema na celem omrežju. Znanih je več vrst razčlemb omrežij. Eno od njih so razbitja. Ta so določena z razbitjem množice njegovih točk na več ločenih nepraznih podmnožic (skupin). Običajno iščemo takšna razbitja, da bo število povezav, ki imajo krajišča v različnih skupinah, čim manjše (razdelitev poslov med k procesorjev), včasih pa bi radi imeli takšnih povezav čim več (barvanje točk danega omrežja s k barvami). Večkrat postavimo še dodatno zahtevo, da naj bodo posamezne skupine čim bolj uravnotežene (po moči čim bolj enake). Razbitju danega omrežja na k skupin pravimo tudi k-razbitje. Druga vrsta razčlemb omrežij so razslojitve. Pri teh razčlembah vsaki točki omrežja določimo njen nivo, sloj na nivoju t pa je potem sestavljen iz točk, ki so na nivojih z vrednostjo t ali več. Ker so sloji na višjih nivojih vsebovani v slojih na nižjih nivojih, govorimo tudi o gnezdenih razslojitvah. Včasih pa nas ne zanima razbitje ali razslojitev celotnega omrežja, pač pa samo tiste točke ali povezane skupine točk, ki izstopajo glede na neko lastnost. V takem primeru imamo v točkah ali na povezavah podane vrednosti (lahko jih tudi izračunamo iz samega omrežja), ki določajo kako pomembna je posamezna točka ali povezava. Če v takem omrežju poiščemo najpomembnejše točke, lahko iz njih dobimo razbitje omrežja tako, da vsako od teh pomembnih točk proglasimo za predstavnika skupine, vsako od preostalih točk pa postavimo v skupino z najbližjim predstavnikom. 11 12 1. Uvod 1.1 Osnovni pojmi iz teorije grafov Graf G je struktura, sestavljena iz množice točk V in seznama povezav med njimi (vsaka povezava je par točk). Posamezni točki v paru, ki predstavlja povezavo, rečemo krajišče povezave. Če sta krajišči enaki, povezavi rečemo zanka. Podmnožici množice točk bomo rekli skupina točk. Naj bo n število vseh točk, m pa število vseh povezav v grafu. Povezava je lahko neusmerjena (neurejen par točk) ali usmerjena (urejen par točk). Neusmerjeno povezavo med točkama uinv bomo zapisali (u:v), usmerjeno povezavo od točke u do točke v pa (u, v). V splošnem, ko ne bomo želeli predpisati, ali mora biti povezava usmerjena ali neusmerjena, jo bomo zapisali (u;v). Graf je enostaven, če vsaka povezava v seznamu nastopa natanko enkrat (v tem primeru lahko namesto o seznamu govorimo o množici povezav). V nadaljevanju se bomo ukvarjali samo z enostavnimi grafi. Graf je neusmerjen, če so vse povezave neusmerjene, in je usmerjen, če so vse povezave usmerjene. V neusmerjenem grafu bomo za množico povezav uporabljali oznako S, v usmerjenem grafu oznako A, v splošnem grafu, kjer lahko imamo obe vrsti povezav, pa oznako C. (u;V) e C «=> (u-.v) g L V (u,v) g L v (v,u) e C Naj bo v G V poljubna točka. Soseščino točke v lahko definiramo na več načinov, odvisno od tega, kako obravnavamo usmerjene povezave. Nm(v) = {ueV:(u:v)ECW(u,v)eC}\{v} Nout(v) = {ueV: (u:v)eCV(v,u)eC}\{v} N(v) = Nm(v) U Nout(v) Naj bo C C V poljubna skupina točk. Za S G {N, Nin, Nout} lahko definiramo še S+{v) = S(v)U{v} s{v,C) = s(v)nc S (C) = \JS(v)\C vec ______________1.1. Osnovni pojmi iz teorije grafov______________ 13 V teoriji grafov številu povezav s krajiščem v danim točki rečemo stopnja točke. V enostavnih grafih je stopnja točke enaka številu njenih sosedov. Spet ločimo med različnimi vrstami stopenj. deg(w) indeg(w) outdeg(w) \N(v)\ \Nin(v)\ \Nout(v)\ deg(v,C) = \N(v,C)\ mdeg(v,C) = \Nm(v,C)\ outdeg(v,C) = \Nout(v,C)\ Največjo stopnjo točke v grafu bomo označili z A = max,,eVdeg(w). Pogosto imamo poleg grafa definirano še funkcijo p: V -»• IR, ki točkam grafa priredi realne vrednosti, ali pa funkcijo w: C -> IR, ki realne vrednosti priredi povezavam (vrednosti povezave rečemo tudi utež). V takem primeru namesto o grafu G = (V, C) govorimo o omrežju M = (V, C,p) ali M = (V, C,w). Vrednosti so lahko poljubna realna števila, velikokrat pa se pripeti, da so vse nenegativne in/ali cele. Običajno sta v tem primeru analiza omrežja in izvedba nekaterih postopkov veliko preprostejša. Vrednosti točk ali povezav so pogosto kar dane kot rezultati različnih meritev. V omrežju avtorjev, kjer sta dva avtorja povezana, če sta napisala kakšen skupen članek, je utež povezave lahko število skupnih člankov, vrednost točke pa na primer letnica rojstva. V splošnem so vrednosti lahko tudi drugih vrst. Tako je na primer vrednost točke lahko tudi država rojstva. Poleg tega pa obstaja še veliko možnosti, kako vrednost točke ali utež povezave izračunati iz samih podatkov o omrežju. Tako je vrednost točke lahko njena stopnja, število različnih poti, ki potekajo skozi točko, stopnja vmesnosti ... Točka je vmesna, če leži na veliko najkrajših poteh med drugimi točkami. Stopnja vmesnosti točke u je definirana z 1 v n(v,t;u) ^ ~ (n-l)(n-2) Vite^Vit)9l0 n(v,t) kjer je n(v,t) število najkrajših poti od v do t, n(v,t;u) pa število najkrajših poti od v do t, ki gredo skozi u. Stopnja vmesnosti je realno število med 0 in 1. Tudi uteži posameznih povezav lahko naračunamo iz samega omrežja. Tako je utež povezave lahko število različnih ciklov omejene dolžine, ki vsebujejo to povezavo, 14 1. Uvod Razvrstitev C množice A je podmnožica množice njenih nepraznih podmnožic, torej C CVA\ {0}. To pomeni, da je C = {A,}, A* C A in At ^ 0. Kadar bomo želeli poudariti, da je C razvrstitev množice A, bomo namesto C pisali C {A). Razvrstitev C je ploska, če velja: i ^ j ==> A n A,- = 0. JVosz/ec razbitja C je unija vseh množic v tem razbitju. Na kratko ga označimo z [j C Razvrstitev C je razbitje, če je ploska in je njen nosilec enak celi množici A, torej če je [j C = A. Razbitju na k podmnožic bomo rekli tudi razbitje reda k ali fc-razbitje. Vsaki od množic v razbitju bomo rekli tudi skupina. Če se omejimo samo na končne množice, potem je tudi vseh različnih razbitij samo končno mnogo. Hitro lahko izračunamo, da je vseh razbitij reda 2 natanko 2n~l - 1, razbitij višjega reda pa je še precej več. Znano je, da je vseh fc-razbitij množice moči n natanko S(n, k), kjer je S(n, k) Stirlingovo število druge vrste. S(n, k) = ^ ]T(-1)* (k) (k - i)n Da bi dobili vtis o velikosti, si poglejmo nekaj takih števil: 5(24, 8) = 82 318 282 158 320 505 5(36, 9) = 54 294 340 536 065 700 496 358 447 625 5(50,10) = 26 154 716 515 862 881292 012 777 396 577 993 781727 011 Običajno nas zanimajo samo razbitja z določeno lastnostjo. Ena od lastnosti, ki nas večkrat zanima, je uravnoteženost razbitja. Ta je definirana kot razlika moči največje in najmanjše skupine, torej bal(C) := max {\Ai\: i = 1,... , k} - mm{\At\ : i=l,...,k} Razbitje C je uravnoteženo, če je bal(C) < 1. Izračunajmo, koliko je vseh uravnoteženih fc-razbitij množice moči n. Da bo izračun preprostejši, predpostavimo da je n deljiv s k. Vse skupine bodo tako enako velike (v vsaki bo s = f točk). Ker nas zanimajo samo bistveno različna razbitja, najprej izberemo prvi element prve skupine (ta element bo vedno v prvi skupini). Izmed preostalih n - 1 izberemo poljubnih s - 1 elementov in jih dodamo v prvo skupino. Preostalih n - s točk pa na podoben način razdelimo v k - 1 skupin. Tako pridemo do rekurzivne zveze S*(n,l) = 1 S*(n,k) = (U~l) S*(n-s,k-l) U- 1 Od tod dobimo rr (is ~ l~\ l\ s-l) S*(n,k)=lS l s_ 1 1.2. Osnovni pojmi iz teorije razvrščanja 15 Poglejmo si ˇse nekaj takih ˇstevil: S?(24,8) = 9 161 680 528 000 S?(36,9) = 388 035 036 597 427 985 390 625 S?(50,10) = 13 536 281 554 808 237 495 608 549 953 475 109 376 Tudi uravnoteˇzenih razbitij je zelo veliko, a kot vidimo v tabeli 1.1, jih je glede na vsa razbitja razmeroma malo. 24 8 1.11296 • 10-4 36 9 7.14688 • 10-6 50 10 5.17546 • 10-7 Tabela 1.1: Razmerja med S* in S Razbitje grafa Q je razbitje množice njegovih točk V. Ker je vseh možnih (pa tudi samo uravnoteženih) razbitij ogromno, pogosto postavimo dodatne zahteve, ki jih mora iskano razbitje izpolnjevati. Ker je v primeru končnega grafa tudi vseh razbitij samo končno mnogo, bi razbitje, ki ustreza vsem našim zahtevam, načeloma lahko poiskali s pregledom vseh dopustnih razbitij, a si tega ravno zaradi njihovega velikega števila ne moremo privoščiti. Znano je, da je večina problemov razbitja NP-težkih [2, 22, 13], kar pomeni, da zanje ni učinkovitega (polinomskega) postopka. Preprosto povedano to pomeni, da za te probleme zaenkrat ni znan noben postopek za iskanje optimalnega razbitja, ki bi bil bistveno hitrejši od pregledovanja vseh dopustnih razbitij, pa tudi upanja, da bi tak postopek našli, ni skoraj nobenega. Zato bomo morali namesto z optimalno biti zadovoljni tudi s približno rešitvijo. Preostane nam uporaba približnih postopkov, ki dajejo dobre (skoraj vedno skoraj optimalne) rešitve. Seveda pa obstajajo tudi polinomsko rešljivi problemi. Tak je na primer problem uravnoteženega razpolavljanja s čim manj povezavami iz ene v drugo skupino. Postopek je opisan v [24]. Glede na to, kakšne točke želimo imeti v isti skupini, ločimo dva osnovna pristopa k določanju razbitij. • Povezanostni pristop. Skupine želimo oblikovati tako, da bodo močno povezane točke v isti skupini, kar z drugimi besedami pomeni, da bo med skupinami čim manj povezav. Primer uporabe tega pristopa je na primer razdelitev n nalog med k procesorjev. Točke grafa so naloge, povezave pa določajo, kje je potrebna izmenjava podatkov. Skupine, ki jih iščemo, bodo določale, kateri procesor bo obdelal katero nalogo, da pa bi bilo izmenjave podatkov med procesorji čim manj, moramo poiskati skupine, med katerimi bo kar se da malo povezav. 16 1. Uvod Po drugi strani pa včasih želimo, da bi bilo povezav znotraj skupin čim manj, med skupinami pa čim več. Tak primer je barvanje grafa na n točkah s k barvami. V tem primeru bodo točke v isti skupini enako pobarvane, zato mora biti med njimi čim manj povezav, da bo barvanje čim boljše. • Podobnostni pristop. Skupine želimo oblikovati tako, da bodo točke, ki so podobno povezane s preostalimi točkami, v isti skupini. Ta pristop se veliko uporablja predvsem pri analizi družboslovnih omrežij - bločno modeliranje. Razvrstitev H množice A je hierarhija nad množico A, če je A^Aj G {0, A, A j}. Hierarhija H je polna, če je U^ = A Hierarhija H je osnovna, če za vsak x G [jH velja {x\ G H. Drugo poglavje Postopki za določanje razčlemb Znanih je precej postopkov za določanje čim boljših razčlemb grafa. Ločimo jih glede na različne lastnosti. Nekateri postopki na primer uporabljajo geometrijske lastnosti grafa (koordinate točk) in so zato uporabni samo za posebne vrste problemov, medtem ko drugi poleg grafa ne potrebujejo dodatnih podatkov. Večina postopkov res poišče iskano razčlembo, poznamo pa tudi take postopke, ki samo poskušajo izboljšati neko dano začetno razčlembo. Strogo deterministični postopki dajo pri istih podatkih vedno enak rezultat, obstajajo pa tudi postopki, ki uporabljajo kar precej naključnih odločitev. Postopki za razčlembo omrežij lahko uporabljajo druge znane postopke iz teorije grafov, ali pa problem obravnavajo samo kot poseben primer nekega drugega problema (kot je nelinearna optimizacija). V tem poglavju bomo pregledali nekatere znane postopke za razčlembo omrežij. Skoraj vsi postopki bodo predstavljeni za grafe brez vrednosti v točkah ali na povezavah, saj je posplošitev na grafe z vrednostmi v večini primerov zelo preprosta. Prav tako se ne bomo ukvarjali s tehničnimi podrobnostmi, kot so nepovezani grafi, na katere moramo biti pri izvedbi postopka še posebej pozorni. 2.1 Razpolavljanje Pri določanju k-razbitij grafa se zelo pogosto uporablja razpolavljanje. To je metoda, s katero najprej poiščemo čim boljše (običajno uravnoteženo) 2-razbitje danega grafa, nato pa rekurzivno razbijemo še obe skupini. Ideja izhaja iz dejstva, da je pri mnogih problemih razbitja število skupin enako neki potenci števila 2 (večina vzporednih računalnikov ima 7p procesorjev). Pri uporabi te metode moramo biti zelo pazljivi, saj se lahko zgodi, da bo končno k-razbitje daleč od optimalnega, tudi če znamo na vsakem koraku poiskati optimalno 2-razbitje [38]. Na sliki 2.1 je na desni strani prikazano 8-razbitje mreže 32 x 32, ki ga dobimo z razpolavljanjem (vsak korak je optimalen). Med skupinami tega razbitja je 128 povezav. Na desni strani iste slike pa je prikazano optimalno 8-razbitje istega grafa, kjer je povezav med skupinami samo 116. 17 18 2. Postopki za določanje razčlemb Slika 2.1: Slabo (levo) in optimalno (desno) 8-mzbitje mreže 32 x 32 Načeloma lahko z razpolavljanjem dobimo zelo slabo razbitje, a izkaže se, da za nekatere pomembne družine grafov (npr. ravninski grafi) dobimo rezultat, ki je kar blizu optimalnemu. Podobno velja tudi, če popustimo pri uravnoteženosti in dopustimo večje razlike v velikosti skupin. 2.2 Določanje razbitij z uporabo koordinat Včasih imamo na razpolago dodatne podatke o grafu, ki jih lahko koristno uporabimo pri določanju razbitja. V veliko primerih (na primer pri reševanju parcialnih diferencialnih enačb) tako poznamo tudi koordinate posameznih točk. Postopki, ki uporabijo te podatke o grafu, predpostavljajo, da sta točki, ki sta si blizu glede na položaj, tudi v grafu povezani s kratko potjo. Pravzaprav podatke o povezavah kar ignorirajo, kar zelo zmanjša njihovo uporabno vrednost v primerih, ko je povezanost točk v grafu pomembna (in znana). To pa tudi pomeni, da teh postopkov ne moremo posplošiti na grafe z uteženimi povezavami. 2.2.1 Koordinatno razpolavljanje Koordinatno razpolavljanje je najpreprostejši postopek, ki temelji na koordinatah točk. S tem postopkom poiščemo hiperravnino, pravokotno na izbrano koordinatno os, ki točke razdeli v dve enako veliki skupini. Če imamo na primer točke v ravnini in iščemo hiperravnino (premico), pravokotno na os y, moramo poiskati vrednost y, tako da bo polovica točk imela manjšo, druga polovica točk pa večjo koordinato y. Iskana premica je torej premica y = y. 2.2. Določanje razbitij z uporabo koordinat 19 Rekurzivno lahko ta poskopek uporabimo na dva načina. Pri prvem izberemo vedno isto koordinatno os, pri čemer dobimo ozke trakove. To ni ravno najbolje, saj imajo trakovi dolge robove, kar ima za posledico veliko povezav med skupinami (glej levi del slike 2.2). Pri drugem pristopu pa koordinatne osi izbiramo ciklično (prvič x, drugič y, ..., potem spet x, ...). Tako dobimo skupine z boljšim razmerjem v dolžini robov, kar pomeni manj povezav med skupinami (glej srednji del slike 2.2). Ena od težav s koordinatnim razpolavljanjem je v tem, da je odvisna od koordinat. V drugačnem koordinatnem sistemu lahko dobimo drugačno razbitje istega grafa (glej desni del slike 2.2). o—o—o—o o—o—o—o o—o—o—o o—o—o—o O-----O o—6 O-----O o—6 o—o o—6 o—o o—6 Slika 2.2: Težave pri koordinatnem razpolavljanju 2.2.2 Stabilno razpolavljanje Ta postopek (glej postopek 2.1) je podoben koordinatnemu razpolavljanju, razlika je samo v načinu, kako izberemo koordinatno os. Namesto ene od standarnih koordinatnih osi izberemo takšno os, da je vsota kvadratov razdalj posameznih točk do te osi čim manjša. Ker je večina točk grafa blizu te osi, so si tudi njihove projekcije na pravokotno hiperravnino blizu. To nam daje upanje, da je točk, ki so blizu te hiperravnine, malo, kar pomeni, da bo tudi povezav, ki potekajo iz ene v drugo skupino točk, malo. Poglejmo si, kako poiščemo takšno os. Naj bo Pi E \Rd položaj točke vi} i = 1,..., n. Iskana os je premica p, podana s točko T in normalizirano smerjo s, tako da je p = {T + as; a G IR}. Ker je p taka premica, da minimizira vsoto kvadratov razdalj točk do premice, hitro opazimo, da težišče točk leži na njej. Težišče je namreč točka, ki minimizira vsoto kvadratov razdalj do točke. Zato izberemo T l±pi n i=i _ 20 2. Postopki za določanje razčlemb Postopek 2.1 En korak stabilnega razpolavljanja Podatki: točke P1,P2,...,Pn Rezultat: skupini V1 in V2 izračunaj težišče T = L?=1 P sestavi matriko A = E"=1(P - T)(P - T)T (upoštevaj simetričnost) izračunaj lastni vektor s matrike A, ki pripada njeni največji lastni vrednosti izračunaj projekcije at = sTP poišči mediano a projekcij a* if an < a then točko Vi postavi v skupino V1 else točko t;* postavi v skupino V2 Naj bo P/ ortogonalna projekcija točke P na premico p, torej P[ = T + aiS, kjer je «i = sT(Pi-T). Potem je razdalja med točko P in premico p enaka & = ||P-P/||2. Ker je vektor P - P/ pravokoten na s, je ^=||p._T||2_ ||a.s||2 Izbrati moramo takšno smer s, da bo vsota kvadratov razdalj čim manjša. n T.d2 = Ellp*-Tll2 i=1 i=1 a 2 = J2\\P-T\\22-J2sT(P-T)(Pl-T)Ts i=1 i=1 n / n \ = X)HPi-Tll2-sT E(Pi-T)(Pi-T)T S Prvi sumand je neodvisen od s, torej je dovolj maksimizirati sTAs, kjer je n A = ]T(P-T)(P-T)T i=1 Toda matrika A je simetrična, zato lahko za vektor s izberemo kar normaliziran lastni vektor, ki pripada največji lastni vrednosti matrike A. To sledi iz [23]. Časovna zahtevnost postopka je 0(d 2 n), saj je edini časovno zahteven korak sestavljanje matrike A. 2.3 Doloˇcanje razbitij brez uporabe koordinat Poleg postopkov, ki potrebujejo podatke o koordinatah točk, obstaja tudi skupina postopkov, ki teh koordinat ne potrebujejo. Za svoje delovanje uporabljajo samo podatke o povezanosti med točkami. Ta skupina postopkov je veliko bolj uporabna, saj podatkov o koordinatah velikokrat nimamo. 2.3. Določanje razbitij brez uporabe koordinat___________ 21 Postopek 2.2 Požrešen postopek__________ Podatki: graf Q = (V, S), število skupin k Rezultat: skupine Vi, V2, ..., Vk for each v G V do used v := false: for i := 1 to k do begin izberi začetno točko u used[u] := true Vi := {u} while V dovolj majhna do begin izberi novo točko w usedw := true Vi := Vi U {w} end end 2.3.1 Poˇzreˇsni postopki Ena od prvih idej, ki jo dobimo, ko želimo poiskati razbitje grafa, je naslednja. Izberimo točko, nato pa na nek način dodajajmo druge točke, dokler skupina ne bo dovolj velika. Vsaka točka, ki jo dodamo, mora biti na nek način najboljša (na primer takšna, da bo število povezav med skupinami čim manjše), ali pa takšna, da se skupina povečuje na določen način (na primer v širino). Pričnemo lahko tudi z več začetnimi točkami (vsaka v svoji skupini) in vzporedno povečujemo skupine. Postopek 2.2 prikazuje najbolj preprost postopek te vrste. Spada v skupino požrešnih postopkov. Podrobnejši opis potrebujeta samo koraka za izbiro začetne in nove točke. Začetno točko za prvo skupino izberemo kot eno izmed točk, ki sta si na največji oddaljenosti v grafu. Začetno točko za druge skupine pa izberemo med prostimi točkami, ki so sosedne prejšnji skupini. Pri tem vedno izberemo tisto točko, ki ima najmanj prostih sosedov (točka v je prosta, če je usedv = false). Na podoben način izberemo tudi novo točko w (med vsemi prostimi točkami, ki so sosedne trenutni skupini, izberemo tisto, ki ima najmanj prostih sosedov). Če trenutna skupina nima nobene proste sosedne točke, izberemo prosto točko, ki je sosedna katerikoli drugi skupini. Opisani postopek poskuša sestaviti povezane skupine, saj vedno (če je to le mogoče) izbiramo med točkami, ki so sosedne trenutni skupini. Naslednji dobro poznan postopek, ki ga pogosto imenujemo tudi požrešni, je Farhatov postopek [19]. Podrobnejša analiza postopka pokaže, daje požrešna samo izbira začetnih točk. Spet moramo podrobneje opisati korak, kjer izberemo začetno skupino točk. Pri prvi skupini to naredimo podobno, kot prej (v začetno skupino damo eno izmed točk, ki sta si na največji oddaljenosti v grafu). Pri določanju drugih začetnih skupin pa 22 _________________2. Postopki za določanje razčlemb Postopek 2.3 Farhatov postopek Podatki: graf Q = (V, S), število skupin k Rezultat: skupine Vi, V2, ..., Vk for each v G V do usedH := false for i := 1 to k do begin izberi začetno skupino točk V for each m G V do used[m] := true while Vi dovolj majhna do for each uE Vi do for each w E N(u) do if usedM then begin usedH := true end end Vi := Vi U {w} v prejšnji skupini poiščemo točko z najmanj prostimi sosedi (a vsaj enim), te sosede pa potem vzamemo za začetno razbitje. Požrešni postopki so precej hitri. Njihova dobra lastnost je, da graf takoj razbi-jejo v k skupin, torej brez rekurzivnega razpolavljanja. To je še posebej uporabna lastnost, če željeno število skupin ni potenca števila 2. Tudi časovna zahtevnost je neodvisna od števila skupin. Po drugi strani pa kvaliteta dobljenega razbitja ni ravno najboljša. Pri večjem številu skupin se tudi pokaže, da zadnje skupine niso povezane. Kvaliteta dobljenega razbitja je pogostokrat odvisna od izbire začetne točke. A ker so ti postopki hitri, si lahko privoščimo in poiščemo več razbitij (pri različnih začetnih točkah), potem pa med njimi izberemo najboljše razbitje. Postopek Kernigan-Lin Eden od prvih postopkov za iskanje razbitij je postopek Kernigan-Lin [30]. Ta ne poišče razbitja, pač pa poskuša izboljšati neko začetno razbitje, pri čemer ni potrebno, da bi skupine začetnega razbitja bile enako velike. Postopek je kasneje doživel številne izboljšave, največje sta opravila Fiduccia in Mattheyses. Ta pristop se po avtorjih imenuje KL/FM. Prvotno je bilo mišljeno, da bi postopek izvedli na skupini naključnih razbitjih, potem pa izbrali najboljše dobljeno razbitje. Pri majhnih grafih dobimo kar smiselne rezultate, pri večjih pa je to precej neučinkovito. Zdaj se postopek uporablja predvsem za izboljšavo razbitij, ki jih dobimo z drugimi postopki. Postopek zamenjuje po dve sosedni točki, ki sta v različnih skupinah, če pri tem 2.3. Določanje razbitij brez uporabe koordinat 23 Postopek 2.4 En korak postopka Kernigan-Lin Podatki: omrežje M = (V, C, w), začetno razbitje (VA, VB) Rezultat: popravljeno razbitje (VA,VB) for each v G V do begin used H := false izračunaj vrednost di%] end fco := velikost prereza začetnega razbitja for i := 1 to min(|V,i|, |VB|) do begin med vsemi prostimi točkami poišči par (ai}bi) z največjo vrednostjo gain usedM := true used[h] := true for each v G N(at) U N(bt) do popravi vrednost diff H, kot da bi zamenjali točki a* in b{ h := h + gain(a,,6t) end poišči najmanjši j, tako da je kj = min^ zamenjaj prvih j parov točk (ai} h) dobimo boljše razbitje. Torej na grafu deluje lokalno in je primerna dopolnitev postopkov, ki na grafu delujejo globalno (taki so na primer koordinatno razpolavljanje in spektralni postopki). Če želimo dobiti čim bolj uravnoteženo razbitje, dovolimo samo premike točk iz večje v manjšo (ali enako veliko) skupino. Postopek ponavljamo, dokler se razbitje izboljšuje, lahko pa tudi dovolimo, da se začasno poslabša in upamo, da se bo kasneje veliko bolj izboljšalo. Postopek je lažje opisati za grafe z uteženimi povezavami, zato naj bo N omrežje (V, L, w), množica točk V pa naj bo razdeljena na dve ločeni skupini VA in VB- Naj vrednost diff(v) pove, za koliko se zmanjša velikost prereza (vsota uteži na povezavah med skupinama), če točko v prestavimo v drugo skupino. Z& v E VA je torej diS(v) = diS(v, VA, Vb) := ]T w((v ; b)) - ]T w((v ; a)) beVB aevA Če točko prestavimo iz ene skupine v drugo, se spremeni samo njena vrednost diff in vrednosti diff njenih sosedov. Vrednost gain para točk a G VA in b G VB pa naj bo sprememba v velikosti prereza, če obe točki prestavimo v drugo skupino. Očitno je gain(a, b) = gain(a, b, VA, VB) ¦= diff(a) + diff(fc) - 2wab En korak postopka Kernigan-Lin prikazuje postopek 2.4. 24 ________________2. Postopki za določanje razčlemb________________ 2.3.2 Spektralno razpolavljanje Spekralno razpolavljanje je popolnoma drugačen postopek od vseh do sedaj opisanih. Ne uporablja koordinat točk, pa tudi na samem grafu ne deluje, pač pa na matrični predstavitvi grafa. Medtem, ko drugi postopki skoraj ne potrebujejo operacij z realnimi števili, pa pri spektralnem razpolavljanju brez tega ne gre, saj postopek temelji na operacijah z matrikami in vektorji. Bistvo spektralnega razpolavljanja je določiti razbitje omrežja na osnovi izbranega lastnega vektorja matrike, dobljene iz podatkov o omrežju [12]. Različne spektralne metode se razlikujejo večinoma po matriki, katere lastni vektor iščemo [35, 36]. Najbolj zahteven del teh metod je ravno izračun lastnega vektorja, saj je pri velikih omrežjih tudi matrika, katere lastni vektor računamo, precejšnja, a ponavadi redka. Čeprav so spektralne metode znane že okoli 20 let, se je zanimanje zanje povečalo šele v zadnjih nekaj letih, ko so računalniki postali dovolj zmogljivi in ko so izboljšali metode za iskanje lastnih vektorjev redkih matrik. Standardni spekter Matrika, katere lastni vektor iščemo, je matrika sosednosti A z elementi j 1 če sta točki i in j povezani aij 0 sicer Fiedler je ugotovil, da ima druga najmanjša lastna vrednost A2 te matrike zelo zanimivo lastnost. Če je omrežje povezano, c poljubna realna konstanta, x pa lastni vektor, ki pripada lastni vrednosti A2, potem je povezano tudi podomrežje, določeno s točkami, ki imajo v lastnem vektorju x pripadajočo komponento manjšo ali enako konstanti c. Isto velja za točke, ki imajo ustrezno komponento v lastnem vektorju večjo ali enako konstanti c. Konstanto c običajno izberemo tako, da bo točke omrežja razdelila v dve približno enako veliki skupini. Laplaceov spekter Matrika, katere lastni vektor iščemo, je Laplaceova matrika L z elementi f -1 če je i ^ j ter sta točki i in j povezani kj = < deg (i) če je i = j { 0 sicer Matriko L lahko dobimo kot razliko L = D - A, kjer je D diagonalna matrika s stopnjami točk po diagonali, A pa matrika sosednosti, ali pa kot produkt L = QQT, kjer je Q incidenčna matrika velikosti |V| x |L| z elementi: {1 če je točka i začetek povezave j -1 če je točka i konec povezave j 0 sicer ___________2.3. Določanje razbitij brez uporabe koordinat___________ 25 Laplaceova matrika ima precej pomembnih lastnosti. Vse njene vrstične (in stolpčne) vsote so enake nič. Zaradi tega ima vsaj eno ničelno lastno vrednost, pripadajoči lastni vektor pa ima vse komponente enake. Ker je matrika L pozitivno semi-definitna, so vse ostale lastne vrednosti pozitivne, če je omrežje povezano. Če ni, je večkratnost ničelne lastne vrednosti natanko število povezanih komponent omrežja. Iz tega lahko sklepamo, da bo lastni vektor, ki pripada lastni vrednosti blizu ničle, razdelil točke omrežja v dve skoraj nepovezani skupini. V prvo skupino gredo točke, ki imajo v lastnem vektorju negativno komponento, v drugo pa točke s pozitivno komponento. Če želimo imeti bolj uravnoteženi skupini, lahko točke razporejamo tudi glede na srednjo vrednost (mediano) komponent lastnega vektorja namesto glede na ničlo. Z istim postopkom lahko nadaljujemo na manjših podomrežjih in tako prvotno omrežje delimo naprej. Ta metoda se imenuje RSB (rekurzivno spektralno razpolavljanje). Namesto, da s pomočjo ene majhne lastne vrednosti razdelimo omrežje na dva dela, lahko s pomočjo dveh ali več majhnih lastnih vrednosti razdelimo omrežje na več delov. Čeprav ima Laplaceov spekter precej zanimivih teoretičnih lastnosti, pomembnih pri razčlenjevanju omrežja, pa ima tudi nekaj slabosti. Ena je ta, da uporablja majhne lastne vrednosti. Lanczoseva metoda za iskanje nekaj (ne vseh) lastnih vektorjev namreč veliko hitreje najde lastni vektor, ki pripada največji lastni vrednosti, kot tistega, ki pripada najmanjši. Normalni spekter Matrika, katere lastni vektor iščemo, je normalna matrika N z elementi f . 1 če sta točki i in j povezani n-=< Vdeg W deg (•?') V [0 sicer Normalno matriko N dobimo kot kvadrat matrike X, ki temelji na povprečjih. Matriko X dobimo tako, da vzamemo matriko Q, na kateri temelji Laplaceova matrika L, ter vse elemente -1 zamenjamo z enicami. Vsako vrstico še delimo s kvadratnim korenom iz vrstične vsote, vsak stolpec pa s kvadratnim korenom iz stolpčne vsote (ta vsota je povsod enaka 2). Normalna matrika N je potem kvadratna matrika XXT. Podobno kot pri Laplaceovi matriki, lahko tudi tu takoj najdemo eno lastno vrednost in pripadajoči lastni vektor. Vsi elementi matrike N so namreč nenegativni in vse vrstične vsote so enake 1. To pomeni, da je N stohastična matrika, ter da ima lastno vrednost 1, pripadajoči lastni vektor pa ima vse komponente enake. Vse druge lastne vrednosti so po absolutni vrednosti manjše od 1 (če je omrežje povezano). Od tod sklepamo podobno kot v primeru Laplaceove matrike. Večkratnost lastne vrednosti 1 je ravno število povezanih komponent omrežja, iz lastnega vektorja, ki je 26 2. Postopki za določanje razčlemb 2.3.3 Večnivojske metode Z večnivojskimi metodami veliko omrežje poskusimo najprej smiselno zmanjšati, nato pa poiskati razbitje manjšega omrežja, kar je običajno precej hitreje. Razbitje osnovnega omrežja potem dobimo iz razbitja manjšega omrežja in podatkov o tem, kako je bilo to manjše omrežje zgrajeno. a) Poenostavitev omrežja (zmanjšamo število točk) Točke in povezave osnovnega omrežja najprej utežimo z utežjo 1, nato pa sestavimo zaporedje manjših omrežij Qi(Vi,Si), sestavljenih iz osnovnega omrežja Go(V0,Lo), tako daje \Vi\ < |V»_i|. Manjše omrežje običajno dobimo tako, da na prejšnjem omrežju poiščemo čim večje ujemanje, nato pa združimo krajišči povezav, ki so v ujemanju. Pri tem je utež nove točke vsota uteži prejšnjih točk, podobno pa velja tudi za povezave. S postopkom končamo, ko dobimo dovolj majhno omrežje, oziroma ko se novo omrežje od prejšnjega le še malo razlikuje. b) Razbitje manjšega omrežja Poenostavljeno omrežje vsebuje dovolj informacije (uteži na točkah in povezavah), da lahko poiščemo uravnoteženo razbitje, ki bo minimiziralo število povezav med posameznimi skupinami. c) Projekcija razbitja nazaj na osnovno omrežje Vsako točko v manjšem omrežju lahko nadomestimo z množico točk prvotnega omrežja, iz katerih je bila dobljena. Vendar nam to ne prinese najboljšega razbitja. Zato razbitje prvotnega omrežja rajši sestavimo po korakih (obratno od poenostavljanja), na vsakem koraku pa dobljeno razbitje izboljšamo še s kakšno hevristično metodo. Najbolj znan program za razčlembo velikih grafov, ki deluje po tem postopku [27, 29, 28] je METIS [26]. Avtor programa je George Karypis iz Univerze v Min-nesoti. Zadnja različica programskega paketa nosi oznako 4.0.1 (november 1998). Programi so v celoti napisani v jeziku ANSI C. To pomeni, da lahko izvorno kodo, ki jo dobimo na omrežju, prevedemo na kateremkoli operacijskem sistemu, ki ima standarden prevajalnik za jezik C, torej skoraj povsod. Iz izvorne kode si lahko naredimo knjižnice funkcij, ki jih potem uporabljamo v svojih programih. Na omrežju dobimo tudi že prevedene programe za okolje Windows. Sorodna paketu METIS sta še paketa parMETIS in hMETIS. Prvi je vzporedna različica osnovnega paketa, drugi pa je namenjen razčlembi hipergrafov. 2.4. Zaporedne modularne razčlembe 27 2.4 Zaporedne modularne razčlembe Modul grafa Q = (V, C) je takšna skupina točk C C V, da za vsako točko v G V \ C velja: t; je povezana z vsemi točkami iz C ali pa t; ni povezana z nobeno točko iz C. Trivialni moduli so 0, V in vse množice, ki vsebujejo eno samo točko. Moduli imajo močne algebraične lastnosti [14]. Če sta C in I? modula z nepraznim presekom, potem so presek, unija in razlika tudi moduli. Ločena modula sta bodisi povezana (vsaka točka prvega modula je povezana z vsako točko drugega modula), bodisi nepovezana (nobena točka prvega modula ni povezana z nobeno točko drugega modula). Modularna razčlemba je še ena od možnosti, kako dobiti razbitje danega grafa. Dobimo jo tako, da poiščemo čim bolj grobo razbitje množice točk na vsaj dva modula (tako razbitje je enolično določeno), potem pa rekurzivno razbijemo vsak netrivialen modul posebej. Slika 2.3 prikazuje eno od možnih razbitij grafa na module. Slika 2.3: Eno od možnih razbitij grafa na module Za določanje modularnih razčlemb obstaja veliko različnih postopkov. Enostavni imajo časovno zahtevnost 0(n3) ali celo 0(n4), obstajajo pa tudi postopki linearne časovne zahtevnosti [14, 32], ki pa so precej zapleteni. 2.5 Pajek Na koncu ne smemo pozabiti omeniti programa Pajek [4] za analizo velikih omreˇzij. Avtorja sta V. Batagelj (Univerza v Ljubljani, Fakulteta za matematiko in fiziko) in A. Mrvar (Univerza v Ljubljani, Fakulteta za druˇzbene vede). Vsi postopki, ki bodo opisani v nadaljevanju, so ˇze vkljuˇceni v ta program. 28 _________________2. Postopki za določanje razčlemb_________________ Poleg običajnih (usmerjenih, neusmerjenih in mešanih) omrežij Pajek podpira tudi delo z dvovrstnimi omrežji, kjer imamo točke dveh vrst (dve ločeni množici točk), povezave pa potekajo samo iz ene v drugo množico točk in delo s časovnimi omrežji, ki se spreminjajo skozi čas. Pajek omogoča tudi delo z drugimi strukturami, kot so razbitja, hierarhije, permutacije in vektorji. V Pajka je vključeno veliko znanih postopkov za analizo omrežij, postopkov za izračun najrazličnejših vrednosti na točkah in povezavah in postopkov za razčlenjevanje, omogoča pa tudi prikaz omrežja na različne načine. Tretje poglavje Prerezi in otoki 3.1 Točkovni otoki Pogosto nas v omrežju zanimajo skupine povezanih točk, katerih vrednosti so večje od vrednosti točk v okolici. Uveljavljen postopek, kako določiti takšne skupine točk (otoke), je z uporabo točkovnih prerezov. Točkovni prerez danega omrežja na nivoju t dobimo tako, da iz omrežja odstranimo vse točke (in pripadajoče povezave), katerih vrednost je manjša od t. Za lažjo predstavo in razumevanje postopkov bomo vrednosti v dani točki rekli kar višina točke. Omrežje s točkami na danih višinah nam torej določa nekakšno pokrajino. Definicija 3.1: Točkovni prerez omrežja M = (V, C,p) na nivoju t je podomrežje Mit) = [V, C,p), določeno z V = {ve V: piv) > t} C! = {(u-v)eC-.u,veV} Definicija 3.2: Neprazna skupina točk C C V je točkovni otok, če njene točke določajo povezan podgraf in so višine sosednih točk manjše ali enake višinam točk iz skupine. max piu) < min piv) ueN(c) v ~ vec y Definicija 3.3: Točkovni otok C C V je pravi točkovni otok, če so višine sosednih točk strogo manjše od višin točk iz skupine. max p(u) < mmp(v) ueN(c) vec Skupine točk, ki ustrezajo povezanim komponentam točkovnega prereza danega omrežja, izpolnjujejo vse zahtevane pogoje za prave otoke. Komponenta je povezana, višine točk v komponenti so vse večje ali enake t, višine točk v okolici pa so vse manjše od t. Komponente točkovnega prereza so torej pravi točkovni otoki. 29 30 3. Prerezi in otoki **r ?T' - - Slika 3.1: Točkovni prerez na enem m več nivojih Potrebujemo torej učinkovit postopek za določanje maksimalnih pravih točkovnih otokov omejene velikost. Pri tem bomo velikost otokov omejili navzdol in navzgor - otok ne sme biti niti premajhen, niti prevelik. 3.1.1 Splošni točkovni otoki Postopek za določanje maksimalnih pravih točkovnih otokov omejene velikosti temelji na točkovnih prerezih omrežja na vedno nižjih nivojih. Delovanje postopka bomo najlažje razumeli, če si predstavljamo, da celotno omrežje potopimo v vodo, nato pa gladino vode postopoma znižujemo in opazujemo, kakšni otoki se pojavljajo. Pri tem nam gladine vode ni treba zniževati zvezno, pač pa samo po višinah točk od najvišje do najnižje. Ko iz vode pokuka prva točka, je to vrh prvega otoka. Ko zagledamo drugo točko, je ta lahko vrh drugega otoka, ali pa pripada prvemu otoku (če je povezana s prvo točko). V splošnem iz vode že gleda nekaj otokov. Ko zagledamo novo točko v, je ta lahko povezana s katero od že vidnih točk, ali pa ne. Če ni povezana z nobeno vidno točko, je to vrh novega otoka, sicer pa združimo vse otoke, ki imajo kakšno točko povezano s točko v, dodamo točko v in tako dobimo nov, večji otok. Otoki, ki jih združimo v večji otok, postanejo vodotoki novega otoka, točka v pa njegovo pristanišče (tako jo poimenujemo zato, ker je to najnižja točka na otoku). Postopek 3.1 za določanje maksimalnih pravih točkovnih otokov omejene velikosti je sestavljen iz dveh delov. V prvem (pripravljalnem) delu postopka sestavimo množico otoki, ki določa, kako so otoki vsebovani eden v drugem. Za vsak otok izvemo, kaj so njegovi podotoki, katera točka je pristanišče ter ali je otok pravi. V drugem delu postopka pa v tej hierarhiji otokov poiščemo vse maksimalne prave točkovne otoke, katerih velikost je omejena s številoma min in max. Iskane otoke nam postopek vrne v množici L. 3.1. Točkovni otoki 31 Postopek 3.1 Maksimalni pravi točkovni otoki omejene velikosti_______________ Podatki: omrežje M = (V, C,p), števili min in max Rezultat: množica L vseh maksimalnih pravih točkovnih otokov velikosti vsaj min in največ max otoki := 0 uredi V nenaraščajoče glede na p for each veV (v dobljenem vrstnem redu) do begin otok := new Otok() otok.pristan := v otok.podotoki := {o G otoki: o D N(v) ^ 0} otoki := otoki U {otok} \ otok.podotoki for each o G otok.podotoki do o.pravi := p(o.pristan) > p(v) end for each o G otoki do o.pravi := true L:=0 while otoki ^ 0 do begin izberi otok G otoki otoki := otoki \ {otok} if |otok| < min then delete otok else if \otok\ > max V otok.pravi then begin otoki := otoki U otok.podotoki delete otok end else L:=LU {otok} end Pripravljalni del postopka pričnemo z urejanjem množice točk V nenaraščajoče po njihovih višinah. Nato spuščamo gladino vode od najvišje do najnižje točke, tako da vsakič iz vode pogleda ena nova točka (točke pregledamo v dobljenem vrstnem redu). Da postopka ne zapletamo po nepotrebnem, se točke, ki so na isti višini, iz vode ne pojavijo vse hkrati, pač pa ena za drugo (vrstni red ni pomemben). Z vsako novo točko v, ki pogleda iz vode, dobimo natanko en nov otok. Točka v je njegovo pristanišče, podotoki pa so tisti otoki, ki vsebujejo kakšno točko, povezano s točko v. Nov otok dodamo v trenutno množico otokov, iz nje pa odstranimo vse njegove podotoke. Teh otokov s tem ne izgubimo, saj do njih lahko še vedno pridemo kot do podotokov novega otoka. Ker nas zanimajo samo pravi otoki, si moramo za vsak otok še zabeležiti, ali je pravi. Tega pa ne moremo storiti takoj, ko otok nastane, pač pa šele kasneje, ko otok postane podotok večjega otoka. Otok je pravi, če je njegovo pristanišče višje od pristanišča večjega otoka. Vsi otoki, ki nam ostanejo ob koncu postopka, so pravi. 32 3. Prerezi in otoki 3.1.2 Enostavni točkovni otoki Definicija 3.4: Skupina točk C ? V je lokalni točkovni vrh, če je pravi točkovni otok in imajo vse njene točke enako višino. Definicija 3.5: Točkovni otok, ki ima en sam lokalni točkovni vrh, imenujemo enostaven točkovni otok. Poiskati vse maksimalne enostavne prave točkovne otoke omejene velikosti je razmeroma preprosto. Po vrsti moramo pregledati vse točke. Če je točka v lokalnem točkovnem vrhu še neodkritega otoka, smo našli nov enostavni točkovni otok. Poiskati moramo še vse točke, ki jih lahko dodamo temu otoku, tako da bo ostal enostaven. To storimo tako, da po vrsti dodajamo najvišje točke iz soseščine trenutnega otoka, dokler je izpolnjen pogoj za otok (končamo lahko že prej, če dosežemo največjo dovoljeno velikost otoka). Če je v soseščini trenutnega otoka več točk na isti višini, izberemo katerokoli izmed njih. Pred koncem postopka je morda potrebno še odstraniti nekaj točk (v obratnem vrstnem redu, kot smo jih dodajali), da dobimo pravi otok. Če je dobljeni otok premajhen, ga zavržemo, sicer pa je to eden od iskanih otokov. Izvedba tega postopka pa ni tako enostavna. Najprej moramo ugotoviti, katere točke pripadajo lokalnim točkovnim vrhovom. To storimo tako da po vrsti pregledamo vse še nepregledane točke. Če točka nima višjih sosedov, moramo poiskati vse točke na isti višini, ki so iz nje dosegljive. Če je v soseščini teh točk kakšna višja točka, si točke označimo za pregledane, sicer pa si jih označimo kot lokalni točkovni vrh. Med postopkom moramo vzdrževati tudi množico sosednih točk trenutnega otoka, iz katere vedno odstranjujemo najvišjo točko. Te točke je najbolje hraniti v kopici (najvišja točka bo vedno v korenu kopice), kar pomeni, da potrebujemo še operacije za delo s kopico. Veliko manj dela pa imamo, če samo dopolnimo postopek 3.1 za določanje splošnih točkovnih otokov, tako da ne bo vrnil vseh maksimalnih pravih točkovnih otokov omejene velikosti, pač pa samo tiste izmed njih, ki so tudi enostavni. Pripravljalni del postopka, kjer določimo vseh n otokov, dopolnimo tako, da vsakemu otoku določimo, kakšne vrste je. Vrsta otoka je lahko flat (vse točke 3.1. Točkovni otoki 33 Postopek 3.2 Maksimalni enostavni pravi točkovni otoki omejene velikosti Podatki: omrežje M = (V, C,p), števili min in max Rezultat: množica L vseh maksimalnih enostavnih pravih točkovnih otokov velikosti vsaj min in največ max otoki := 0 uredi V nenaraščajoče glede na p for each veV (v dobljenem vrstnem redu) do begin otok := new Otok() otok.pnstan := v otok.podotoki := {o E otoki: o D N(v) ^ 0} otoki := otoki U {otok} \ otok.podotoki for each o E otok.podotoki do o.pravi := p(o.pnstan) > p(v) if \otok.podotoki\ = 0 then otok.vrsta := flat else if \otok.podotoki\ = 1 then begin o := podotok if o.wrsta ^ flat then otok.vrsta := o.wrsta else if p(o.pnstan) = p(v) then otok.vrsta := flat else otok.vrsta := SINGLE end else begin for each o E otok.podotoki do begin ok := o.vrsta = flat A p(o.pnstan) = p{v) if ofc then break end if ok then otok.vrsta := flat else otok.vrsta := multi end end for each o E otoki do o.pravi := true L:=0 while otoki ^ 0 do begin izberi otofc E otoki otoki := otofcz \ {otok} if |otofc| < mm then delete otofc else if \otok\ > max V otok.pravi V otok.vrsta = multi then begin ofofcz := otofcz U otok.podotoki delete otofc end else L:=LU {otok} end 34 _______________________3. Prerezi in otoki_______________________ otoka imajo isto višino), single (otok ima en sam lokalni točkovni vrh) ali multi (otok ima več lokalnih točkovnih vrhov). Poglejmo si podrobneje, kako določimo vrsto novega otoka. • Če otok nima podotokov, je sestavljen iz ene same točke, torej je vrste flat. • Če ima otok samo en podotok, imamo tri možnosti. Če podotok ni vrste flat, torej če je vrste single ali multi, potem je tudi nov otok enake vrste. Če pa je podotok vrste flat, je vrsta novega otoka odvisna od višine pristanišča podotoka in višine nove točke. Če sta višini enaki, je tudi nov otok vrste flat, sicer pa dobimo otok vrste single. • Če pa ima otok več podotokov, moramo najprej preveriti, kakšni so ti podotoki. Če so vsi vrste flat in so vsa njihova pristanišča na isti višini kot nova točka, potem je tudi nov otok vrste flat, sicer pa je vrste multi. Pogoj v drugem delu postopka, ki odloči, ali je otok potrebno razbiti na podotoke in pregledati vsak podotok posebej, dopolnimo tako, da dodatno preverimo še, ali je otok vrste multi (tudi v tem primeru ga je potrebno razbiti). Postopek 3.2 prikazuje tako dopolnjen postopek 3.1, kjer je stara koda napisana v svetlejši barvi, da so dopolnitve bolj vidne. 3.1.3 Izvedba Predpostavimo, da je omrežje predstavljeno s strukturo Graph. Ker sama predstavitev omrežja v postopku ni bistvenega pomena, se v podrobnosti o tej strukturi ne bomo spuščali. Točko v omrežju bomo predstavili s strukturo Vert. Ta bo vsebovala celoštevilsko lastnost id z vrednostjo med 0 in n - 1, ki bo enolično določala točko. Vsebovala bo tudi realno lastnost value, v kateri bomo hranili vrednost točke. Na druge podatke o točki (na primer seznam sosedov) se v izvedbi postopka ne bomo sklicevali, zato so v opisu strukture izpuščeni. struct Vert { int id; // enolična oznaka iz [0,n) double value,- // vrednost }; Izkaže se, da je najprimernejša podatkovna struktura za predstavitev otoka drevo. Vsak otok namreč nastane z združitvijo točke, ki ji rečemo pristanišče (koren drevesa) z nekaj manjšimi otoki, ki jim rečemo podotoki (poddrevesa). Množica podotokov je lahko tudi prazna, kar pomeni, da ustrezno vozlišče v drevesu ne bo imelo poddreves (list). Ker vsako vozlišče v drevesu ustreza enemu otoku, ga bomo predstavili s strukturo VertIsland. Točka v vozlišču (lastnost port) je pristanišče otoka, poddrevesa pa predstavljajo podotoke. Ker ne vemo vnaprej, koliko podotokov bo imel _________________________3.1. Točkovni otoki_________________________35 posamezen otok, bomo poddrevesa vodili v obliki seznama. Tako bomo v vsakem vozlišču imeli kazalec na prvo poddrevo (lastnost subislands), ker pa skoraj vsako vozlišče ustreza tudi podotoku nekega večjega otoka, še kazalec na naslednje poddrevo v seznamu (lastnost next). Poleg tega bomo v vsakem vozlišču imeli zapisano še velikost otoka (lastnost size), da nam kasneje ne bo treba pregledovati celih dreves, da bi se dokopali do tega podatka. Pri sestavljanju novega otoka bo za dano točko v podotoku potrebno čim hitreje najti koren drevesa, v katerem se ta točka nahaja, da bomo to drevo pripeli kot poddrevo večjemu drevesu. Da bomo koren lahko poiskali, bomo v vsakem vozlišču potrebovali še kazalec na prednika v drevesu (lastnost parent). Pozabiti pa ne smemo še na logično lastnost regular, ki določa, ali je otok pravi. struct Vertlsland { int size; // velikost otoka Vert *port; // pristanišče Vertlsland *subislands,- // kazalec na prvi podotok Vertlsland *next; // kazalec na naslednji podotok Vertlsland *parent; // kazalec na prednika bool regular; // ali je otok pravi }; Za predstavitev vseh otokov, torej za vsa drevesa skupaj, bomo potrebovali natanko n vozlišč. Namesto da bi pomnilnik rezervirali za vsako vozlišče posebej, lahko ves potreben pomnilnik zanje rezerviramo kar v enem kosu (tabela vozlišč). Vozlišča v tabeli islands bomo zasedali po vrsti od začetka proti koncu tabele. Za dano točko bo treba znati hitro ugotoviti, ali je že vidna, oziroma ali že pripada kateremu od dreves, s katerimi so predstavljeni otoki. Ker imamo lahko več točk na isti višini, si z višinami točk pri odgovoru na to vprašanje ne moremo pomagati. Rešitev je v dodatni tabeli pos, ki za vsako točko vsebuje kazalec na koren drevesa, ki predstavlja otok, ki ima to točko za pristanišče. Če točka še ni vidna, ustrezni kazalec ne kaže nikamor. Pripravljalni del postopka je zdaj preprost. Po vrsti pregledujemo točke iz ne-naraščajoče urejene množice V in vsakič zasedemo eno vozlišče v tabeli. To vozlišče postane koren drevesa, ki predstavlja otok, ki ima trenutno točko za pristanišče. Na začetku je to drevo brez poddreves, torej je njegova velikost enaka 1. Potem pregledamo vse sosede trenutne točke. Če je sosed že v katerem od dreves (to vidimo v tabeli pos), moramo poiskati koren tega drevesa in drevo pripeti kot poddrevo k novemu vozlišču (najlažje ga pripnemo na začetek seznama poddreves). Kazalce na prednike v vseh vozliščih na poti do korena preusmerimo neposredno na koren novega drevesa. S tem si precej skrajšamo morebitne naslednje sprehode proti korenu drevesa (podobno kot pri postopku Union-Find). Pri iskanju korena drevesa, ki ustreza podotoku, se lahko pripeti, da je to drevo že pripeto kot podotok k novemu otoku. V tem primeru se iskanje korena ustavi pri vozlišču, ki ustreza novemu otoku. Seveda takrat ne smemo narediti ničesar več. 36 3. Prerezi in otoki Program 3.1: Maksimalni pravi točkovni otoki omejene velikosti int *vertlslands(Graph *g, int min, int max) { Vert *vert = vertices(g); int n = size(vert); qsort(vert, n, sizeof(*vert), vertDescending); Vertlsland *islands = new Vertlsland[n]; Vertlsland **pos = new Vertlsland *[n]; for (int i = 0; i < n; ++i) pos[i] = NULL; for (int i = 0; i < n; ++i) { Vert *v = vert[i]; Vertlsland *p = pos[v->id] = &islands[i]; p->size = 1; p->port = V; p->subislands = p->next = p->parent = NULL; p->regular = true,- for (Vert *u in neighbors(g, v)) { if (pos[u->id] != NULL) { Vertlsland *q = pos[u->id]; while (q->parent != NULL) { Vertlsland *t = q; q = q->parent; t->parent = p; } if (p != q) { q->parent = p; q->next = p->subislands; p->subislands = q; p->size += q->size; q->regular = q->port->value > v->value; } } } } int c = 0; int *part = new int[n]; while (n--) { Vertlsland *p = &islands[n]; if (p->parent != NULL) markVert(part, p, part[p->parent->port->id], p); else if (p->size < min) markVert(part, p, 0, p); else if (p->size > max | !p->regular) markVert(part, p, 0, NULL); else markVert(part, p, ++c, p); } delete [] pos; delete [] islands; return part; } Zdaj lahko med vsemi dobljenimi otoki poiˇsˇcemo maksimalne prave toˇckovne otoke omejene velikosti. Rezultat bomo vrnili v obliki razbitja - vsak otok bo svoja skupina, toˇcke ki ne pripadajo nobenemu ustreznemu otoku, pa bomo dali v _________________________3.1. Točkovni otoki_________________________37 posebno skupino z oznako 0. Razbitje predstavimo s tabelo celih števil, kjer vsaki točki določimo oznako skupine. Iskane otoke bi lahko poiskali s preprosto rekurzivno funkcijo, kjer bi pregledali vsa vozlišča dobljenih dreves. Če bi bil ustrezen otok premajhen, bi iskanje v globino prekinili, če bi bil prevelik ali nepravi, bi postopek ponovili na vseh poddrevesih, sicer pa bi ga označili kot novo skupino. A pri velikih omrežjih uporaba rekurzije ni priporočjiva, saj lahko hitro pride do prekoračitve na skladu. Ker pa so vsa vozlišča dreves zapisana v tabeli, se rekurziji lahko izognemo. Vozlišča dreves so v tabeli urejena tako, da je koren vsakega drevesa vedno za koreni vseh svojih poddreves. Ker iščemo maksimalne otoke ustrezne velikosti, bomo vozlišča pregledovali s konca proti začetku tabele. Tako bomo vsak otok pregledali prej, kot kateregakoli od njegovih podotokov. Poleg tega bomo vrednost lastnosti parent v vozlišču uporabili za to, da bomo razlikovali med nepregledanimi točkami in tistimi točkami, za katere že vemo, v katero skupino razbitja jih moramo postaviti. Pri nepregledanih točkah bo vrednost te lastnosti enaka NULL, pri drugih pa bo kazalec kazal na neposrednega prednika, torej na točko, ki bo določala oznako skupine. Po izteku pripravljalnega dela postopka je vrednost lastnosti parent v vseh vozliščih, ki predstavljajo glavne otoke, enaka NULL, pri tistih, ki predstavljajo podotoke, pa kaže na enega od prednikov v drevesu. To pa je ravno tisto, kar potrebujemo. Pregled točk torej poteka od konca proti začetku tabele. Če je znan prednik v drevesu, bomo točko postavili v isto skupino, v kateri je prednik, sicer pa otok, ki ustreza trenutni točki še ni bil pregledan. Če je ta otok premajhen, prevelik ali pa ni pravi, bomo točko postavili v skupino 0, sicer pa v novo skupino. Pri pregledu vsake točke moramo točkam v korenih poddreves še nastaviti kazalce na prednika, da bomo kasneje vedeli, kako jih obravnavati. Če moramo vse točke v poddrevesih postaviti v isto skupino kot trenutno točko, bomo kazalce na prednika v korenih poddreves nastavili na trenutno vozlišče. To naredimo v primerih, ko točko postavimo v isto skupino kot njenega prednika, če točko postavimo v novo skupino ali pa če je ustrezen otok premajhen. V vseh drugih primerih (otok je prevelik ali pa ni pravi) kazalce na prednika v korenih poddreves postavimo na NULL. S tem si označimo, da ustrezen otok še ni pregledan. Obe nalogi skupaj (postavljanje točke v skupino in nastavljanje kazalcev na prednika) opravlja pomožna funkcija markVert. Točko, ki ustreza pristanišču otoka, ki ga predstavlja vozlišče p, postavi v skupino c, korenom vseh poddreves pa nastavi prednika na q. Oznake skupin za posamezne točke vodimo v tabeli part, ki jo funkcija dobi za parameter. Ta tabela bi lahko bila tudi globalna, a to ne spada k pravilom lepega programiranja. Razširitev opisane izvedbe postopka, tako da bi lahko iskali tudi maksimalne enostavne prave otoke omejene velikosti, je preprosta. Potrebno je samo slediti dopolnitvam v postopku 3.2, zato se s tem tu ne bomo ukvarjali. 38 3. Prerezi in otoki void markVert(int *part, Vertlsland *p, int c, Vertlsland *q) { part[p->port->id] = c; for (p = p->subislands; p != NULL; p = p->next) p->parent = q; } 3.1.4 Časovna zahtevnost Poglejmo si še, koliko časa porabi opisani postopek za določanje maksimalnih pravih točkovnih otokov omejene velikosti. Za urejanje množice točk V potrebujemo O(n\ogv) CcLScL. V pripravljalnem delu postopka pregledamo vse točke, za vsako točko pa še vse njene sosede. Pogojni stavek, kjer preverjamo, ali je sosed trenutne točke že viden, se tako izvrši O {m) krat. Znotraj tega pogojnega stavka pa imamo še eno zanko, kjer se od vozlišča, ki predstavlja soseda trenutne točke v podotoku, pomikamo proti korenu. Ker med pomikanjem proti korenu vse povezave preusmerjamo neposredno na koren (podobno kot pri postopku Union-Find), porabimo za vse operacije skupaj O{ma{n)) časa, kjer je a obrat Ackermannove funkcije, ki narašča zelo počasi (še pri n = 265536 ima vrednost manjšo od 5). V zaključnem delu postopka imamo eno samo zanko, s katero pregledamo vsa vozlišča dreves, torej se izvrši natanko ra-krat. V vsaki ponovitvi te zanke imamo klic pomožne funkcije, v kateri pa je še ena zanka. Ta teče po vseh poddevesih. Vseh ponovitev te zanke je natanko toliko, kot je vseh poddreves, torej za zaključni del postopka potrebujemo O{n) časa. Ker je vrednost funkcije a za smiselne vrednosti n manjša od majhne konstante, je časovna zahtevnost celotnega postopka O(max{nlogn,m}). 3.1.5 Primer Poglejmo si omrežje avtorjev, ki je bilo dobljeno iz bibliografije [11] iz Computational Geometry Database geombib, verzija februar 2002 [25]. Dva avtorja sta povezana, če sta napisala vsaj en skupen članek. Utež na povezavi določa število skupnih člankov, a teh uteži ne bomo potrebovali. Z uporabo preprostega programa, napisanega v programskem jeziku Python, sem podatke iz oblike BibT E X predelal v obliko, ki jo razume Pajek. Dobljeno omrežje ima 9072 točk (avtorjev) in 22577 povezav (vsaj toliko je skupnih člankov ali knjig), od tega je 13567 povezav z utežjo 1. Pri predelavi podatkov iz oblike BibT E X je prišlo do številnih težav zaradi različnih načinov pisanja imen in priimkov avtorjev. Tako dobljeno omrežje vsebuje več točk, ki ustrezajo istemu avtorju. Na primer R.S. Drysdale, Robert L. Drysdale, Robert L. Scot Drysdale, R.L. Drysdale, S. Drysdale, R. Drysdale in R.L.S. Drysdale ali Pankaj K. Agarwal, P. Agarwal, Pankaj Agarwal in P.K. Agarwal. Ti so očitni in 3.1. Točkovni otoki 39 H. Tuy M. D. Altschuler M. A. Conger A. Levy N. Hodges S. J. Dwyer Erich Gamma D. Kimelman Ralph Johnson John Vlissides M. Yau L. Kuklinski Richard Helm H. I. Price K. R. Lee A. Rudich 40 3. Prerezi in otoki M. L. Marquez Garcia \G. Sanniti di Baja S. McCallum Xs' Am\n #R. Loos S. J. Wan O } J S. K. M. Wortg^ P. Prusinkiewiczj. Cohon ng ( Bruno Buchberger Collins E. Horowitz \B. Kutzler 9 SvSahni •_ . V. V. Ragnavan \ l>- Metna P. V. Sankar G. H. Hostetter Marina Gavrilova S. Wang S. Z. Wang M. D. Brice S. H. Bryant J. B. Williams J. R. Rodgers ) T. Shimanouchi J. G. Cleary Stephane Perennes Jerome Galtier M. Gautherie M. G. Vallet PSutLouis George \ E. Saltel F. Hech M. J. Castro-Diaz B. Mohammadi Houman Borouchaki Marku Markus Kukuk Andre Hinkenjann R. Ramaraj Matthias Otte G. M. Nielson Heinrich Muller R. Franke Hans Hagen A. Schmitt ) W. Leister B. Lang ~S. Abramowski Sabine Stifter Y. Won S. Nahar J. Bhasker O. Kennard H. Ratschek P. G. Bao M. Tasumi C. Cherfils F. Hermeline M. Stark B. Sarter M. Kreeb scal J. Fre 3.1. Točkovni otoki 41 S. Raghotama IL. G. Shapiro 0 V. Shapiro R. M. Haralick D. L. Vossler P. A. Koparkar L S. Raghothama G. Armstrong D. J. Sheehy D. J. Robinson S. J. Bridgett C. A. McGleenan D. J. leradi Cavit Aydin S. M. Dorney Doug J. lerardi .-E. Andersson n. i-. /^n-l. Desaulniers N. F. Stewart M. Boyer L. Paquette A. Inselberg 0 B. Dimsdale J. Rivero Chao-Kuei Hung #N. Megiddo D. T. Lee 0 y Jano Dan Halperin Kurt Mehlhorn Joseph S. B. Mitchell Godfried T. Toussaint onidas J. GuibasJack Scott Snoeyink Richard Pollack Joseph S. B. Mitchell V # Tetsuo A ^wlicha Sharir Mark H. Overmars David M. Mount M # Jorg-Rudiger ^ % Chee-Keng Yap Herbert Edelsbrunner (~ _ •_'%!„„, David P. Dobkin Robert E. Tarjanj Jorg-Rudiger Sack Chee-Keng Yap Herbert Edelsbrunner 'r- ^. n n "David P. Dobkin Franco P. Preparata Alok Aggarwal Pankaj K. Agarwal *f w,ln Emo Welz I • Danny Z. Chen Joseph O’Rourke Roberto Tamassia # Prabhakar Raghavan Jorge Urrutia Michael T. Goodrich L. Parida P. K. Ghosh S. P. Madur Y.-B. Chen M. Reif M. Hsieh H. Q. Lee T. Chomut 42 3. Prerezi in otoki Tudi za omrežja, ki imajo uteži na povezavah, lahko definiramo otoke. Da si bomo lažje predstavljali delovanje postopka, bomo uteži dane povezave rekli kar višina povezave. Podobno, kot pri točkovnem primeru, lahko povezavne otoke iščemo s pomočjo povezavnih prerezov. Povezavni prerez danega omrežja na nivoju t dobimo tako, da iz omrežja odstranimo vse povezave, katerih višina je manjša od t, ter vse točke, ki po odstranitvi teh povezav postanejo izolirane. Definicija 3.6: Povezavni prerez omrežja M = (V, C, w) na nivoju t je podomrežje M(t) = (V,C',w), določeno z C! = {eeC:w(e)>t} V = {veV:3ueV:(u;v)eC} Definicija 3.7: Neprazna skupina točk C C V je povezavni otok, če sta v skupini vsaj dve točki, če točke skupine določajo povezan podgraf in če obstaja vpeto drevo T na teh točkah, tako da so višine povezav, ki povezujejo točke iz skupine s točkami izven skupine manjše ali enake višinam povezav v drevesu T. max w((u;v))< min w(e) (u;v)ec-. eeL(T) ueC/w^C Definicija 3.8: Povezavni otok C C V je pravi povezavni otok, če obstaja vpeto drevo T, tako da so višine povezav, ki povezujejo točke iz skupine s točkami izven skupine strogo manjše od višin povezav v drevesu T. max w((u;v)) < min w(e) ueCAvgC Skupine točk, ki ustrezajo povezanim komponentam v povezavnem prerezu danega omrežja, izpolnjujejo vse zahtevane pogoje za prave povezavne otoke. Ker so to skupine točk, ki so po brisanju povezav z višino manjšo od t ostale povezane, obstaja vpeto drevo, ki vsebuje samo povezave na višinah, ki so večje ali enake t. Po drugi strani so višine povezav med skupinami vse manjše od t, sicer bi krajišči take povezave bili obe v isti skupini. Te skupine točk so torej pravi povezavni otoki. Podobno, kot pri točkovnem primeru, je tudi tu od izbire nivoja t odvisno, na koliko povezanih komponent razpade omrežje ter kako velike so te komponente. Najmanjša možna komponenta je sestavljena iz dveh točk (ker smo pobrisali vse izolirane točke), navzgor pa velikost ni omejena z drugim, kot z velikostjo celega omrežja. Treba bo torej zopet najti postopek, ki bo poiskal prave povezavne otoke omejene velikosti. 3.2. Povezavni otoki 43 3.2.1 Splošni povezavni otoki Pri določanju povezavnih otokov bomo poskusili uporabiti isto idejo, ki nas je pripeljala do točkovnih otokov. Podobno kot v točkovnem primeru, bomo tudi tu omrežje najprej potopili v vodo, nato pa gladino vode postopoma zniževali in opazovali, kakšni otoki se pojavljajo. Seveda nam gladine vode ni treba zniževati zvezno, pač pa po korakih po višinah povezav od najvišje do najnižje. Tudi tu bomo predpostavili, da povezave, ki so na isti višini, ne pridejo iz vode vse naenkrat, pač pa postopoma ena za drugo. Postopek 3.3 za določanje maksimalnih pravih povezavnih otokov omejene velikosti je zelo podoben postopku 3.1 za določanje maksimalnih pravih točkovnih otokov omejene velikosti. Da bo postopek bolj preprost, bomo malo popustili pri definiciji povezavnega otoka in dovolili tudi povezavne otoke, ki vsebujejo eno samo točko. Takemu otoku bomo rekli trivialen povezavni otok. Točke najprej razporedimo v n trivialnih povezavnih otokov, potem pa po vrsti pregledamo vsako povezavo od najvišje do najnižje. Če krajišči povezave pripadata istemu otoku, ne storimo ničesar, če pa pripadata dvema različnima otokoma, ta dva otoka združimo (v bistvu počnemo isto, kot če bi iskali maksimalno vpeto drevo s Kruskalovim postopkom). Tu opazimo tudi edino večjo razliko med točkovnim in povezavnim postopkom. V točkovnem primeru smo tekočo točko vedno dodali neki množici otokov (ki je lahko bila tudi prazna), v povezavnem primeru pa tekočo povezavo ignoriramo ali pa združimo natanko dva otoka (postaneta podotoka večjega otoka). Razlika je tudi, kako definiramo pristanišče. V točkovnem otoku je to bila najnižja točka na otoku, v povezavnem primeru pa je to povezava, s katero smo združili dva otoka (to ni nujno najnižja povezava med točkami na otoku). Otok, ki vsebuje eno samo točko, nima pristanišča. Za vsak otok si moramo tudi zabeležiti, ali je pravi. To lahko naredimo za oba podotoka šele takrat, ko ju združimo. Otok je pravi, če nima pristanišča ali pa če je njegovo pristanišče višje kot pristanišče večjega otoka. Ko zmanjka vode, nam ostane toliko otokov, kolikor povezanih komponent ima omrežje. A nas zanimajo samo pravi otoki omejene velikosti. Te poiščemo podobno, kot v točkovnem primeru. 3.2.2 Enostavni povezavni otoki Definicija 3.9: Skupina točk C ? V je lokalni povezavni vrh, če je pravi povezavni otok in obstaja vpeto drevo, v katerem imajo vse povezave enako višino kot najvišja povezava med poljubnima dvema točkama. Definicija 3.10: Povezavni otok, ki ima en sam lokalni povezavni vrh, imenujemo enostaven povezavni otok. 44 3. Prerezi in otoki Postopek 3.3 Maksimalni pravi povezavni otoki omejene velikosti_______________ Podatki: omrežje M ={V,C,w), števili min in max Rezultat: množica L vseh maksimalnih pravih povezavnih otokov velikosti vsaj min in največ max otoki := {{v} :veV} for each o G otoki do o.pnstan := null uredi C nenaraščajoče glede na w for each e{u ;v) G C (v dobljenem vrstnem redu) do begin 01 := otofc G ofofcz : m G otok 02 := otofc G otoki : t; G otofc if ol ^ o2 then begin otok := new Otofc() otok.pnstan := e otok.podotokl := ol otok.podotok2 := o2 otofcz := otofcz U {otofc} \ {ol,o2} ol.pravi := ol.pnsiara = null V w(ol.pnstan) > w{e) o2.pravi := o2.pnstan = null V w(o2.pnstan) > w{e) end end for each o G otoki do o.pmm := true L:=0 while otofcz ^ 0 do begin izberi otok G otofcz otofcz := otoki \ {otok} if \otok\ < mm then delete otok else if jofofcl > max V otok.pravi then begin otofcz := otofcz U {otok.podotokl, otok.podotok2} delete otofc end else L := L U {otofc} end Da bomo izmed vseh pravih povezavnih otokov izloˇcili samo enostavne, moramo otoku predpisati vrsto. Podobno, kot v toˇckovnem primeru, je vrsta otoka lahko flat (obstaja vpeto drevo, v katerem imajo vse povezave enako viˇsino kot najviˇsja povezava med poljubnima dvema toˇckama), single (otok ima en sam lokalni povezavni vrh) ali multi (otok ima veˇc lokalnih povezavnih vrhov). Poglejmo si podrobneje, kako doloˇcimo vrsto novega otoka. • Trivialen povezavni otok je vrste flat. 3.2. Povezavni otoki 45 - Če sta oba podotoka vrste flat in sta višini obeh pristanišč enaki višini trenutne povezave, je tudi nov otok vrste flat. - Če je samo en podotok vrste flat in je višina njegovega pristanišča enaka višini trenutne povezave, je nov otok vrste single. - V vseh ostalih primerih dobimo otok vrste multi. Pogoj v drugem delu postopka, ki odloči, ali je otok potrebno razbiti na podotoke in pregledati vsak podotok posebej, dopolnimo tako, da dodatno preverimo še, ali je otok vrste multi (tudi v tem primeru ga je potrebno razbiti). Postopek 3.4 prikazuje tako dopolnjen postopek 3.3, kjer je stara koda napisana v svetlejši barvi, da so dopolnitve bolj vidne. 3.2.3 Izvedba Podobno, kot pri točkovnem primeru predpostavimo, da je omrežje predstavljeno s strukturo Graph, točka v omrežju pa s strukturo Vert. Dodatno moramo še opisati, kako je predstavljena povezava med dvema točka. Povezavo opišemo s strukturo Edge, ki bo vsebovala kazalca na začetno in končno točko povezave (lastnosti source in target) ter višino povezave (lastnost value). Najprej se moramo odločiti, kakšno podatkovno strukturo bomo uporabili za predstavitev povezavnega otoka. Ker je povezavni otok ena sama točka, ali pa je sestavljen iz natanko dveh podotokov, bomo za njegovo predstavitev uporabili dvojiško drevo, ki bo imelo dve vrsti vozlišč. Vozlišče opišemo s strukturo EdgeIsland. V listih bo drevo imelo zapisane vse točke (lastnost vert), ki so na otoku, notranja vozlišča pa bodo hranila povezave (lastnost port), s katerimi smo združevali dva otoka v večji otok. Povezava v korenu drevesa bo torej pristanišče ustreznega otoka, poddrevesi (lastnosti left in right) pa bosta predstavljali njegova podotoka. Vsako vozlišče v drevesu bo moralo vsebovati podatek o tem, kdo je njegov prednik (lastnost parent). Le tako bomo za dano točko lahko ugotovili, kateremu drevesu pripada (poiskati bomo morali koren drevesa). Da pa se ne bomo pri vsakem iskanju korena pomikali vedno po isti poti, bomo po vsakem prehodu poti vsem vozliščem na poti podatek o predniku popravili, tako da bo kazal neposredno na koren (podobno kot pri postopku Union-Find). Poleg tega bomo v vsakem vozlišču imeli še podatek o velikosti otoka (lastnost size) ter podatek, ki pove, ali je otok pravi (lastnost regular). Za predstavitev vseh otokov bomo potrebovali n vozlišč za točke (listi) in največ n-1 vozlišč za povezave, skupno torej največ 2n-1 vozlišč. Namesto da bi pomnilnik 46 3. Prerezi in otoki Postopek 3.4 Maksimalni enostavni pravi povezavni otoki omejene velikosti Podatki: omrežje M ={V,C,w), števili min in max Rezultat: množica L vseh maksimalnih enostavnih pravih povezavnih otokov velikosti vsaj min in največ max otoki := {{v} :veV} for each o G otoki do o.pnstan := null for each o G otoki do o.ursia := flat uredi C nenaraščajoče glede na w for each e{u ;v) G C (v dobljenem vrstnem redu) do begin 01 := otok G ofofcz : m G otofc 02 := otofc G ofofcz : t; G otok if ol ^ o2 then begin otok := new OtokQ otok.pnstan := e otok.podotokl := ol otok.podotok2 := o2 otofcz := otofcz U {otofc} \ {ol,o2} ol.pravi := ol.pnsiara = null V w(ol.pnstan) > w{e) o2.pravi := o2.pnstan = null V w(o2.pnstan) > w{e) p\ := ol.vrsta = flat A (ol.pnstan = null V w(ol.pnstan) = w{e)) p2 := o2.vrsta = flat A (o2.pnstan = null V w(o2.pnsiara) = w{e)) if pi Ap2 then otok.vrsta := flat else if pi Vp2 then otok.vrsta := single else otok.vrsta := multi end end for each o G otofcz do o.pmm := true L:=0 while otofcz ^ 0 do begin izberi otok G otofcz otoki := otofc« \ {otofc} if \otok\ < mm then delete otok else if |ofofc| > max V otok.pravi V otok.vrsta = multi then begin otofcz := otofcz U {otok.podotokl, otok.podotok2} delete otofc end else L:=LU {otok} end rezervirali za vsako vozlišče posebej, lahko ves potreben pomnilnik zanje rezerviramo kar v enem kosu (tabela vozlišč). Vozlišča v tabeli islands bomo zasedali po vrsti 3.2. Povezavni otoki 47 struct Edge { Vert *source; // kazalec na začetno točko Vert *target; // kazalec na končno točko double value,- // vrednost }; struct Edgelsland { int size; // velikost otoka Vert *vert; // točka v listu Edge *port; // pristanišče Edgelsland *left; // kazalec na levo poddrevo Edgelsland *right; // kazalec na desno poddrevo Edgelsland *parent; // kazalec na prednika bool regular; // ali je otok pravi }; od začetka proti koncu tabele, pri čemer prvih n vozlišč za liste zasedemo takoj na začetku postopka. V pripravljalnem delu postopka najprej uredimo množico vseh povezav nenara-ščajoče, nato pa pripravimo prvih n vozlišč v tabeli islands. V glavni zanki nato po vrsti pregledamo vse povezave. Za trenutno povezavo e poiščemo vozlišči vi in v2, v katerih sta zapisani njeni krajišči. Nato poiščemo korena pl in p2 dreves, v katerih sta ti dve vozlišči vsebovani. Če sta vsebovani v dveh različnih drevesih, moramo ti dve drevesi združiti. To naredimo tako, da pripravimo novo vozlišče v tabeli, in ti dve drevesi postavimo za poddrevesi. Sproti še seštejemo velikosti poddreves, da dobimo velikost novega drevesa (število listov), nato pa se po poti od krajišč do korena sprehodimo še enkrat in vse kazalce na prednike preusmerimo neposredno na koren novega drevesa. Zaključni del postopka je zelo podoben tistemu pri točkovnem primeru. Edina razlika je v tem, kako točke na otoku postavimo vse v isto skupino. V točkovnem primeru smo točko v korenu postavili v novo skupino, vse druge točke v poddreve-sih pa v isto skupino, kot njihovega prednika. V našem primeru pa imamo točke samo v listih drevesa, drugje pa povezave, ki jih ne moremo razporejati po skupinah. Zato pri prvi povezavi naredimo novo skupino in vanjo postavimo krajišči povezave, krajišča drugih povezav v poddrevesih pa v isto skupino, kot je eno od krajišč prednika v drevesu. Nekatere od točk tako večkrat postavimo v isto skupino (namesto k različnih točk postavimo v skupino 2k - 2 točk, med katerimi je samo k različnih). Pomožna funkcija markEdge krajišči povezave, ki ustreza pristanišču otoka, ki ga predstavlja vozlišče p, postavi v skupino c, korenoma obeh poddreves pa nastavi prednika na q. Namesto lastnosti vert in port bi bilo dovolj imeti samo eno, saj lastnost vert potrebujemo samo v listih (trivialni otoki), lastnost port pa samo v notranjih vozliščih, ki predstavljajo poveyave. Ker pa sta to kazalca različne vrste, smo zaradi preglednosti raje ohranili obe lastnosti. 48 3. Prerezi in otoki Program 3.2: Maksimalni pravi povezavni otoki omejene velikosti int *edgeIslands(Graph *g, int min, int max) { Vert *vert = vertices(g); Edge *edge = edges(g); int n = size(vert); int m = size(edge); qsort(edge, m, sizeof(*edge), edgeDescending); EdgeIsland *islands = new EdgeIsland[2 * n - 1]; for (int i = 0; i < n; ++i) { islands[i].size = 1; islands[i].vert = vert[i]; islands[i].port = NULL; islands[i].left = islands[i].right = islands[i].parent = NULL; islands[i].regular = true; } int nn = n; for (int i = 0; i < m; ++i) { Edge *e = edge[i]; EdgeIsland *p1, *v1 = &islands[e->source->id]; EdgeIsland *p2, *v2 = &islands[e->target->id]; pl->parent); p2->parent); for (pi = vl; pl->parent != NULL; pi for (p2 = v2; p2->parent != NULL; p2 if (pi != p2) { Edgelsland *p = &islands[nn++]; p->size = pl->size + p2->size; p->vert = NULL; p->port = e; p->left = pi; p->right = p2; p->parent = NULL; p->regular = true,- pl->regular = pl->port == NULL || pl->port->value > e->value; p2->regular = p2->port == NULL || p2->port->value > e->value; for (pi = vl; pi != NULL;) { Edgelsland *pp = pi; pi = pl->parent; pp->parent = p,- } } for (p2 = v2; p2 != NULL;) { EdgeIsland *pp = p2; p2 p2->parent; pp->parent = p; } } int c = 0; int *part = new int[n]; for (int i = 0; i < n; ++i) part[i] = 0; while (nn > n) { EdgeIsland *p = &islands[--nn]; if (p->parent != NULL) markEdge(part, p, part[p->parent->port->source->id], p); else if (p->size < min) markEdge(part, p, 0, p); else if (p->size > max || !p->regular) markEdge(part, p, 0, NULL); else markEdge(part, p, ++c, p); } delete [] islands; return part; } 3.2. Povezavni otoki 49 void markEdge(int *part, EdgeIsland *p, int c, EdgeIsland *q) { part[p->port->source->id] = part[p->port->target->id] = c; p->left->parent = p->right->parent = q; } Opisano izvedbo postopka 3.3 bi lahko preprosto dopolnili, tako da bi dobili vse maksimalne enostavne prave povezavne otoke omejene velikosti. Dovolj je slediti navodilom v postopku 3.4. 3.2.4 Časovna zahtevnost Za urejanje množice povezav potrebujemo O(mlogm) časa, potem pa še O(n) časa za pripravo tabele vozlišč. Pri določanju vseh otokov moramo pregledati vse povezave, torej se glavna zanka izvrši m-krat, v zanki pa moramo poiskati poti od točk, ki predstavljata krajišči povezave, do korenov dreves, ki ti dve točki vsebujeta. Ker poti vsakič skrajšamo podobno kot pri postopku Union-Find, za gradnjo vpetega gozda potrebujemo O(ma(n)) časa, kjer je a obrat Ackermannove funkcije. Za zaključni del postopka, kjer določimo iskane otoke, potrebujemo O(n) časa, saj moramo pregledati največ n - 1 vozlišč, vsakič pa pokličemo pomožno funkcijo, ki ima konstantno časovno zahtevnost. Ker je m omejen s kvadratom ra-ja, lahko namesto log m pišemo kar logra. Ker a{n) narašča precej počasneje, kot logra, pa je skupna časovna zahtevnost postopka enaka O {m log n). 3.2.5 Primer Na britanskih univerzah so od junija 1968 do maja 1971 anketirali tamkajˇsnje ˇstudente. Za vsako od besed iz danega seznama so morali napisati besedo, ki jim pride prva na misel. Tako so dobili veliko omreˇzje, sestavljeno iz 23219 toˇck (besede) in 325624 usmerjenih povezav, med katerimi je tudi 564 zank. Zanima nas, katere so tiste skupine besed, ki so med seboj najbolj povezane. Uteˇzi na povezavah doloˇcimo tako, da za vsako povezavo preˇstejemo, na koliko tranzitivnih trikotnikih leˇzi. Tranzitivne trikotnike izberemo zato, ker nas poleg neposrednih povezav med besedami zanimajo tudi posredne, preko neke vmesne toˇcke. Ko na dobljenem omreˇzju poiˇsˇcemo vse povezavne otoke velikosti od 5 do 30, dobimo 53 otokov, ki vsi skupaj vsebujejo 664 toˇck. Nekateri od bolj zanimivih otokov so prikazani na slikah, ki sledijo. 50 3. Prerezi in otoki HAMPIONSHIP SINGING SING POP GROUP SONG TONE PLAYING FIVES BADMINTON SAXOPHONE MOTOR CYCLE COUCHES #PILLOW-CASE I^RM-CHAIR SLEEPING A AG i| •»^„...^„„ #~ N. \ iCOMFORTABLI COSltJESS (*y^HION \ \ \ j / ^sO\ \ \ 1COMFORT'" COZY m BEDDING SLUMBERS SLEEP MATTRESS RELAXED RELAXATION DRESSING-GOWN RELAXING" RESTING ¦SLEEPING LOUNGING DISTRAUGHT M \ ¦l.-" WHSFORTUNE \ jUNHAPPINESS BREATHLESS DESPAIR DISAPPOINTMENT JOYFUL LAUGHTER INFLICTION BALLS GYM LANE BACH STOP CO BED UNCOMFORTA*BLE R TIREDNESS TIRING ASLEEP MERRIMENT FORESEE SIGHT 3.2. Povezavni otoki 51 CLOTHING SMOCK FROM HOME DRY MARTINI LEMONADE i LEAKY BREAKWATER SHIPS PONDS WATERS > SEASIDE OCEAN SEASCAPE LAGOON AGAIN ALREADY MEANWHILE SOMETIME EDUCATION UNPAID THRIFTY DEALER LOOT PROPERTY SCIENTIFIC RESEARCH ATTRACTIVE DELIGHTFUL KEG BITTER TRAINING SHAPELY ACTIVITY 52 3. Prerezi in otoki Na eni od slik se lepo vidi, da so bili anketirani ˇstudenti. V otoku, ki vsebuje besedo work, so namreˇc veˇcinoma besede, ki so znaˇcilne za ˇstudentsko delo (activity, education, engineering, homework, learning, lecturer, lectures, lessons, maths, research, school, science, scientific, study, studying, teacher, teaching, training). 3.3 Lastnosti otokov Hitro opazimo, da so točkovni in povezavni otoki neodvisni od samih vrednosti točk ali povezav, pomembna je samo njihova medsebojna urejenost glede na višino. Torej lahko vrednosti točk in povezav preslikamo s katerokoli strogo naraščajočo realno funkcijo, ne da bi pri kakorkoli vplivali na otoke. Trditev 3.1: Sosednji točki ne moreta pripadati dvema ločenima pravima točkovnima otokoma. Dokaz: Naj bosta u in v dve sosednji točki. Točka u naj pripada otoku A, točka v pa otoku B. Po definiciji bi za višine teh dveh točk moralo veljati: p(u) < piv) in piv) < p(u), kar pa je nemogoče. D Trditev 3.2: Naj bo Hp(N) množica vseh pravih točkovnih otokov omrežja M. Potem je Hp polna hierarhija nad množico V. Dokaz: Pravi točkovni otok je po definiciji neprazna podmnožica množice točk V, torej je Hp razvrstitev množice V. Naj bosta A in B poljubna otoka iz Hp. Recimo, da je njun presek neprazen, različen od A in različen od B. To pomeni, da je A n B ^ 0, A g B in B g A, torej obstajajo točke v G A n 5, Ul G A \ B in u2 G B \ A. Ker točki v in Ul obe pripadata otoku A, vsak otok pa določa povezan podgraf, obstaja pot od v do ux po točkah iz A. Ker točka v pripada tudi otoku 5, moramo nekje na tej poti prestopiti iz množice B v množico A, torej obstaja vsaj ena točka zx G A n N(B). Na podoben način se prepričamo, da obstaja tudi pot od v do u2 po točkah iz B, na njej pa obstaja točka z2 G B n N(A). Ker je zx G A in z2 G N(A), mora biti p(zi) > p(z2), ker pa je z2 G B in Zl G N(B), mora biti tudi p(z2) > p(Zl). To pa je protislovje, torej mora biti A D B G {0, A, B}, kar pomeni, da je Hp hierarhija. Slika 3.2: Hp je polna hierarhija 3.3. Lastnosti otokov 53 Trditev 3.3: Naj bo HW(N) množica vseh pravih povezavnih otokov omrežja M. Potem je Hw hierarhija nad množico V. Dokaz: Pravi povezavni otok je po definiciji neprazna podmnožica množice točk V, torej je Hw razvrstitev množice V. Naj bosta A in B poljubna otoka iz Hw. Recimo, da je njun presek neprazen, različen od A in različen od B. To pomeni, da je A n B ^ 0, A g B in B g A, torej obstajajo točke v G A n B, ux G A \ B in u2 G B \ A. Ker je A povezavni otok, obstaja vpeto drevo, katerega povezave imajo vse večjo utež kot povezave, ki povezujejo točke na otoku s točkami izven otoka. Ker pa imamo v otoku A točko v G B in točko ux E A\B mora v tem vpetem drevesu obstajati povezava ex z enim krajiščem v B in drugim krajiščem v A \ B. Na podoben način se prepričamo, da v otoku B obstaja vpeto drevo, ki vsebuje povezavo e2 z enim krajiščem v A in drugim krajiščem v B\A. Od tod dobimo, da mora biti w(ei) > w(e2) in w(e2) > w(ei). To pa je protislovje, torej mora biti AC\B G {0, A, B}, kar pomeni, daje Hw hierarhija. Slika 3.3: Hw je hierarhija Hw pa ni nujno polna hierarhija. Če imamo v grafu kakšno izolirano točko, potem ta ne pripada nobenemu povezavnemu otoku. Če pa v grafu ni izoliranih točk, potem so množice točk, ki ustrezajo povezanim komponentam grafa, tudi pravi povezavni otoki, torej so v Hw. To pa pomeni, da je Hw polna hierarhija nad množico V natanko tedaj, ko graf ne vsebuje izoliranih točk. D Naj bo H(A; k, K) hierarhija nad množico A, ki vsebuje samo tiste množice iz H(A), katerih moč je med k in K, torej H(A; k, K) = {X G H{A) :k<\X\< K). Očitno je tudi H(A;k,K) hierarhija in H(A;k,K) C H{A), kjer je C običajna vsebovanost množic. Pravimo tudi, daje H(A; k, K) bolj groba hierarhija kot H{A). Če je H{A) polna hierarhija, pa H(A; k, K) ni več nujno polna. Trditev 3.4: Za h < k < K < Kx velja H(A; k, K) C H(A; h, K,). Dokaz: Naj bo X G H{A; k, K). Potem je k < \X\ < K. Ker pa je h < k in K < K1} je tudi h < \X\ < K1} torej je X G H{A; h, Ki). D Trditev 3.5: Za h < k < K < Kx velja H(A; k, K) = H({JH(A; kl} Ki); k, K). 54 3. Prerezi in otoki Dokaz: Tudi to je očitno. Če iz H najprej odstranimo vse množice, katerih velikost je manjša od kx ali večja od Ku nato pa iz dobljene hierarhije še vse tiste množice, katerih velikost je manjša od k ali večja od K, nam ostanejo natanko tiste množice iz H, katerih velikost je med k in K. D Bolj kot same hierarhije pa nas zanimajo omrežja, ki jih dobimo pri določanju otokov. Naj bo NP{N; k, K) omrežje pravih točkovnih otokov omrežja M, katerih velikost je vsaj k in največ K. To je podomrežje omrežja A/", določeno z množico točk \JHp{N;k,K). Zanima nas, ali lahko velikost točkovnih otokov omejujemo postopoma, torej ali lahko točkovne otoke še bolj omejene velikosti določimo kar na dobljenem omrežju točkovnih otokov omejene velikosti, ali pa moramo vse skupaj narediti spet na prvotnem omrežju. Izkaže se, da lahko. Trditev 3.6: Za kx < k < K < Kx veljaNP{N; k, K) = NP(NP(N; h,^); k, K). Dokaz: Recimo, da v omrežju M določimo vse prave točkovne otoke velikosti vsaj fci in največ Kx. Iz omrežja potem odstranimo vse točke, ki ne pripadajo nobenemu takemu otoku, skupaj z vsemi pripadajočimi povezavami. Dobljeno omrežje označimo z M- Povezane komponente tega omrežja so ravno maksimalni pravi točkovni otoki velikosti med h in K1} saj dva ločena točkovna otoka med sabo ne moreta biti povezana. Poglejmo sedaj, kaj se zgodi, če poskušamo velikost otokov še bolj omejiti. Ker je množica vseh pravih točkovnih otokov hierarhija, je vsak pravi točkovni otok velikosti med k in K vsebovan v nekem maksimalnem pravem točkovnem otoku velikosti med kx in Ku torej je vsebovan v eni od povezanih komponent omrežja M-Zato je vseeno, ali prave točkovne otoke velikosti med k in K iščemo v omrežju M ali pa v omrežju M- V obeh primerih dobimo iste otoke. ? Podobno definiramo tudi omrežje NW{N\ k, K) pravih povezavnih otokov omrežja M, katerih velikost je vsaj k in največ K. To je podomrežje omrežja M, določeno z množico točk \JHW{N; k,K), iz katerega dodatno odstranimo vse povezave med maksimalnimi otoki in vse povezave znotraj maksimalnih otokov, ki imajo manjšo višino kot pristanišče. Tudi za omrežje povezavnih otokov velja podobno, kot za omrežje točkovnih otokov. Trditev 3.7: Za kx < k < K < Kx velja NW{N; k, K) = NW(NW(N; k^K^; k,K). Dokaz: Recimo, da v omrežju M določimo vse prave povezavne otoke velikosti vsaj fci in največ Kx. Iz omrežja potem odstranimo vse točke, ki ne pripadajo nobenemu takemu otoku, vse povezave med maksimalnimi dobljenimi otoki in vse povezave znotraj maksimalnih otokov, ki imajo utež manjšo od uteži pristanišča. Dobljeno omrežje označimo z M- Povezane komponente tega omrežja so ravno maksimalni pravi točkovni otoki velikosti med kx in Ku saj smo odstranili vse povezave med maksimalnimi otoki, točke znotraj maksimalnih otokov pa so še vedno med seboj povezane, saj mora obstajata vpeto drevo, katerega povezave imajo vse večjo ali enako utež, kot pristanišče. 3.3. Lastnosti otokov 55 Zdaj pa naj bo A e Hp{ML) poljuben pravi točkovni otok omrežja NL. Naj bo t vrednost najnižje točke otoka A. Ta otok je podmnožica množice povezav omrežja M. Vsaka povezava iz A ima utež vsaj t, vse sosedne povezave pa imajo utež manjšo od t, ker imajo v omrežju ML vse sosedne točke vrednost manjšo od t. Ker vsak točkovni otok določa povezan podgraf, tudi množica povezav A določa povezan podgraf v M. Množica krajišč povezav iz množice A je torej pravi povezavni otok omrežja M. ? 56 _______________________3. Prerezi in otoki_______________________ Za konec si še poglejmo, ali obstaja kakšna povezava med pravimi točkovnimi in pravimi povezavnimi otoki na omrežju, kjer vrednost posamezne točke definiramo kot največjo utež njenih sosednih povezav. p(v) = max w((v;u)) (3.1) ueN(v) Naj bo A G Hp, torej je A pravi točkovni otok. Naj bo v pristanišče otoka A, t = p{v) pa njegova vrednost. Vsaka točka na otoku A ima potem vrednost večjo ali enako t, vsaka točka iz soseščine N{A) pa vrednost manjšo od t. Iz definicije vrednosti točk sledi, da mora imeti vsaka točka v omrežju vsaj eno sosedno povezavo z enako utežjo, kot je vrednost točke, hkrati pa je to tudi največja utež njenih sosednih povezav. Ker so vrednosti točk v soseščini N{A) vse manjše od t, so tudi uteži povezav, ki imajo eno krajišče na otoku A, drugo pa izven otoka, vse manjše od t. Za vsako točko na otoku A pa mora obstajati vsaj še ena točka znotraj otoka, do katere obstaja povezava z utežjo vsaj t. Od tod dobimo prvo ugotovitev, da vsi pravi točkovni otoki vsebujejo vsaj dve točki. Poglejmo si zdaj vse tiste povezave znotraj otoka A, ki imajo utež vsaj t. Če bi te povezave med seboj povezale vse točke otoka A, potem je A tudi pravi povezavni otok, torej A e Hw. Žal pa to ni vedno res, saj lahko te povezave razbijejo otok A na več povezanih komponent. Vsaka od teh komponent pa je pravi povezavni otok. Od tod sledi, da vsak pravi točkovni otok na nivoju t razpade na nekaj pravih povezavnih otokov na nivojih vsaj t. Preverimo še v drugo smer, torej ali je vsak pravi povezavni otok na nivoju t vsebovan v katerem od pravih točkovnih otokov na nivoju vsaj t. Hitro vidimo, da so vrednosti vseh točk na takem povezavnem otoku večje ali enake t, saj mora obstajati vpeto drevo, ki vsebuje samo povezave z utežmi vsaj t. Če k otoku dodamo še vse točke iz soseščine, katerih vrednost je vsaj t, pa dobimo iskani pravi točkovni otok na nivoju vsaj t. Povzemimo Izrek 3.9: Če v omrežju Af(V,C,w) definiramo funkcijo p: V -»• IR s predpisom 3.1, veljajo naslednje trditve. • Vsak pravi točkovni otok vsebuje vsaj dve točki. • Vsak pravi točkovni otok na nivoju t je sestavljen iz enega ali več pravih povezavnih otokov na nivoju vsaj t. • Vsak pravi povezavni otok na nivoju t je vsebovan v pravem točkovnem otoku na nivoju vsaj t. Četrto poglavje Sredice Eno od pomembnih vprašanj v analizi družboslovnih omrežij je prepoznavanje močno povezanih skupin točk. Takšne skupine so podmnožice točk, znotraj katerih so relativno močne povezave. Pri formalnem opisu takih skupin naletimo na različne pojme, kot so fc-klika, fc-pleme, fc-križ, fc-spletka, fc-sredica [37], množica lambda ... Za večino od njih se izkaže, da so algoritmično zelo zahtevni (NP težki ali vsaj kva-dratični), za določanje sredic, ki jih je že leta 1983 predstavil Seidman, pa obstaja zelo učinkovit postopek [9]. Po analizi takih gosto povezanih skupin točk lahko skupine stisnemo v eno samo točko ali pa jih cele odstranimo iz omrežja. Tako dobimo manjše, lažje obvladljivo omrežje, ki ga analiziramo naprej na isti način, ali pa kako drugače. Definicija 4.1: Podgraf H = (C, C\C) grafa Q = (V, C), določen z množico C C V, je sredica reda k ali k-sredica natanko tedaj, ko za vsak v G C velja: degH{v) > k, in je H največji podgraf s to lastnostjo. Sredici največjega reda rečemo tudi glavna sredica. Središčno število točke v je največji red sredice, ki vsebuje to točko. Pogosto tudi podmnožici točk C rečemo sredica, saj enolično določa podgraf H. Stopnjo točk lahko definiramo na različne načine. Stopnja je lahko število različnih sosedov, število vhodnih povezav, število izhodnih povezav, vsota števil vhodnih in izhodnih povezav ... Tako dobimo različne vrste sredic, vse pa imajo naslednje lastnosti. • Sredica reda 0 je vedno cel graf. Vsaka točka grafa ima namreč vsaj 0 sosedov. • Sredice so gnezdene. To pomeni, daje vsaka sredica vsebovana v vseh sredicah manjšega reda, torej sredice določajo gnezdeno razslojitev grafa. i < j => Hj c Hi Sredice niso nujno povezani podgrafi. Na sliki 4.1 vidimo primer, ko ima sredica reda 2 dve komponenti. To ni nič presenetljivega, saj že osnovni graf ni povezan. Na sliki pa lahko vidimo tudi dve komponenti sredice reda 3, ki pa ležita v isti komponenti prvotnega grafa. 57 58 4. Sredice Slika 4.1: Sredice redov 0, 1, 2 in 3 Množica vseh povezanih komponent posameznih slojev je hierarhija. Povezani komponenti v istem sloju imata namreč prazen presek, če pa gre za komponenti v različnih slojih, imata prazen presek ali pa je komponenta višjega sloja vsebovana v komponenti nižjega sloja. 4.1 Postopek za določanje hierarhije sredic V postopku za določanje hierarhije sredic moramo vsaki točki danega grafa izračunati njeno središčno število. Pri tem si pomagamo z naslednjo lastnostjo [6]: Če v grafu rekurzivno odstranimo vse točke stopnje manjše od k (in vse pripadajoče povezave), je preostanek grafa ravno sredica reda k. Postopek torej temelji na odstranjevanju točk. Pričnemo s celim grafom (sredica reda 0), kjer najprej odstranimo vse točke stopnje 0. Središčna števila odstranjenih točk so enaka 0. Iz dobljenega grafa (sredica reda 1) rekurzivno odstranimo vse točke stopenj 0 ali 1. Ostane nam sredica reda 2, odstranjene točke pa imajo središčno število enako 1. Postopek ponavljamo tako dolgo, da odstranimo vse točke. Središčno število točke, ki jo odstranjujemo, je maksimum njene trenutne stopnje in središčnega števila točke, ki smo jo odstranili pred njo. Točke grafa je potrebno najprej urediti naraščajoče glede na njihove stopnje, nato pa jih po vrsti odstranjevati iz grafa. Vsakič, ko odstranimo neko točko, se stopnja njenih sosedov zmanjša, zato moramo točke ustrezno preurediti. Opazimo še, da točk ni potrebno odstranjevati iz grafa, dovolj je že, da si samo zapomnemo, kakšne bi bile stopnje preostalih točk, če bi točko odstranili. Če je stopnja sosedne točke manjša od stopnje trenutne točke, potem je sosedna točka že bila obdelana in navidezno odstranjena iz grafa. V tem primeru ne naredimo ničesar. Če naletimo na sosednjo točko, ki ima isto stopnjo kot trenutna točka, imamo dve možnosti. Če je sosednja točka že bila obdelana, ne smemo narediti ničesar, če pa še ni bila obdelana, bo kmalu prišla na vrsto, njeno središčno število pa bo enako 4.2. Izvedba 59 Postopek 4.1 Določanje sredic__________________________ Podatki: graf Q = (V, C), predstavljen s seznami sosedov Rezultat: tabela core s središčnimi števili posameznih točk izračunaj stopnje točk (dobimo tabelo degree) uredi množico točk V nepadajoče glede na njihove stopnje for each v e V (v dobljenem vrstnem redu) do begin coreM := degreeH for each u G N(v) do if degree[u] > degree^] then begin degree[u] := degree[u] - 1 preuredi V end end središčnemu številu trenutne točke, torej nam ni treba storiti ničesar. Ukrepati moramo samo v primeru, ko naletimo na sosedno točko večje stopnje. Takšna točka še ni bila obdelana, zato moramo njeno stopnjo zmanjšati za 1 in preurediti množico točk. Tako pridemo do postopka 4.1. 4.2 Izvedba V začetku postopka moramo čim bolj učinkovito urediti množico točk glede na njihove stopnje. Ker so vse stopnje nenegativne, največja stopnja pa je običajno majhna glede na število točk, lahko uporabimo urejanje s koši. Vse točke z isto stopnjo damo v isti koš, v tabelo pa nato po vrsti zapišemo najprej točke iz prvega koša (točke s stopnjo 0), nato točke iz drugega koša (točke s stopnjo 1) ... Preurejanje množice točk je malo zahtevnejše. Tabelo je potrebno preurediti vsakič, ko neki točki zmanjšamo stopnjo za 1. Če si predstavljamo, da so točke v tabeli še vedno v koših, to pomeni, da moramo točko iz enega koša prestaviti v prejšnji koš. Ker položaj točk znotraj košev ni pomemben, lahko to naredimo tako, da točko, ki jo moramo prestaviti, zamenjamo s točko, ki je prva v istem košu, nato pa velikost prejšnjega koša povečamo za ena, začetek koša, v katerem je bila točka, pa pomaknemo za eno mesto v desno (velikost tega koša se pri tem zmanjša za ena). Da bi to lahko hitro izvedli, moramo poznati položaje točk v tabeli in začetke vseh košev (kje v tabeli se prične kateri koš). Če si predstavljamo, da so točke oštevilčene od 0 do n - 1, bi podatkovna struktura bila videti takšna, kot je prikazana na sliki 4.2. Izvedba postopka za določanje hierarhije sredic je narejena v programskem jeziku C++. Dani graf Q je predstavljen s strukturo Graph. Ker lahko graf predstavimo na več različnih načinov, strukture ne bomo podrobneje opisovali. Predpostavimo 60 4. Sredice deg 0 n-\ u '¦'! 0 , md vert pos Slika 4.2: Tabele v postopku določanja hierarhije sredic samo, da so točke grafa oštevilčene od 0 do n - 1. Uporabnik mora priskrbeti še funkcije size, degree in in neighbors, opisane v tabeli 4.1. Z uporabo primerne strukture za opis grafa G (seznami sosedov) lahko vse omenjene funkcije napišemo tako, da bodo imele konstantno časovno zahtevnost. Celoten postopek za določanje hierarhije sredic je izveden s funkcijo cores v programu 4.1, ki za parameter dobi podatke o grafu G, do katerih pridemo preko spremenljivke g. Rezultat funkcije je tabela, ki vsebuje središčna števila posameznih točk grafa G. Najprej definiramo nekaj pomožnih spremenljivk (03-04) in tabel (05-07). V spremenljivko n naračunamo velikost grafa (število točk v grafu). Tabela vert bo vsebovala točke grafa, urejene nepadajoče glede na njihove stopnje. Kje v tabeli vert se nahaja posamezna točka, bo zapisano v tabeli pos. V tabelo deg bomo naračunali stopnje posameznih točk, na koncu pa bomo v tej tabeli dobili njihova središčna števila. ime(parametri) rezultat size(G) degree(G,v) in neighbors(G,v število točk grafa G stopnja točke v v grafu G naslednji še neobiskan sosed točke v v grafu G Tabela 4.1: Opis funkcij, ki jih mora priskrbeti uporabnik 4.2. Izvedba 61 Program 4.1: Določanje sredic v enostavnih neusmerjenih grafih 01 int *cores(Graph *g) 02 { 03 int v, d; 04 int n = size(g); 07 int *vert = new int [n]; 06 int *pos = new int [n]; 05 int *deg = new int [n]; 08 09 int md = 0; 10 for (v = 0; v < n; ++v) { 11 deg[v] = degree(g, v); 12 if (deg[v] > md) md = deg[v]; 13 } 14 15 int *bin = new int[md + 1]; 16 for (d = 0; d <= md; ++d) bin[d] = 0; 17 for (v = 0; v < n; ++v) ++bin[deg[v]]; 18 19 int start = 0; 20 for (d = 0; d <= md; ++d) { 21 int num = bin[d]; 22 bin[d] = start; 23 start += num; 24 } 25 26 for (v = 0; v < n; ++v) { 27 pos[v] = bin[deg[v]]++; 28 vert[pos[v]] = v; 29 } 30 31 for (d = md; d > 0; --d) bin[d] = bin[d - 1]; 32 bin[0] = 0; 33 34 for (int k = 0; k < n; ++k) { 35 v = vert[k]; 36 for (int u in neighbors(g, v)) { 37 if (deg[u] > deg[v]) { 38 int du = deg[u]; 39 int pu = pos[u]; 40 int pw = bin[du]; 41 int w = vert[pw]; 42 if (u != w) { 43 pos[u] = pw; vert[pu] = w; 44 pos[w] = pu; vert[pw] = u; 45 } 46 ++bin[du]; 47 --deg[u]; 48 } 49 } 50 } 51 52 delete [] vert; 53 delete [] pos; 54 delete [] bin; 55 return deg; 56 } 62 4. Sredice Stopnje točk izračunamo v zanki (10-13), tako da za vsako točko pokličemo funkcijo degree. Hkrati izračunamo še največjo stopnjo md. Ko vemo, kakšna je največja stopnja, lahko ustvarimo še eno pomožno tabelo. To je tabela bin, v kateri bomo za vsako možno stopnjo imeli indeks, kje v tabeli vert se pričnejo točke te stopnje. Grafičen prikaz uporabljenih tabel je na sliki 4.2. Nato uredimo točke v naraščajočem vrstnem redu po njihovih stopnjah. Pri tem uporabimo urejanje s koši (15-29). Najprej preštejemo, koliko točk bo v posameznem košu (15-17), pri čemer so v istem košu točke z isto stopnjo. Koši so oštevilčeni od 0 do md. Iz podatkov o velikosti košev lahko določimo (19-24) začetne položaje košev v tabeli vert. Koš 0 se prične na mestu 0, drugi koši pa na mestu, ki je enako vsoti začetnega položaja in velikosti prejšnjega koša. Da bi se izognili dodatni tabeli, za shranjevanje začetnih položajev uporabimo kar isto tabelo (bin). Nato lahko zapišemo točke grafa g v tabelo vert (26-29). Za vsako točko vemo, kateremu košu pripada in kakšen je začetni položaj tega koša. Točko zapišemo na ustrezno mesto, v tabelo pos zapišemo njen položaj, in povečamo začetni položaj koša, ki smo ga uporabili. Ko se zanka izteče, so točke urejene po stopnjah. V zadnjem koraku pripravljalne faze moramo povrniti začetne položaje košev na stare vrednosti (31-32). V prejšnjem koraku smo jih večkrat povečali, ko smo zapisali točke v ustrezne koše. Očitno je, da je spremenjen začetni položaj ravno prvotni začetni položaj naslednjega koša. Dovolj je torej samo prepisati vrednosti v tabeli bin za eno mesto v desno. Začetni položaj koša 0 postavimo nazaj na 0. Glavna zanka (34-50) ustreza zanki for each v postopku 4.1. Zanka teče po vseh točkah v grafa g v vrstnem redu, določenem s tabelo vert. Središčno število tekoče točke v je ravno trenutna stopnja te točke, ki je že zapisana v tabeli deg. Vsaki sosedni točki u točke v, ki ima večjo stopnjo, moramo zmanjšati stopnjo in jo prestaviti za en koš v levo. To je operacija, ki jo opravimo v konstantnem času. Najprej zamenjamo točko u in prvo točko v istem košu. V tabeli pos zamenjamo tudi njuna položaja. Na koncu povečamo začetni položaj koša (s tem povečamo velikost prejšnjega in zmanjšamo velikost trenutnega koša). 4.2.1 Časovna zahtevnost Za izračun stopenj točk (10-13) potrebujemo O(n) časa. Urejanje s koši (15-32) je sestavljeno iz petih zank velikosti največ n. Vsaka se izvede v konstantnem času, torej je celotna časovna zahtevnost urejanja O(n). Stavek (35) je konstantne časovne zahtevnosti, izvede se za vsako točko enkrat, torej prispeva O{n) k časovni zahtevnosti postopka. Pogojni stavek (37-48) je tudi konstantne časovne zahtevnosti. Ker se izvrši za vsako povezavo v grafu največ dvakrat, je prispevek zanke (36-49) v vseh ponovitvah zanke (34-50) ravno O(max{m,n}). 4.3. Primer 63 4.2.2 Prilagoditev postopka za druge vrste sredic Da bi opisani postopek deloval tudi na grafih z usmerjenimi povezavami in zankami, so potrebni samo malenkostni popravki, odvisno od tega, kako definiramo stopnjo toˇcke. V primeru vhodne (izhodne) stopnje mora funkcija in neighbors v vrstici ˇ 36 vrniti naslednjega ˇse neobiskanega izhodnega (vhodnega) soseda. Ce je stopnja definirana kot vsota vhodne in izhodne stopnje pa mora vrniti naslednjega ˇse neobi-ˇ skanega vhodnega ali izhodnega soseda. Ce je neka toˇcka vhodni in izhodni sosed, ga mora funkcija vrniti dvakrat. Maksimalna stopnja toˇcke je v tem primeru lahko najveˇc 2n - 2, na kar moramo paziti pri rezerviranju pomnilnika za tabelo bin. 4.3 Primer Knuthov slovar angleških besed [31] je omrežje, ki ima 52652 točk (angleške besede dolžine od 2 do 8 znakov) in 89038 povezav. Dve točki (besedi) sta povezani, če lahko eno besedo dobimo iz druge tako, da zamenjamo, odvzamemo ali dodamo eno črko. Dobljeno omrežje je redko, saj je povprečna stopnja komaj 3.382. Rezultati programa so prikazani v tabeli 4.2. točke s središčnim številom k velikost sredice reda k k # % # % 25 26 0.049 26 0.049 16 34 0.065 60 0.114 15 16 0.030 76 0.144 14 59 0.112 135 0.257 13 82 0.156 217 0.412 12 200 0.380 417 0.792 11 202 0.384 619 1.176 10 465 0.883 1084 2.059 9 504 0.957 1588 3.016 8 923 1.753 2511 4.769 7 1114 2.116 3625 6.885 6 1590 3.020 5215 9.905 5 2423 4.602 7638 14.507 4 3859 7.329 11497 21.836 3 5900 11.206 17397 33.042 2 8391 15.937 25788 48.978 1 13539 25.714 39327 74.693 0 13325 25.308 52652 100.000 Tabela 4.2: Sredice v primeru Knuthovega slovarja angleˇskih besed 64 4. Sredice Slika 4.3: Matrika sosednosti sredice reda 16 brez sredice reda 25 Sredica reda 15 ima dodatnih 16 toˇck (ow, bow, cow, Dow, how, jow, low, mow, now, pow, row, sow, tow, vow, wow, yow). To je spet klika, saj se besede razlikujejo samo v prvih ˇcrkah. 4.4 Primer Delovanje postopka si poglejmo še na omrežju avtorjev geombib [25]. Sumarni rezultati so predstavljeni v tabeli 4.3. 4.4. Primer 65 Sredica Frekvenca KumFrekv% Predstavnik 0 1185 16.1378 N. Bourbaki 1 2218 46.3435 S. Kambhampati 2 1714 69.6854 G. Bilardi 3 1023 83.6171 Y. I. Yoon 4 503 90.4671 B. B. Kimia 5 248 93.8445 C. A. Duncan 6 122 95.5059 T. M. Murali 7 126 97.2218 J. M. Kleinberg 8 34 97.6849 F. F. Yao 9 37 98.1888 K. R. Lee 10 20 98.4611 H. Alt 11 52 99.1693 M. Flickner 13 1 99.1829 M. H. Overmars 14 7 99.2782 M. Sharir 15 14 99.4689 N. M. Amato 16 17 99.7004 D. White 21 22 100.0000 L. J. Guibas Vsota 7343 Tabela 4.3: Porazdelitev središčnih števil Točke stopnje 0 so izolirane točke - avtorji brez soavtorjev. Sredica reda 21 (glavna sredica) je sestavljena iz 22 točk, kjer ima vsaka točka vsaj 21 sosedov znotraj sredice (očitno je to klika). Na sliki 4.4 je prikazan podgraf, porojen s točkami iz sredice reda 10 (in višjih). Ima 133 točk. Te so obarvane različno (sivi odtenki) glede na središčno število. Slika je bila dobljena z uporabo avtomatskega risanja s postopkom Kamada-Kawai. Nekatere točke so bile dodatno rahlo prestavljene, da so oznake lažje berljive. Glavna sredica je sestavljena iz najtemnejših točk v sredini spodnjega dela slike. Na njo se povezujejo sredice nižjih stopenj. Podrobnejši pogled v prerez na nivoju 15 razkrije, da tudi točke s središčnim številom 15 tvorijo kliko reda 14. Ta klika je močno povezana s skupino avtorjev (P. K. Agarwal, D. P. Dobkin, L. J. Guibas, C.-K. Yap, H. Edelsbrunner, D. Eppstein, J. S. Snoeyink, L. P. Chew in M. W. Bern) iz glavne sredice. Drugi člani glavne sredice sodelujejo v glavnem samo med seboj. Dve skupini s središčnima številoma 16 in 11 (obe sta spet kliki) sta povezani z ‘zveznimi’ avtorji (Scott A. Mitchell in D. T. Lee) iz glavne skupine. Opazimo tudi, daje vrstni red avtorjev glede na središčna števila rahlo drugačen, kot vrstni red glede na njihove stopnje (avtorji in število različnih soavtorjev): L. J. Guibas (102), P. K. Agarwal (98), J. S. Snoeyink (91), H. Edelsbrunner (90), M. H. Overmars (88), M. Sharir (87), J. O’Rourke (85), R. Tamassia (79), J. S. B. Mitchell (76), C.-K. Yap (76), E. Welzl (74), D. P. Dobkin (73), G. T. Toussaint (72), M. T. Goodrich (70), K. Mehlhorn (69), R. E. Tarjan (69). 66 4. Sredice Mvl.Yvinec ^J-M Robert r\ Mj.Devillers p r~\ "^—^_^ Q.Lazard ^ ^.D.Demaine „ Mt/l.T.deBerg Me.Asano Qj.Katoh Q- p C) MJ.LSouvaine ^ p, ".G.Tollis Q/l.Teillaud ^R00S ^H.Overmars Q, Rofe ^-R.Sack^.Alt Q, |ma| ^?.Seidel m.O’Rourke r\ ^vl.T.Goodrich ^?.Seidel ^J.O Rourke p\ ^vl.T.Goodrich p „ A Mj.Halperin A, _, ,„ ,™\ atn ^-d.Erickson- % Sharir "-S.Suri ^-J.S.Wter ¦fJ.M.Amato ^.Mehlhorn ^.Pollack ' Qj.Chazelle Q^W.Cheng^ZCnen ^.Wenger ^.Schwarzkopf^S|_°eyink %E.Hershberger * •,,<, n «i A ^.K.Agarwal A ^.Tamassia ^.LS.Drysdale r\ J.Pach *tWelzl A ~ l, ^.P.Preparata p a u y ^..J.Guibas (~\ MvKedem ^S.J.Fortune «-, "J.Guibas Q MvKedem ^S.J.Fortune f~\ S.C.Clements * % Eppstein #, A %K.Yap ^Matousek (_L G Kirkpatrick r ^.S.Sawhney «1 •;-,-¦ hi ^.A.Mitchell j* ^B.Aronov ^ p, MJ.Ashley D.White ^. l rimble » ^.Edelsbrunner ^J.P.Dobkin v_^ Aurenhammer MJ-T.Lee r\ r ¦ ^vl.W.Bern a pi ' Mj.Steele ^n/ ff a ^/1.W.Bern gh pi ' ^.D.SjaaTrrfa ^RL°b- * K Dey • A , ^^ ^A"arWa' Q.R.Kosaraju ^ ~ j i.rv.ucy ^j.Amenta v-P.Yanker MJ.Petkovic A. ,—n A A Gi u ^B.Lerman •hj.VWIson »JRHipp -L.Lopez-Buriek ^.Rassmann JHass %Sedgwick t;.K.Johnson Q,.Flickner Ckoorkani %/.R.Oakes ^ ^ •KjTautges ^™ %Letscher ^H %Grimm •r.LEdwa.ds ¦ ^,,enz|ey ^ZOnn ,W«kS Q^^ Slika 4.4: Računska geometrija: sredica reda 10 Števila skupnih člankov, ki jih imata dva avtorja, v tem primeru nismo upoštevali. Da bi upoštevali tudi vrednosti na povezavah, bi morali uporabiti posplošen postopek za določanje sredic [8]. Tudi ta je učinkovit (podkvadratičen), njegova časovna zahtevnost je C(m-max{ A, log n}), kjer je A maksimalna stopnja v omrežju. 4.5 Posplošitev sredic Do sedaj je pri določanju sredic edino vlogo igrala stopnja posameznih točk. Namesto stopnje pa bi lahko uporabili tudi kakšno drugo funkcijo. Pri izbiri funkcije imamo veliko možnosti, še posebej, če imamo v grafu podane vrednosti točk ali uteži na povezavah. To nas pripelje do posplošitve pojma sredice. Definicija 4.2: Točkovna funkcija p na omrežju M ali krajše p-funkcija je funkcija p(v,C), veV,CCVz realnimi vrednostmi. Poglejmo si nekaj primerov točkovnih funkcij. . P1(v,C) = deg(v,C) • p2(v,C) = mdeg(v,C) • p3(v,C) = outdeg(v,C) p4(v, C) = indeg(w, C) + outdeg(w, C) 4.5. POSPLOŠITEV SREDIC 67 • p5(v,C)= J2 w((v;u)),kieriew:L^\R+ ueN(v,C) • Pe(v,C)= max w((v ; u)), kjer je w : C -> IR ueN(v,C) • p7(v,C) = število ciklov dolžine k po točkah iz C, ki gredo skozi točko v • pa(v,C) = de^V( ,C )\ če je deg(w) > 0; 0, sicer (težave z listi - deg(w) = 1) • enovita relativna gostota Pb(v,C) =-----deg^'9 , če je deg(w) > 0; 0, sicer maxueA,(„) deg(u) p'h(v,C) =---------eg^\ ^, če je deg(v,C) > 0; 0, sicer maxM€iV(l,)C)deg(«,C) • raznovrstnost pc(v,C) = m^ueNM deg(u) - mmueN{v,c) deg(u) p'c(v, C) = maxMeiV(,)C) deg(u, C) - mmueN{vfi) deg(u, C) • pd(v,C) = maxueN+{VtC) deg(u) - mmueN+{VtC) deg(u) p'd(v,C) = ma^jv+^o deg(u,C) - minu(,N+{vfi) deg(u,C) za primer, ko je Q = (V, S), K(X) naj bo poln graf na množici točk X pe{v,C) \f(K(N+( \L(C)C\L(K(N+(v)))\ \L(C)nL(K(N+(v,C)))\ \L(K(N+(v,C)))\ V definicijah funkcij pc in pd lahko funkcijo deg zamenjamo s poljubno funkcijo q: V -»• IR. Definicija 4.3: Podgraf H = (C, C\C), porojen z množico točk C C V je p-sredica na nivoju t G IR natanko tedaj, ko • VveC:t W G V : p(w, d) < p(w, C2) Točkovne funkcije px - p7 in pa - pe so vse monotone, funkcije p'a - p'e pa ne. Za monotono točkovno funkcijo p lahko dobimo p-sredico na nivoju t z zaporednim brisanjem točk, v katerih je vrednost funkcije p manjša od t, glej postopek 4.2. 68 4. Sredice Postopek 4.2 Določanje p-sredice na nivoju t Podatki: omrežje M = (V, C,p), predstavljeno s seznami sosedov in t G IR Rezultat: množica C C V, C je p-sredica na nivoju t C := V while 3v G C : p(v, C) < t do C := C \ {v} Trditev 4.1: Za monotono točkovno funkcijo p postopek 4.2 vrne p-sredico na nivoju t. Dokaz: Očitno je, da množica C, ki jo vrne postopek, zadošča prvi lastnosti iz definicije p-sredice. Pokazati moramo še, da je rezultat neodvisen od vrstnega reda točk, ki jih odstranjujemo. Predpostavimo nasprotno. Naj obstajata dve različni p-sredici na nivoju t. Označimo ju s C in V. Sredico C smo dobili z zaporednim odstranjevanjem točk u1} u2, u3, ..., Ur, sredico I? pa z zaporednim odstranjevanjem točk Vl, v2, v3, ¦ ¦ ¦, vq. Predpostavimo, da V \ C ^ 0. Pokazali bomo, da nas to pripelje do protislovja. Izberimo poljubno točko zeV\C. Pokazali bomo, da je tudi točko z potrebno odstraniti. Najprej odstranimo točke iz zaporedja vu v2, v3, ..., vq. Tako dobimo množico V. Ker je z G V \ C, se pojavi v zaporedju uu u2, u3, ..., us = z. Naj bo U0 = 0 in Ui = U^ U {m}. Ker je p(ui} V \ U^) < t za vsak i=l,...,r, velja zaradi monotonosti funkcije p tudi p{uh (V \ V) \ U^) < t za vsak i = 1,..., r. Torej lahko odstranimo tudi vse točke UieV\C, kar pomeni, da je V \ C = 0, to pa je protislovje, ki smo ga želeli pokazati. Ker je rezultat postopka enolično določen in ker je vrednost funkcije p na točkah izven C manjša od t, je izpolnjen tudi drugi pogoj iz definicije p-sredice. Dobljena množica C je torej p-sredica na nivoju t. ? Posledica 4.2: Za monotono točkovno funkcijo p so p-sredice gnezdene t1 Uu C Hu Dokaz: Dokaz sledi neposredno iz trditve 4.1. Ker je rezultat neodvisen od vrstnega reda brisanj, določimo najprej sredico Htl. Nato odstranimo še nekaj dodatnih točk in tako dobimo sredico Ht2. Torej je Ht2 CHtl. ? Podobno, kot v primeru navadnih sredic, lahko sklepamo, da je za monotono točkovno funkcijo p množica povezanih komponent posameznih slojev p-sredic hierarhija. Povezani komponenti, ki sta obe v istem sloju, sta ločeni, če pa sta v dveh različnih slojih, sta ločeni, ali pa je komponenta višjega sloja vsebovana v komponenti nižjega sloja. 4.5. POSPLOŠITEV SREDIC 69 1 p(v,C)= \N{v,C)\ueN{vfi) 0, J2 w((v;u)), N{v,C)±% sicer Pri tem je w: C -> IR+ funkcija, ki določa uteži na povezavah danega omrežja. Za testno omrežje izberimo omrežje M = (V, C, w) na množici točk V = {a, 6, c, d, e, /}, kjer so povezave in njihove uteži podane s tabelo: C (a;b) (b;c) (c;d) (b;e) (e;f) w 4 13 13 Če najprej odstranimo točko b, dobimo drugačen rezultat, kot če bi najprej odstranili točko c (ali točko e). Dobljeni rezultati so prikazani na sliki 4.5. Slika 4.5: Nemonotona točkovna funkcija Začetno omrežje je p-sredica na nivoju 2. Če želimo dobiti p-sredico na nivoju 3, imamo tri možnosti pri izbiri točke, ki jo bomo pobrisali kot prvo: b, c ali e. Če se odločimo za točko b, dobimo potem, ko odstranimo še izolirano točko a, p-sredico d = {c, d, e, /} na nivoju 3. Opazimo lahko, da je vrednost funkcije p v točkah c in e narasla z 2 na 3. 70 4. Sredice Postopek 4.3 Določanje p-sredice na nivoju t Podatki: omrežje M = (V, C,p), predstavljeno s seznami sosedov in t G IR Rezultat: množica C C V, C je p-sredica na nivoju t C := V for each t; G V do p H := p(v, N(v)) sestavi min-kopico heap iz točk V glede na funkcijo p while \heap\ > 0 A p[u := heap.top] < t do begin C := C \ {u} odstrani u iz kopice heap for each v G iV(u,C) do begin p[v] :=p(v,N(v,C)) popravi kopico heap (dvigni element t;) end end Če pričnemo z brisanjem točke c, dobimo množico {a,6,e,/} na nivoju 2. Pri tem se vrednost točke b poveča na 2.5. Nadaljujemo lahko z brisanjem točke b, kar nam da p-sredico C2 = {e, /} na nivoju 3, ali pa z brisanjem točke e, pri čemer dobimo p-sredico C3 = {a, b} na nivoju 4. Kot vidimo, je rezultat postopka odvisen od vrstnega reda brisanj. Tudi gnez-denosti sredic ni: p-sredica na nivoju 4 ni vsebovana v p-sredici na nivoju 3. 4.6 Postopki za določanje posplošenih sredic Definicija 4.5: Točkovna funcija p je lokalna natanko tedaj, ko p(v,C)=p(v,N(v,C)) Točkovne funkcije P1 - p6 so vse lokalne, funkcija p7 pa ni lokalna za k > 4. V nadaljevanju bomo predpostavili, da za točkovno funkcijo p obstaja konstanta p0, tako da je Vv G V : p(v, 0) = p0 Za lokalno monotono točkovno funkcijo p obstaja postopek za določitev p-sredice na nivoju t, čigar časovna zahtevnost je C(m-max{A,logn}), glej postopek 4.3. Pri tem smo predpostavili, da lahko vrednost p(v, N{v,C)) izračunamo v času 0(deg(v,C)). Stavek, kjer izračunamo novo vrednost p[v] lahko pogosto pospešimo, tako da to vrednost samo dopolnimo, ne da bi jo šli računati od začetka. Opisani postopek lahko preprosto popravimo tako, da nam vrne hierarhijo p-sredic, glej postopek 4.4. Hierarhija je določena s središčnimi števili, ki pripadajo posameznim točkam (nivo najvišje p-sredice, ki še vsebuje izbrano točko). 4.7. Primer 71 Postopek 4.4 Določanje hierarhije p-sredic Podatki: omrežje M = (V, C,p), predstavljeno s seznami sosedov Rezultat: tabela core s središčnimi števili posameznih točk C := V for each «eVdo p[v] := p(v, N(v)) sestavi min-kopico heap iz točk V glede na funkcijo p while \heap\ > 0 do begin u := heap.top C := C \ {u} odstrani m iz kopice heap core[m] := p[u] for each t; G iV(u,C) do begin := max{p[u],p(v,N(v,C))} popravi kopico /leap (dvigni element v) end end Predpostavimo, da je P največji čas, ki ga potrebujemo za izračun vrednosti ,C), kjer je v G V in C C V. Potem je časovna zahtevnost prvih treh korakov postopka 4.3 enaka 0(n) + O(Pn) + 0(n log n) = 0(n- max{P,logn}). Poglejmo si p(w,C), kjer je v G V in C C V. Potem je časovna zahtevnost prvih treh korakov postopk še telo zanke while. Ker se velikost množice C na vsakem koraku zanke zmanjša za 1, imamo največ n ponovitev zanke. Prva dva stavka v tej zanki lahko izvršimo v konstantnem času, torej je njun prispevek v postopku enak 0(n). V vseh ponovitvah zanke for znotraj zanke while obravnavamo vsako povezavo grafa največ enkrat. Torej se zanka for izvede največ m-krat, za kar potrebujemo m ¦ (P + O(logn)) časa. Če seštejemo vse skupaj, dobimo časovno zahtevnost celotnega postopka, ki je enaka O (m ¦ max{P, log n}). Za lokalno točkovno funkcijo p, katere vrednost p(v,N(v,C)) lahko izračunamo v času 0(deg(v,C)), je P = 0(A). V primerih, ko pa lahko vrednost funcije popravimo brez ponovnega izračunavanja, pa je P = 0(1). Za točkovne funkcije P1 - p4 postopek vrne isti rezultat kot postopek, opisan na začetku poglavja, a se bolj splača uporabljati prejšnjega, ker je hitrejši (linearen v številu povezav). 4.7 Primer Tudi delovanje tega postopka si poglejmo na omrežju avtorjev geombib [25]. Prej smo vrednosti na povezavah ignorirali, zdaj pa bomo te vrednosti uporabili pri določanju posplošenih sredic. Spomnimo se, da je p5 funkcija, ki točki predpiše vsote uteži na sosednih povezavah. Utež povezave pove, koliko skupnih člankov 72 4. Sredice MM.Bern r-~ MD.Dobkin ^-S.Suri M3.Chazelle r~\ ^-ti.uhazelle ^-R.Seidel ".Guibas m.Snoeyi MH.Edelsbrunner %.Sharir ^.Agarwal MJ.Halperin Mz.Welzl ^J.Matousek Mvl.Overmars ^/l.vanKreveld ^¦Yap ^/l.deBerg Mj.Schwarzkopf ^J.lcking ^?.Klein M.Tollis ^.Garg ^-J.Boissonnat -6.Devi Hers .Czyzowicz ^-P.Gupta HVI.Smid M^.Janardan ".Majhi MJ.Schwerdt Yvinec Slika 4.6: Računska geometrija: p5-sredica na nivoju 46 Peto poglavje Povezanost s kratkimi cikli Povezanost s kratkimi cikli je posploˇsitev obiˇcajne povezanosti. Namesto s potjo (zaporedje povezav) morata biti dve toˇcki povezani z zaporedjem kratkih ciklov, v ˇ katerem imata dva zaporedna cikla vsaj eno skupno toˇcko. Ce imajo vsi sosedni cikli v zaporedju vsaj eno skupno povezavo, govorimo o povezavni povezanosti s kratkimi cikli [10]. 5.1 Trikotniška povezanost 5.1.1 Neusmerjeni grafi Naj bo g = (V, S) enostaven neusmerjen graf. Točka m G V je v relaciji K s točko v G V, če je u = v ali obstaja pot v^odw do v. Relaciji K pravimo relacija povezanosti. Točka m G V je v relaciji B s točko v G V, če je u = v ali obstaja cikel v G, ki vsebuje u in v. Relaciji B pravimo relacija dvopovezanosti. Podgrafu, ki je izomorfen 3-ciklu C3, bomo rekli trikotnik. Podgraf H grafa G je tnkotniški, če vsaka njegova točka in vsaka njegova povezava pripada vsaj enemu trikotniku v H. Definicija 5.1: Zaporedje (TX)T2)... ,T8) trikotnikov v G (točkovno) trikotniško povezuje točko m G V s točko v G V, če je 1. ueVi^), 2. ve V(TS) in 3. V^jnV^)^ za i = 2,..., s. Takemu zaporedju pravimo (točkovna) trikotniška veriga, glej sliko 5.1. 73 74 5. Povezanost s kratkimi cikli Slika 5.1: Tnkotmška veriga Definicija 5.2: Točka m G V je (točkovno) tnkotmško povezana s točko v G V, nK3u, če je u = v ali obstaja (točkovna) trikotniška veriga, ki (točkovno) trikotniško povezuje točko u s točko v. Trditev 5.1: Relacija K3 je ekvivalenčna relacija na množici točk V. Ker bomo kasneje to in večino drugih trditev iz tega razdelka posplošili, jih tukaj navajamo brez dokazov. Ekvivalenčna relacija razbije množico točk v enega ali več ekvivalenčnih razredov, oziroma komponent. Komponenta je trivialna, če je sestavljena iz ene same točke. Trditev 5.2: Množice točk maksimalnih povezanih trikotniških podgrafov so natanko netrivialne komponente (točkovne) trikotniske povezanosti. Toda podgrafi, ki so porojeni z netrivialnimi komponentami (točkovne) trikotniske povezanosti niso nujno trikotniški podgrafi, torej tudi ne maksimalni povezani trikotniški podgrafi. To lahko vidimo na sliki 5.2, kjer vse točke grafa pripadajo isti komponenti trikotniske povezanosti, graf pa ni trikotniški zaradi povezave e, ki ne pripada nobenemu trikotniku. e Slika 5.2: Graf m trikotniški Postopek za določitev relacije K3 je preprost, glej postopek 5.1. Množico točk razbije na k skupin (ekvivalenčnih razredov), ki jih označimo s d, C2, ..., Ck. Najprej izberemo poljubno točko m G V in jo damo v novo množico, ki bo na koncu eden od ekvivalenčnih razredov. Potem po vrsti v množico dodajamo vse tiste točke, ki so iz točke u dosegljive po trikotnikih. Postopek ponavljamo tako dolgo, da so vse točke v svojih ekvivalenčnih razredih. Če so množice sosedov urejene, lahko uporabimo prilagojeno različico zlivanja in tako izračunamo N(u) D N(v) v času 0(A). V tem primeru je časovna zahtevnost postopka enaka O (Am), saj moramo pregledati vse točke, pri obdelavi točke u pa moramo obiskati vse njene sosede in za vsakega soseda v poiskati presek N(u)DN(v). 5.1. Trikotniška povezanost 75 Postopek 5.1 Ekvivalenčni razredi relacije K3 Podatki: graf Q = (V, S) Rezultat: komponente d, C2, ..., Ck relacije K3 fc:=0 while V ^ 0 do begin izberi u G V k := k + 1 Cfc := 0 C := {m} while C ^ 0 do begin izberi u E C Ck '¦= Ck U {m} for each t; G iV(u) do begin AT := N(u) n iV(w) if M ± 0 then L := C U AT U {v} end V := V \ {«} L:=L\{m} end end Definicija 5.3: Trikotniško omrežje M3{<3) = (V,S3,w3), ki ga določa graf Q = (V, S), je podgraf Q3 = (V, S3) grafa 0, katerega povezave so tiste povezave grafa Q, ki pripadajo kakemu trikotniku: e G L3, če e G L in e pripada trikotniku. Utež w3(e) povezave e G L3 je število različnih trikotnikov v grafu Q, na katerih leži povezava e. Trditev 5.3: K3(S) = K(03) Postopek za določitev S3 in w3 je preprost, glej postopek 5.2 in sliko 5.3. Če so množice sosedov urejene, je računanje uteži w3(e) časovne zahtevnosti 0(A), ker pa moramo utež naračunati za vsako povezavo posebej, je skupna časovna zahtevnost postopka enaka O (Am). N(u) Slika 5.3: w3(e) := \N(u)nN(v)\ 76 5. Povezanost s kratkimi cikli Postopek 5.2 Tnkotmško omrežje_______________ Podatki: graf Q = (V, S) Rezultat: trikotniško omrežje N3(G) = (V, S3,w3) L3 ¦= 0 for each e{u : v) G S do begin w3{e) := \N(u)nN(v)\ if w3(e) > 0 then S3 := S3 U {e} end Definicija 5.4: Zaporedje (Ti, T2,..., T,) trikotnikov v Q povezavno tnkotmško povezuje točko ueV s točko t; G V, če je 1. m G V(Ti), 2.«e V(T,) in 3. €{%-!) n 5(7;) ^ 0 za « = 2,..., s. Takemu zaporedju pravimo povezavna tnkotmška veriga, glej sliko 5.4. Slika 5.4: Povedna tnkotmška veriga Definicija 5.5: Točka m G V je povezavno trikotniško povezana s točko v G V, «L3w, če je m = t; ali obstaja povezavna trikotniška veriga, ki povezavno trikotniško povezuje točko u s točko v. Poglejmo si dvopovezan graf na sliki 5.5. Točki um v sta povezavno trikotniško povezani, medtem ko točki x in z nista. Relacija L3 ni tranzitivna: xL3v, vL3z, točka x pa ni v relaciji L3 s točko z. Slika 5.5: Dvopovezan tnkotmški graf Trditev 5.4: Relacija L3 določa ekvivalentno relacijo na množici povezav S. 5.1. Trikotniška povezanost 77 Postopek 5.3 Ekvivalenčni razredi relacije na L, določene z L3 Podatki: graf Q = (V, S) Rezultat: komponente d, C2, ..., Ck relacije na L fc:=0 while L ^ 0 do begin izberi e E L k:=k + l Ck ¦= 0 C := {e} while C ^ 0 do begin izberi e(u:v) E C Ck := Ck U {e} L := S \ {e} AT := iV(u) n N(v) C:=CU{(u:x),xeM}U{(v:x),xeM} C:=C\{e} end end Postopek za določitev relacije L3 je preprost, glej postopek 5.3. Množico povezav razbije na k skupin (ekvivalenčni razredi relacije na L), ki jih označimo s d, C2, ¦ ¦ ¦, Ck. Točka m je v relaciji L3 s točko v, če sta obe točki krajišči povezav iz iste skupine. uL3v ^^ 3i 3e, f E d : u E V(e) Av E V(f) Z V(e) smo označili množico krajišč povezave e. V vsaki ponovitvi notranje zanke iz množice L odstranimo eno povezavo in jo shranimo v množico Ck. Notranja zanka se torej izvrši natanko m-krat. Vse prireditvene stavke in primerjave lahko opravimo v konstantnem času, razen stavka, kjer določamo presek dveh množic sosednih točk. Če so množice sosedov urejene, ima ta stavek časovno zahtevnost C(A), ker pa se nahaja v notranji zanki, je časovna zahtevnost celotnega postopka enaka O {Am). Opozoriti velja, da v notranji zanki odstranimo povezavo e iz množice povezav L, torej tudi iz grafa. Zato so množice sosedov dinamične - odvisne so od trenutne množice povezav L. Od tod sledi, da potem ko odstranimo povezavo e iz množice L (in tudi iz L), se ta povezava ne more več pojaviti v C. Definicija 5.6: Naj bo B3 = B n K3. Trditev 5.5: V grafu Q velja: a. BCK d. B3 C B b. K3 C K e. B3 C K3 c. L3 C B3 78 5. Povezanost s kratkimi cikli Definicija 5.7: Naj bo t (v) število različnih trikotnikov grafa G, ki vsebujejo točko v. Trditev 5.6: 2t(v)= J2 ws(e) e:e(v.u) Dokaz: Vsak trikotnik, ki vsebuje točko v, vsebuje tudi natanko dve povezavi s krajiščem v tej točki. Ce torej za vsako povezavo s krajiščem v točki v preštejemo, koliko trikotnikom pripada, smo vsak trikotnik šteli dvakrat. ? Definicija 5.8: Stopnja nasičenosti v točki v je definirana kot v [40]: 2t(v) C {v) deg(w)(deg(w) - 1) Ker v enostavnem grafu velja t (v) < deg2W), je C (v) G [0,1]. Problem s tako definirano stopnjo nasičenosti je, da favorizira točke z majhno stopnjo. To lahko popravimo tako, da C {v) pomnožimo z ^^. y ' A(deg(w) - 1) Še vedno je 0 < C (v) < 1, a samo točke v največji kliki imajo vrednost 1. 5.1.2 Usmerjeni grafi Če ima graf Q kakšno neusmerjeno povezavo, jo nadomestimo z dvema nasprotno usmerjenima povezava. V nadaljevanju naj bo Q = (V, A) enostaven usmerjen graf. Nad izbrano povezavo a(u,v) G A obstajajo štirje različne vrste usmerjenih trikotnikov: ciklični (cyc), tranzitivni (tra), vhodni (in) in izhodni (out) trikotniki (glej sliko 5.6). Za vsako vrsto dobimo ustrezno trikotniško omrežje M^yc, A/]™, Nt in A/T*. cyc tra in out Slika 5.6: Vrste usmerjenih trikotnikov nad izbrano povezavo V usmerjenih omrežjih razlikujemo med šibko in krepko povezanostjo. Na šibko povezanost lahko gledamo kot na običajno povezanost v skeletu S = (V, Ss) grafa Q Ss = {(u:v):u^vA(u,v) G A} _ _____________________5.1. Trikotniška povezanost_____________________ 7g Definicija 5.9: Podgraf H grafa Q je ciklično tnkotmški, če vsaka njegova točka in vsaka njegova povezava pripada vsaj enemu cikličnemu trikotniku v H. Trditev 5.7: Šibko povezan ciklično tnkotmški graf je tudi krepko povezan. Podobno, kot v neusmerjenem primeru, lahko tudi v usmerjenem definiramo več vrst povezanostnih relacij. Če se omejimo na ciklične trikotnike, lahko definiramo (točkovno) ciklično trikotniško povezanost C3 in povezavno ciklično trikotniško povezanost D3. Definicija 5.10: Zaporedje (Ti, T2,..., %) cikličnih trikotnikov v Q (točkovno) ciklično trikotniško povezuje točko ueV s točko v G V, če je 1. ue V(Ti), 2. v G V(TS) in 3. V^jnV^)^ za i = 2,..., s. Takemu zaporedju pravimo (točkovna) ciklična trikotniška veriga. Definicija 5.11: Točka m G V je (točkovno) ciklično trikotniško povezana s točko v G V, uC3v, če je u = v ali obstaja (točkovna) ciklična trikotniška veriga, ki (točkovno) ciklično trikotniško povezuje točko u s točko v. Definicija 5.12: Zaporedje (TX,T2,...,%) cikličnih trikotnikov v Q povezavno ciklično trikotniško povezuje točko m G V s točko v G V, če je 1. ueV{%), 2. v G V(%) in 3. A(%_1) n A(%) ^0 za i = 2,..., s. Takemu zaporedju pravimo povezavna ciklična trikotniška veriga. Definicija 5.13: Točka m G V je povezavno ciklično trikotniško povezana s točko v G V, uD3v, če je u = v ali obstaja povezavna ciklična trikotniška veriga, ki povezavno ciklično trikotniško povezuje točko u s točko v. Za C3 in D3 veljajo podobne lastnosti, kot za K3 in L3. Trditev 5.8: Relacija C3 je ekvivalenčna relacija na množici točk V. Trditev 5.9: Relacija D3 določa ekvivalenčno relacijo na množici povezav A. Tudi postopki za določitev relacij in pripadajočih omrežij so podobni, kot v neusmerjenem primeru, torej imajo tudi enako časovno zahtevnost. Na primer, v cikličnem trikotniškem omrežju M^yc = (V,Afc,Wzyc) za vsako povezavo a G AT velja: wT(a(u,v)) = \Nout(v) n Nm(u)\ 80 5. Povezanost s kratkimi cikli ciklično neciklično Slika 5.7: Krepko tnkotniško povezana grafa Naj bo R relacija dosegljivosti v danem usmerjenem grafu g. Točka v G V je dosegljiva iz točke ueV, uRv, če je u = v ali pa obstaja sprehod od u do v. Naj bo S relacija krepke povezanosti v danem usmerjenem grafu g. Točki m G V in v G V sta v relaciji S, če je u = v ali obstajata sprehoda od u do v in od v do m. OčitnojeS = RnR"1. Trditev 5.10: V usmerjenem grafu Q velja: a. D3 C C3 b. C3 C S3 c. S3 C S Trditev 5.11: c3{G) = s{gcyc) 5.1.3 Tranzitivnost Povezava je tnkotniško tranzitivna, če je osnova nekega tranzitivnega trikotnika. Tranzitivne povezave so pravzaprav bližnjice - če nekatere od njih zbrišemo, lahko podatki še vedno potujejo po podpornih povezavah. Uporabimo jih lahko tudi za preverjanje pravilnosti prenosa. Trditev 5.12: Če iz grafa Q = (V, A) zbrišemo nekaj (ali vse) povezave, ki pripadajo tnkotniško tranzitivm poti vr (vsaka povezava na poti vr je tnkotniško tranzitivna), se relacija dosegljivosti ne spremeni: R(0) = R(g\A{n)). Dokaz: Ker je graf g \ A(n) podgraf grafa g, je očitno R(0 \ A(ir)) C R(0). Naj bo povezava a poljubna povezava na trikotniško tranzitivni poti vr. Ker je trikotniško tranzitivna, lahko od enega do drugega krajišča pridemo tudi po dveh podpornih povezavah, torej lahko povezavo a odstranimo, ne da bi s tem prekinili katerega 5.2. fc-KOTNIŠKA POVEZANOST 81 Slika 5.8: Vseh trikotniˇsko tranzitivnih povezav ne moremo odstraniti 5.2 L>kotniška povezanost Ker je pojem fc-ciklična povezanost že uporabljen v teoriji grafov, bomo nadaljevali z ‘geometrijsko’ terminologijo (trikotnik, fc-kotnik). 5.2.1 Neusmerjeni grafi Naj bo g = (V, S) enostaven neusmerjen graf. Podgrafu, ki je izomorfen fc-ciklu Ck, bomo rekli k-kotmk, podgrafu, ki je izomor-fen enemu od s-ciklov C8, 3 < s < k pa (k)-kotmk. Podgraf H grafa Q je k-kotniški, če vsaka njegova točka in vsaka njegova povezava pripada vsaj enemu (fc)-kotniku v . 82 ________________5. Povezanost s kratkimi cikli________________ Definicija 5.15: Zaporedje (d, d,..., Cs) (fc)-kotnikov v Q (točkovno) k-kotniško povezuje točko ueV s točko v G V, če je 1. u G V(d), 2. ve V {C a) in 3. V(Ci_1) n V(d) ± 0 za z = 2,..., s. Takemu zaporedju pravimo (točkovna) k-kotmška veriga, glej sliko 5.9. Slika 5.9: k-kotmška veriga Definicija 5.16: Točka m G V je (točkovno) k-kotniško povezana s točko v G V, «Kfcw, če je u = v ali obstaja (točkovna) fc-kotniška veriga, ki (točkovno) fc-kotniško povezuje točko u s točko v. Trditev 5.13: Relacija Kk je ekvivalenčna relacija na množici točk V. Dokaz: Refleksivnost sledi iz definicije relacije Kk. Če fc-kotniško verigo od u do v obrnemo, dobimo fc-kotniško verigo odWow, torej je relacija Kk simetrična. Še tranzitivnost. Naj bodo u, v in z takšne točke, daje uKkv in vKkz. Če točke niso paroma različne, je pogoj za tranzitivnost trivialno izpolnjen. Predpostavimo torej, da so točke u, v in z paroma različne. Ker je uKkv, obstaja fc-kotniška veriga od u do v, ker pa je vKkz, obstaja tudi fc-kotniška veriga od v do z. Če ti dve verigi staknemo, dobimo fc-kotniško verigo od u do z, torej je vKkz. ? Trditev 5.14: Množice točk maksimalnih povezanih k-kotniških podgrafov so natanko netrivialne komponente (točkovne) k-kotniske povezanosti. Dokaz: Naj bosta u\xvv poljubni točki, ki pripadata povezanemu fc-kotniškemu podgrafu. Če sta točki enaki, je očitno uKkv. Sicer pa obstaja pot iv = u,e1,z1,e2, z2,e3,z3,..., es, v od u do v. Ker je podgraf fc-kotniški, vsaka povezava e* na tej poti pripada vsaj enemu (fc)-kotniku d v tem podgrafu. Za dobljeno fc-kotniško verigo (d,C2,...,C8) velja: • d G L(Ci) za i=l,...,s • u G V(d), v G V {C 8) e V(Ci_1) n V(L) za i = 2,..., s 5.2. fc-KOTNIŠKA POVEZANOST 83 k wk(e) > J2(r - 2)(r - 3) • • • (r - i + 1) i=3 84 5. Povezanost s kratkimi cikli 1. u g V(Ci), 2. ve V {C s) in 3. L(Ci_i) n L(L) ^ 0 za « = 2,..., s. Takemu zaporedju pravimo povedna k-kotniška veriga, glej sliko 5.10. Slika 5.10: Povezavna k-kotniška veriga Definicija 5.19: Točka m G V je povezavno k-kotmško povezana s točko v G V, «Lfcw, če je u = v ali obstaja povezavna fc-kotniška veriga, ki povezavno fc-kotniško povezuje točko u s točko v. Trditev 5.16: Relacija Lk določa ekvivalenčno relacijo na množici povezav S. Dokaz: Naj bo ~ relacija na S, ki je definirana takole: e ~ /, če je e = / ali pa obstaja povezavna fc-kotniška veriga (CUC2, ¦ ¦ .,C8), kjer je e G S (d) in / G L{CS). Refleksivnost relacije ~ sledi iz njene definicije. Tudi simetričnost je preprosta. Naj bo e ~ /. Potem obstaja povezavna k-kotniška veriga ‘od’ e ‘do’ /. Če jo obrnemo, dobimo povezavno fc-kotniško verigo ‘od’ / ‘do’ e, torej je / ~ e. Še tranzitivnost. Naj bodo e, / in g takšne povezave, da je e ~ / in / ~ g. Potem obstajata povezavni fc-kotniški verigi ‘od’ e ‘do’ / in ‘od’ / ‘do' g. Če ti dve verigi staknemo, dobimo povezavno fc-kotniško verigo ‘od’ e ‘do’ g (oba (fc)-kotnika na stiku verig vsebujeta povezavo /, torej njun presek ni prazen). Zato je tudi e ~ g. __________________________5.2. k-KOTNIŠKA POVEZANOST__________________________ 85 Definicija 5.20: Naj bo Bk = B n Kk. Trditev 5.17: V grafu Q velja: a. B C K d. BkCB b. Kk C K e. Bk C Kk c. Lk C Bk zai 88 ________________5. Povezanost s kratkimi cikli________________ Za Cfc in Dfc veljajo podobne lastnosti, kot za Kk in Lk. Trditev 5.19: Relacija Ck je ekvivalenčna relacija na množici točk V. Dokaz: Refleksivnost sledi iz definicije relacije Ck. Če ciklično fc-kotniško verigo od ti do t; obrnemo, dobimo ciklično fc-kotniško verigo od v do u, torej je relacija Ck simetrična. Še tranzitivnost. Naj bodo u, v in z takšne točke, da je uCkv in vCkz. Če točke niso paroma različne, je pogoj za tranzitivnost trivialno izpolnjen. Predpostavimo torej, da so točke u, v in z paroma različne. Ker je uCkv, obstaja ciklična fc-kotniška veriga od u do v, ker pa je vCkz, obstaja tudi ciklična fc-kotniška veriga od v do z. Če ti dve verigi staknemo, dobimo ciklično fc-kotniško verigo od u do z, torej je uCkz. ? Trditev 5.20: Relacija Dfc določa ekvivalenčno relacijo na množici povezav A. Dokaz: Naj bo ~ relacija na A, ki je definirana takole: e ~ /, če je e = / ali pa obstaja povezavna ciklična fc-kotniška veriga (C1}C2, ...,C8), kjer je e E .4(d) in / e A(CS). Refleksivnost relacije ~ sledi iz njene definicije. Tudi simetričnost je preprosta. Naj bo e ~ /. Potem obstaja povezavna ciklična fc-kotniška veriga ‘od’ e ‘do’ /. Če jo obrnemo, dobimo povezavno ciklično fc-kotniško verigo ‘od’ / ‘do’ e, torej je / ~ e. Še tranzitivnost. Naj bodo e, / in g takšne povezave, da je e ~ / in / ~ g. Potem obstajata povezavni ciklični fc-kotniški verigi ‘od’ e ‘do’ / in 'od’ / ‘do' g. Če ti dve verigi staknemo, dobimo povezavno ciklično fc-kotniško verigo ‘od’ e ‘do’ g (oba (fc)-cikla na stiku verig vsebujeta povezavo /, torej njun presek ni prazen). Zato je tudi e ~ g. ? Definicija 5.26: Povezava je ciklična, če pripada vsaj enemu usmerjenemu ciklu v grafu G. Dolžina cikla pri tem ni pomembna. Ciklični povezavi, ki ne pripada nobenemu (fc)-ciklu, rečemo k-dolga povezava. Trditev 5.21: Če graf Q = (V, A) ne vsebuje nobene k-dolge povezave, potem je njegova ciklična k-kotniška redukcija Q/Ck = (V/Ck,A*), kjer za X,Y e V/Ck velja (X,Y) E A* ^^ 3u E X 3v E Y : (u,v) E A, acikličen graf. Dokaz: Predpostavimo, da ciklična fc-kotniška redukcija grafa Q ni aciklična. Potem vsebuje cikel C*, ki ga lahko razširimo do cikla C v grafu Q. Naj bo a* poljubna povezava cikla C* in naj bo a ustrezna povezava cikla C. Ker sta krajišči povezave a* dve različni točki, krajišči povezave a pripadata dvema različnima komponentama relacije Ck. Povezava a torej ne pripada nobenemu cikličnemu (fc)-kotniku. Ker pa a pripada ciklu C, je to ciklična povezava, torej je fc-dolga. To pa je protislovje s predpostavko, da graf ne vsebuje fc-dolgih povezav. Torej mora biti ciklična fc-kotniška redukcija grafa Q acikličen graf. ? _______________________5.2. fc-KOTNIŠKA POVEZANOST_______________________ 89 Iz tega dokaza vidimo, kako v grafu poiskati fc-dolge povezave. To so natanko tiste povezave, ki ustrezajo cikličnim povezavam v Q/Ck. Definicija 5.27: Točka m G V je krepko k-kotniˇsko povezana s točko v G V, uSkv, čejeu = v ali obstaja krepko povezan fc-kotniški podgraf, ki vsebuje točki u in v. Trditev 5.22: V usmerjenem grafu Q velja: a. Dk C Ck b. Ck C Sk c. Sk C S zai