prikaz prve stranice dokumenta Problem bojanja grafa i njegove primjene u telekomunikacijama
Access restricted to students and staff of home institution
master's thesis
Problem bojanja grafa i njegove primjene u telekomunikacijama
Zagreb: University of Zagreb, Faculty of Science, 2014. urn:nbn:hr:217:041586
Fofonjka, Anamarija
University of Zagreb
Faculty of Science
Department of Mathematics

Cite this document

Fofonjka, A. (2014). Problem bojanja grafa i njegove primjene u telekomunikacijama (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:041586

Fofonjka, Anamarija. "Problem bojanja grafa i njegove primjene u telekomunikacijama." Master's thesis, University of Zagreb, Faculty of Science, 2014. https://urn.nsk.hr/urn:nbn:hr:217:041586

Fofonjka, Anamarija. "Problem bojanja grafa i njegove primjene u telekomunikacijama." Master's thesis, University of Zagreb, Faculty of Science, 2014. https://urn.nsk.hr/urn:nbn:hr:217:041586

Fofonjka, A. (2014). 'Problem bojanja grafa i njegove primjene u telekomunikacijama', Master's thesis, University of Zagreb, Faculty of Science, accessed 24 April 2024, https://urn.nsk.hr/urn:nbn:hr:217:041586

Fofonjka A. Problem bojanja grafa i njegove primjene u telekomunikacijama [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2014 [cited 2024 April 24] Available at: https://urn.nsk.hr/urn:nbn:hr:217:041586

A. Fofonjka, "Problem bojanja grafa i njegove primjene u telekomunikacijama", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2014. Available at: https://urn.nsk.hr/urn:nbn:hr:217:041586

Please login to the repository to save this object to your list.
Metadata
TitleProblem bojanja grafa i njegove primjene u telekomunikacijama
AuthorAnamarija Fofonjka
MentorRobert Manger (mentor)
Committee memberRobert Manger (predsjednik povjerenstva)
Committee memberNela Bosner (član povjerenstva)
Committee memberMaja Starčević (član povjerenstva)
Committee memberZvonimir Bujanović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2014-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:041586
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
RepositoryRepository of the Faculty of Science
Created on2019-01-22 10:26:24

(©) Nacionalna i sveučilišna knjižnica u Zagrebu 2015. Sva prava pridržana. | Hrvatske bratske zajednice 4 p.p. 550, 10000 Zagreb, Hrvatska Tel. ++ 385 1 616-4040
OIB: 84838770814 | IBAN: HR66 2340 0091 1000 1008 1, Porezni broj (PDV identifikacijski broj) - VAT Number: HR84838770814
Prijava u repozitorij