Problem bojanja grafa i njegove primjene u telekomunikacijama

diplomski rad

• Autor: Anamarija Fofonjka
• Mentor: Robert Manger (mentor)
• Član povjerenstva: Robert Manger (predsjednik povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Član povjerenstva: Maja Starčević (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2014-09-25, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Današnji ubrzani način života prisiljava ljude na korištenje tehnologije. Mnogim ljudima je život nezamisliv bez mobilnog uređaja. Mobilna mreža je izrazito složena struktura i potrebno ju je dobro konfigurirati budući da je broj ljudi koji koriste njene usluge svakim danom sve veći. Ovaj diplomski rad bavi se problemom optimizacije mobilne mreže Japana. Rad započinje definiranjem osnovnih pojmova i matematičkim modeliranjem problema. Matematičkom formulacijom problema zaključujemo da njegovo rješavanje zahtjeva pronalaženje optimalnog rješenja problema bojanja grafova uz dodatne uvjete i ograničenja. Pripadni problem optimizacije spada u klasu NP-teških problema, što otprilike znači da je vrlo zahtjevan za rješavanje. Nakon što je problem jasno definiran, izlažemo nekoliko algoritama za njegovo rješavanje. Pokazujemo da imunološki algoritam, inspiriran radom našeg imunološkog sustava, nije dobar za rješavanje ovog problema. Puno bolje rezultate daje algoritam koji nalazi jako dobro početno bojanje i zatim lokalnim pretragama nastoji doći do boljeg rješenja. Algoritam prilagodbe daje jednako dobre rezultate, ali je nekoliko puta sporiji. Za sve algoritme određeni su optimalni parametri te su provedena testiranja bojanjem šest grafova koji predstavljaju dio mobilne mreže Japana. Na samom kraju rada dane su smjernice za moguća poboljšanja.

Sažetak (engleski)

Today’s fast lifestyle is forcing people to use technology. For many people, life is unimaginable without a mobile device. Mobile network is a very complex structure and needs to be well-configured as the number of people who use its services is increasing daily. This paper deals with the problem of mobile network optimization. At the beginning, we list the basic terms in order to define mathematical model of the problem. We conclude that problem resolution demands finding the optimal solution to the graph coloring problem with additional conditions and restrictions. The corresponding optimization problem belongs to the class of NP-hard problems, which roughly means that it is very challenging to resolve. Once the problem is clearly defined, we present several algorithms for solving it. The algorithm inspired by the work of our immune system is not suitable and it gives the worst results. Much better results are obtained using very good initial coloring and local search for solution improvement. The adaptation algorithm gives equally good results, but it is several times slower. After that, we determine optimal parameters for all algorithms and test them by coloring six graphs that represent part of Japanese mobile network. At the end of the paper we list possible improvements and conclusions.

• Ključne riječi: optimizacije mobilne mreže; matematičko modeliranje problema; problema bojanja grafova
• Ključne riječi (engleski): mobile network optimization; mathematical model of the problem; graph coloring problem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:041586
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Pristup korisnicima matične ustanove
• Datum i vrijeme pohrane: 2019-01-22 10:26:24