Primjene teorije grafova

diplomski rad

• Naslov (engleski): Applications of graph theory
• Autor: Barbara Prkačin
• Mentor: Slaven Kožić (mentor)
• Član povjerenstva: Slaven Kožić (predsjednik povjerenstva)
• Član povjerenstva: Luka Grubišić (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Član povjerenstva: Siniša Slijepčević (č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: 2021-09-21, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: Dijkstrin algoritam; telekomunikacije; mjere centralnosti
• Ključne riječi (engleski): Dijkstra’s algorithm; telecommunications; centrality measures
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:110930
• 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: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-11-05 12:03:36