| OPOMBE | Bibliografija: str. 99-102 // Povzetek ; Abstract // Univ. Ljubljana, Fak. za matematiko in fiziko, Oddelek za matematiko // Precej znanih postopkov za analizo omrežij je prepočasnih, dabi 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 (podkvadratič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 maksimalenpodgraf, v katerem ima vsaka točka vsaj ▫$k$▫ sosedov. Sredice določajo gnezdeno razslojitev 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 relacijepovezanosti točk (točkovno in povezavno povezanost s kratkimi cikli v neusmerjanih 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. // Severalwell known algorithms for network analysis are too slow to be used on largenetworks. Therefore we often decompose the network to smaller parts that are easier to handle. In doctoral disswrtation we study efficient (subquadratic) algorithms for large networks decompositions. The preamble contains some basic definitions and notations used in continuation. 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 the fifth chapter contain original contributions of the dissertation. In the third chapter the vertexand edge islands of networks are defined. Vertex islands is connected set of vertices having values greater then 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 forms 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 functions instead of degree. It is shown that there exist 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 connectivityrelations on the set of vertices (vertex and edge short cycles connectivityin undirect and direct graphs). We notice, that some of them are equivalence relations on the set of vertices, while the other determine equivalence relations on the set of lines, which give us another decomposition of a given graph.Način dostopa (URN): http://www.dlib.si/?urn=URN:NBN:SI:doc-RBIA5C56 |