-
Uporaba teorije grafov za naloge dodeljevanja frekvenc : magistrsko deloŠparl, Petra, 1975-2016Cilj magistrskega dela je pregled rezultatov pri nalogah dodeljevanja frekvenc na heksagonalnih grafih. V prvem poglavju je opisana ena glavnih nalog v omrežjih mobilne telekomunikacije in sicer ... dodeljevanje frekvenc oddajnikom, znotraj omejenega frekvenčnega spektra, pri danih interferenčnih omejitvah. Naloga je z leti postajala vedno pomembnejša in vedno težja, saj se je mobilna telekomunikacija v zadnjem času zelo hitro razvijala. Omejeno množico frekvenc je namreč potrebno dodeliti velikemu številu mobilnih uporabnikov, pri čemer poljubni dve dodeljeni frekvenci ne smeta povzročati nedovoljene interference. V praksi se veliko uporablja celični koncept, kjer velika področja razdelimo na manjša, imenovana celice. S tem se poveča izraba frekvenčnega spektra, saj lahko različnim celicam dodelimo enake množice frekvenc, če so le te dovolj medsebojno oddaljene. V drugem poglavju je predstavljena uporaba teorije grafov za naloge dodeljevanja frekvenc. Celične mreže so ponavadi predstavljene kot uteženi heksagonalni grafi, kjer točke predstavljajo območja oziroma celice, povezave predstavljajo možnosti interference med frekvencami, vektor uteži pa zahteve posamezne celice oziroma število klicev, ki morajo biti oskrbljeni v celici, ki jo dana točka predstavlja. Naloga dodeljevanja frekvenc v jeziku teorije grafov je ustrezno pobarvati utežen heksagonalen graf, pri čemer je potrebno upoštevati interferenčne omejitve, ki povedo katerim točkam grafa ne smemo dodeliti enakih barv. Interferenčne omejitve predstavimo z zaporedjem naravnih števil ▫$c_0\geq c_1\geq c_2\geq c_3...,$▫ kjer ▫$c_1$▫ pomeni minimalno razliko med frekvencama dodeljenima klicema iz celic, ki sta na radalji i v mreži. Če barve, ki jih imamo na razpolago za omenjeno večbarvanje označimo z zaporednimi naravnimi števili, potem omejitev ▫$c_i$▫ pomeni, da se morajo barve dodeljene točkama na razdalji i razlikovati najmanj za ▫$c_i$▫. Na začetku tretjega poglavja je podan optimalen algoritem za večbarvanje ciklov. V nadaljevanju so podrobno analizirani in primerjani trije konstruktivni dokazi zgornjih mej za uteženo kromatično število heksagonalnih grafov v odvisnosti od uteženega kličnega števila [26, 18, 20]. Izkazalo se je, da prva dva dokaza podajata enaki zgornji meji za kromatično število poljubnega heksagonalnega grafa G in sicer ▫$X_w(G)\le [\frac{4\omega_w(G)+1}{3}]$▫.Prvi dokaz ima eno pomembno lastnost, ki je drugi dokaz nima. Algoritem dobljen na osnovi prvega dokaza je namreč porazdeljen, medtem ko algoritem, ki ga dobimo s pomočjo drugega dokaza, ni. Porazdeljena izvedba prvega algoritma je podana na koncu tretjega poglavja. Za tretji dokaz se je izkazalo, da ima napako, kar je pokazano v razdelku 3.2.2, kjer je podan tudi ustrezen protiprimer. V četrtem poglavju je obravnavano večbarvanje heksagonalnih grafov brez trikotnikov. Najprej je predstavljen algoritem za 5-[2]-barvanje heksagonalnih grafov brez trikotnikov, s pomočjo katerega je v nadaljevanju podan dokaz zgornje meje za uteženo kromatično število heksagonalnih grafov brez trikotnikov v odvisnosti od uteženega kličnega števila [10]: ▫$X_w(G)\le [\frac{5\omega_w(G)}{4}]+3$▫. V drugem delu četrtega poglavja je predstavljen algoritem za 7-[3]-barvanje heksagonalnih grafov brez trikotnikov. Omenjeni algoritem je imel v originalu [8] napako, ki je v delu popravljena. V petem poglavju so obravnavana večbarvanja heksagonalnih grafov z omejitvami. Na začetku je predstavljeno večbarvanje z omejitvami ▫$c_o\g 1$▫, ▫$c_1=1$▫ in ▫$c_i=0$▫ za ▫$ i\geq 2 [27]$▫ v nadaljevanju pa večbarvanje z omejitvami ▫$c_o=c_1=c_2$▫ in ▫$c_i=0$▫, za ▫$i\geq 3[4]$▫. V obeh primerih so podani dokazi za zgornje meje kromatičnega števila v odvisnosti od kličnega števila. V šestem in sedmem poglavju so opisani sorodni rezultati oziroma odprti problemi iz področja dodeljevanja frekvencVrsta gradiva - magistrsko delo ; neleposlovje za odrasleZaložništvo in izdelava - Maribor : [P. Šparl], 2001Jezik - slovenskiCOBISS.SI-ID - 10787336
Avtor
Šparl, Petra, 1975-2016
Drugi avtorji
Žerovnik, Janez, 1958-
Teme
matematika |
teorija grafov |
klika |
klinično število |
heksagonalen graf |
barvanje točk grafa |
kromatično število |
magistrske naloge |
mathematics |
graph theory |
clique |
clique number |
hexagonal graph |
vertex voloring of graph |
chromatic number |
weighted graph |
algorithm
Signatura – lokacija, inventarna št. ... |
Status izvoda | Rezervacija |
---|---|---|
Skladišče II 0000051380 Skladišče II 51380 |
prosto - za čitalnico
|
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.