Primjene teorije grafova

master's thesis

• Title (english): Applications of graph theory
• Author: Barbara Prkačin
• Mentor: Slaven Kožić (mentor)
• Committee member: Slaven Kožić (predsjednik povjerenstva)
• Committee member: Luka Grubišić (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Siniša Slijepčević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-09-21, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu obrađene su tri primjene teorije grafova. Nakon pregleda osnovnih koncepata teorije grafova slijedi kratka analiza problema najkraćeg puta i primjer rješenja Dijkstrinim algoritmom te se navode neke primjene. U nastavku je detaljnije obrađen problem bojanja grafova kojem je cilj minimizirati broj boja potrebnih da susjedni vrhovi grafa budu obojani različitim bojama. Dan je pregled tri primjene bojanja grafova s naglaskom na primjeru iz telekomunikacija. Posljednje i najopširnije poglavlje obrađuje mjere centralnosti čija je svrha odrediti važnost nekog vrha u grafu. Opisuje se nekoliko različitih primjena mjera centralnosti, uključujući analizu mreže citata akademskih članaka koji obrađuju temu pandemije bolesti COVID-19.

Abstract (english)

This thesis is a study of three topics on the application of graph theory. After a review of the central concepts of graph theory, we first give a brief analysis of the shortest path problem and an example of its solution via Dijkstra’s algorithm, together with some applications of this approach. We then proceed to give a more detailed analysis of the problem of graph colouring, which aims to minimise the number of colours needed to ensure that adjacent graph vertices are always coloured differently. Here we review three applications of graph colouring, focusing on an application in telecommunications. The main and final chapter is a discussion of graph centrality measures, which seeks to measure the “importance” of a vertex in a graph. We describe several different applications of centrality measures, including an analysis of citation networks for academic articles on the topic of the COVID- 19 pandemic.

• Keywords: Dijkstrin algoritam; telekomunikacije; mjere centralnosti
• Keywords (english): Dijkstra’s algorithm; telecommunications; centrality measures
• Language: croatian
• URN:NBN: urn:nbn:hr:217:110930
• 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: Open access
• Created on: 2021-11-05 12:03:36