Problem bojanja grafa i njegove primjene u telekomunikacijama

master's thesis

• Author: Anamarija Fofonjka
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Maja Starčević (član povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-09-25, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: optimizacije mobilne mreže; matematičko modeliranje problema; problema bojanja grafova
• Keywords (english): mobile network optimization; mathematical model of the problem; graph coloring problem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:041586
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Access restricted to students and staff of home institution
• Created on: 2019-01-22 10:26:24