DIKUL - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Razčlembe omrežij : doktorska disertacija
    Zaveršnik, Matjaž
    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 (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 maksimalen podgraf, 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 relacije povezanosti 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.
    Type of material - dissertation ; adult, serious
    Publication and manufacture - Ljubljana : [M. Zaveršnik], 2003
    Language - slovenian
    COBISS.SI-ID - 12894297

Library/institution City Acronym For loan Other holdings
Central Technological Library of the University of Ljubljana Ljubljana CTK outside loan 1 cop.
FMF and IMFM, Mathematical Library, Ljubljana Ljubljana MAKLJ reading room 1 cop.
National and University Library, Ljubljana Ljubljana NUK reading room 1 cop.
University of Maribor Library Maribor UKM reading room 1 cop.
University of Primorska University Library Koper - Capodistria UPUK reading room 1 cop.
loading ...
loading ...
loading ...