Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Posplošena barvanja in heksagonalni grafi : doktorska disertacija
    Šparl, Petra, 1975-2016
    Disertacija obravnava probleme v zvezi s posplošenimi barvanji grafov. Pri tem se v večini primerov omejimo na utežene inducirane podgrafe neskončne trikotniške mreže ali heksagonalne grafe, ki ... izhajajo iz praktičnega problema dodeljevanja frekvenc v celičnih omrežjih. Največkrat gre za probleme, ki spadajo v razred NP, zato bomo iskali ▫$k$▫-optimalne algoritme in zgornje meje za rešitve optimizacijskih nalog. V uvodnem poglavju disertacije podamo pregled posplošenih barvanj grafov, ki jih pričujoce delo obravnava. Predstavimo praktičen problem dodeljevanja frekvenc, ki je običajno opisan s pomočjo teorije grafov in ga v večini primerov lahko prevedemo na problem večbarvanja grafov. Definiramo heksagonalne grafe, ki se v literaturi pogosto pojavljajo kot model za celična omrežja. Naštejemo glavne znane rezultate ter odprta vprašanja in domneve v zvezi s posplošenimi barvanji uteženih heksagonalnih grafov. V drugem poglavju podamo osnovne pojme in definicije, ki jih potrebujemo v nadaljevanju disertacije. V tretjem razdelku drugega poglavja spregovorimo o algoritmih. Med drugim opišemo zahtevnost računskih problemov in aproksimacijske algoritme. V zadnjem razdelku podrobneje predstavimo problem dodeljevanja frekvenc in uporabo teorije grafov za matematični model omenjenega problema. V tretjem poglavju definiramo večbarvanje grafov in uteženo kromatično število. V prvem razdelku obravnavamo večbarvanje heksagonalnih grafov. Na začetku razdelka predstavimo dosedanje rezultate, v nadaljevanju pa podamo 4/3-aproksimacijski algoritem za večbarvanje heksagonalnih grafov in dokaz pravilnosti le-tega. V drugem razdelku govorimo o posebnem primeru, ko heksagonalni grafi ne smejo vsebovati trikotnikov. Predstavimo dosedanje rezultate in 5/4-aproksimacijski algoritem za večbarvanje heksagonalnih grafov brez trikotnikov. V tretjem razdelku opišemo večbarvanje heksagonalnih grafov z omejitvami. V četrtem poglavju želimo algoritme iz tretjega poglavja realizirati kot ▫$k$▫-lokalne porazdeljene algoritme za večbarvanje heksagonalnih grafov. V prvem razdelku dokažemo, da obstaja 2-lokalen 4f 3-aproksimacijski porazdeljen algoritem za večbarvanje heksagonalnih grafov. V drugem razdelku se ponovno omejimo na heksagonalne grafe brez trikotnikov. Na začetku razdelka podamo 2-lokalen algoritem za 5-[2]barvanje heksagonalnih grafov brez trikotnikov. V nadaljevanju razdelka dokažemo, da lahko omenjeni algoritem posplošimo in podamo 2-lokalni 5/4-aproksimacijski algoritem za večbarvanje heksagonalnih grafov brez trikotnikov. Peto poglavje je namenjeno homomorfizmom grafov. V uvodu poglavja podamo definicijo ▫$H$▫-pobarvljivosti in predstavimo nekaj splošnih rezultatov. V prvem razdelku nas zanima obstoj homomorfizmov heksagonalnih grafov v lihe cikle. Pokažemo, da obstaja homomorfizem iz poljubnega heksagonalnega grafa brez trikotnikov v cikel ▫$C_5$▫. Podamo primer heksagonalnega grafa brez trikotnikov, za katerega ne obstaja homomorfizem v cikel ▫$C_9$▫. Vprašanje za cikel ▫$C_7$▫ ostaja odprto. Na koncu poglavja na kratko spregovorimo o povezavi med homomorfizmi in ▫$n-[k]$▫barvanji grafov. V šestem poglavju obravnavamo dve posplošitvi barvanja grafov, krožno barvanje in deljeno barvanje. Prvi razdelek je namenjen krožnemu barvanju. Podamo definicijo krožnega barvanja in krožnega kromatičnega števila ter nekatere znane rezultate v zvezi s krožnim kromatičnim številom. V drugem razdelku definiramo deljeno barvanje in deljeno kromatično število ter podamo nekaj lastnosti o slednjem. V tretjem razdelku spregovorimo o zvezi med krožnim in deljenim kromatičnim številom. V četrtem razdelku predstavimo povezavo med homomorfizmi ter krožnim in deljenim barvanjem. Pokažemo, da je za poljuben končen graf ▫$G$▫ obstoj homomorfizma v cikel ▫$C_{2k+1}$▫ ekvivalenten neenakosti ▫$\chi_c(G) \le 2 + 1/k$▫. V zadnjem razdelku podamo zgornje meje za krožno in deljeno kromatično število heksagonalnih grafov. Na koncu je podanih nekaj odprtih problemov iz področja, ki ga disertacija obravnava.
    Vrsta gradiva - disertacija ; neleposlovje za odrasle
    Založništvo in izdelava - Maribor : [P. Šparl], 2005
    Jezik - slovenski
    COBISS.SI-ID - 220511232

Knjižnica/institucija Kraj Akronim Za izposojo Druga zaloga
FMF in IMFM, Matematična knjižnica, Ljubljana Ljubljana MAKLJ v čitalnico 1 izv.
Miklošičeva knjižnica - FPNM, Maribor Maribor PEFMB v čitalnico 1 izv.
Narodna in univerzitetna knjižnica, Ljubljana Ljubljana NUK v čitalnico 1 izv.
Univerzitetna knjižnica Maribor Maribor UKM v čitalnico 1 izv.
loading ...
loading ...
loading ...

Vnos na polico