-
Posplošena barvanja in heksagonalni grafi : doktorska disertacijaŠparl, Petra, 1975-2016Disertacija 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 odrasleZaložništvo in izdelava - Maribor : [P. Šparl], 2005Jezik - slovenskiCOBISS.SI-ID - 220511232
Avtor
Šparl, Petra, 1975-2016
Drugi avtorji
Žerovnik, Janez, 1958-
Teme
Grafi |
Disertacije |
barvanje grafov |
uteženi grafi |
heksagonalni grafi |
krožno barvanje |
krožno kromatično število |
deljeno barvanje |
deljeno kromatično število |
dobro večbarvanje točk grafa |
uteženo klično število |
uteženo kromatično število |
porazdeljen algoritem |
▫$k$▫-aproksimacijski algoritem |
▫$k$▫-lokalen algoritem |
homomorfizem grafov |
▫$H$▫-pobarljivost |
graph colouring |
weighted graphs |
hexagonal graphs |
circular colouring |
circular chromatic number |
fractional colouring |
fractional chromatic number |
proper multicolouring of graph vertices |
weighted clique number |
weighted chromatic number |
distributed algorithm |
▫$k$▫-competitive algorithm |
▫$k$▫-lokal algorithm |
graph homomorphism |
▫$H$▫-colorability
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.
|
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Šparl, Petra, 1975-2016 | 20495 |
Žerovnik, Janez, 1958- | 03430 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.