Analiza in nadgradnja aplikacije za delo z grafi : diplomsko delo

Korošec, Luka Taras (author), Šparl, Primož (mentor), Zapušek, Matej (co-mentor)

Ob svojem študiju na Pedagoški fakulteti Univerze v Ljubljani sem se ob obiskovanju predmetov Teorija grafov, Diskretna matematika in Računalniška matematika spoznal s spletno aplikacijo z0diak za delo z grafi. Aplikacijo, ki vsebuje zajeten nabor funkcij, je v okviru svojega diplomskega dela leta 2013 razvil Luka Jurković. Z njo lahko ustvarimo vizualno reprezentacijo enostavnih neusmerjenih grafov in nato na prikazanem grafu uporabljamo različna orodja. Tekom večletne uporabe aplikacije sem spoznal, da ima le-ta določene pomanjkljivosti in da bi bile dobrodošle kakšne dodatne funkcije, zato sem se odločil, da v okviru svojega diplomskega dela analiziram aplikacijo in njeno uporabnost ter jo nadgradim z novimi funkcijami in funkcionalnostmi. Analizo uporabnosti aplikacije sem opravil s pomočjo anketnega vprašalnika in sicer med študenti, ki so aplikacijo redno uporabljali pri svojem študiju. Glede na rezultate analize odgovorov ter tehnično in algoritemsko zahtevnost implementacije, sem izluščil tiste funkcionalnosti, ki sem jih lahko dodal v aplikacijo. Le-ta sedaj med drugim poleg obstoječih funkcionalnosti podpira tudi izračun in prikaz ožine ter premera grafa, prikaz zaporedja stopenj grafa in funkcije, s katerimi si lahko pomagamo pri iskanju Hamiltonovega cikla. V diplomskem delu je razloženo njihovo delovanje, na konkretnih primerih pa je prikazan tudi primer uporabe funkcij.

• Language: Slovenian
• Keywords: aplikacija z0diak, manipulacija grafa, premer, ožina, Hamiltonov cikel
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: PEF - Faculty of Education
• Publisher: [L.T. Korošec]
• Year: 2016
• Number of pages: 33 str., [3] str. pril.
• PID: 20.500.12556/RUL-85946
• UDC: 004.4(043.2)
• COBISS.SI-ID: 11193161
• Publication date in RUL: 20.09.2017

Secondary language

• Language: English
• Title: Analysis and an improvement of an application for graph manipulation

Abstract

During my studies at the Faculty of Education, University of Ljubljana, I familiarized myself with a web application for graph manipulation called z0diak while I was attending courses on Graph Theory, Discrete Mathematics and Computer Mathematics. This application, which has a substantial set of functionalities, was developed by Luka Jurković for his diploma thesis in 2013. With it we can create visual representations of simple undirected graphs and then use a multitude of tools on the displayed graph. In my years of using this application I realized that it has a few shortcomings and that I would appreciate new additional features. That is why I decided to analyze the application and its usability and upgrade it with new features and functionalities for my diploma thesis. Using a questionnaire and with the help of students who used the application regularly in their studies, the analysis of usefulness of the application has been carried out. According to the results of the analysis of student responses as well as technical and algorithmic complexities of the implementation, I discerned those features that could be added to the application with a reasonable amount of effort and added them. Apart from the existing functionalities the application now also supports the calculation and display of the girth and diameter of the graph, calculation of the graph degree sequence and functions which can help in determining whether a graph contains a Hamiltonian cycle or not. The thesis explains how these functions were implemented and also presents a demonstration of their usage on specific examples.

• Keywords: computer application, graph, računalniška aplikacija, graf