Search

Informacijsko komunikacijska omrežja že nekaj časa rastejo in postajajo vse pomembnejša. Uporabljamo jih vsi in posegajo v vse pore sodobne družbe. S pomembnostjo in razvojem informacijsko komunikacijskih omrežij raste tudi odgovornost, ki je na strani tistih, kateri upravljajo z omrežji. Omrežja je potrebno dograjevati, jih nadzirati in učinkovito upravljati, da lahko uporabnikom zagotovijo kvalitetno in varno uporabniško izkušnjo. Zadnja leta opažamo pospešen razvoj orodij, ki lajšajo delo omrežnim inženirjem in zmanjšujejo vpliv človeškega faktorja. V magistrski nalogi obravnavamo načine avtomatizacije upravljanja in nadziranja omrežnih naprav. V nalogi so opisani različni omrežni protokoli in orodja za avtomatizacijo kot so NETCONF, RESTCONF, gRPC, Ansible, Chef in ostali. Poudarek je na načinu avtomatizacije z uporabo lastnih skript, napisanih v programskem jeziku Python in uporabi knjižnic Netmiko in NAPALM. Avtomatizacija v kontekstu IKT-omrežij predstavlja nadomestek človeške interakcije z omrežnimi napravami. Z avtomatizacijo se med sistemi izmenjujejo podatki, ki jih je potrebno obdelati, jih shraniti in jih interpretirati, da nam lahko podajo potrebne informacije. Zato sem v nalogi obravnaval možnosti hranjenja podatkov v relacijskih in nerelacijskih podatkovnih bazah in kritično vrednotil primernost obeh načinov pri avtomatizaciji. Poleg tega sem podrobno predstavil eno izmed orodij za učinkovito razčlenjevanje podatkov, to je Python knjižnica TextFSM. V nalogi je predstavljen primer, kako lahko več členov in orodij, ki skrbijo za različne funkcionalnosti, ki nam lajšajo delo z omrežij, združimo v celoto in jih povežemo v uporabnikom prijazno platformo. V primeru platforme gSmart, ki je opisana v magistrski nalogi, so za avtomatizacijo uporabljene lastne Python skripte, podatki se hranijo v graf bazi, upravljanje platforme pa je dogodkovno vodeno. Information and communication networks have been growing for some time now and are becoming increasingly important. We all use them, and they permeate every aspect of modern society. With the significance and development of information and communication networks, the responsibility of those who manage the networks also grows. Networks need to be expanded, monitored, and efficiently managed in order to provide users with a quality and secure user experience. In recent years, there has been accelerated development of tools that facilitate the work of network engineers and reduce the impact of the human factor. In my master's thesis, I address methods of automating the management and monitoring of network devices. The thesis describes various network protocols and automation tools such as NETCONF, RESTCONF, gRPC, Ansible, Chef, and others. The emphasis is on automation using custom scripts written in the Python programming language and the use of libraries such as Netmiko and NAPALM. Automation in the context of ICT networks represents a replacement for human interaction with network devices. Through automation, data is exchanged between systems, which needs to be processed, stored, and interpreted in order to provide us with the necessary information. Therefore, I explored the options for storing data in relational and non-relational databases and critically evaluated the suitability of both approaches for automation. Additionally, I provided a detailed presentation of one of the tools for effective data parsing, namely the Python library TextFSM. The thesis presents an example of how multiple components and tools that handle various functionalities, making our work with networks easier, can be integrated into a whole and connected to a user-friendly platform. In the case of the gSmart platform described in the master's thesis, custom Python scripts are used for automation, data is stored in a graph database, and the management of the platform is event-driven.

Parkinsonova bolezen je počasi napredujoča, nevrodegenerativna bolezen, za katero ne poznamo vzroka nastanka. Glavni znaki bolezni so tremor, zaviranje gibanja (rigidnost) ter upočasnjenost gibanja. Resnost bolezni zdravniki ocenjujejo s pomočjo lestvice MDS-UPDRS. Lestvica vključuje sklop za ocenjevanje motoričnih sposobnosti pacienta, v katerega spada vaja tapkanja s prsti. V okviru te diplomske naloge smo se osredotočili na analizo video posnetkov, na katerih pacienti s parkinsonovo boleznijo izvajajo vajo tapkanja s prsti. Opazovali in analizirali smo različne motnje gibanja, ki so opisane v lestvici MDS-UPDRS. Cilj te diplomske naloge je bil izdelati funkcionalno programsko opremo, s katero bi avtomatizirali postopek analize prej omenjenih video posnetkov pacientov, in razviti aplikacijo za pomoč zdravnikom pri ocenjevanju vaje tapkanja s prsti. Parkinson's disease is a progressive, neurodegenerative disease whose cause is unknown. Main signs of the disease are tremor, rigidity and slowness of movement. Doctors assess the severity of Parkinson's using the MDS-UPDRS scale. Scale includes a section for evaluating the patient's motor skills, which includes a finger tapping exercise. Within the scope of this diploma thesis, we focused on the analysis of videos in which patients with Parkinson's disease perform a finger tapping exercise. We observed and analyzed various movement anomalies, which are described in the MDS-UPDRS scale. The goal of this thesis was to create a functional software that would automate the analysis process of the mentioned video recordings and develop an application to help doctors with finger tapping exercise evaluation.

Banke in ostale finančne institucije morajo dandanes zadovoljiti celi vrsti regulativnih zahtev, ki se osredotočajo na pregled njihove stranke in preprečevanje pranja denarja. Potencialno rešitev za skalabilno in učinkovito izvajanje postopkov pregleda stranke predstavlja koncept samosuverene digitalne identitete (SSI) z uporabo decentraliziranih identifikatorjev (DID) in preverljivih poverilnic. Na podlagi problema so bile definirane zahteve praktične rešitve, ki so služile kot iztočnica za načrtovanje arhitekture z uporabo UML diagramov in izbiro ustreznih tehnologij, uporabljenih pri implementaciji. V okviru diplomske naloge smo izdelali aplikacijo, ki predstavlja praktično demonstracijo uporabe SSI za izpolnjevanje pogojev zakonov o pregledu stranke za izvajanju transakcij na Ethereum verigi blokov. Funkcionalnosti SSI so bile razvite z uporabo ogrodja Veramo ter DID metodo ethr, ki temelji na Ethereum verigi blokov. Z namenom omogočanja vizualnega pregleda skladnosti transakcij z omenjenimi zakoni, aplikacija nato podatke o izvedenih transakcijah ter metapodatke o poverilnicah zapiše v lokalno podatkovno bazo Neo4j, ki se uporabi za vizualizacijo podatkov verige blokov v obliki grafa. Ugotovili smo, da implementacija SSI z uporabo DID in preverljivih poverilnic, ki temeljijo na DID metodi ethr, predstavljajo enostaven in učinkovit mehanizem za izdajanje digitalnih poverilnic, ki se uporabijo za dokazovanje izpolnjevanja pogojev zakonov pregleda stranke. Izpostavili smo izrazito prednost ponovne uporabe izdanih poverilnic, nezmožnost ponarejanja poverilnic in dejstva, da se izdane poverilnice hranijo izključno pri uporabniku in ne tudi v centraliziranih podatkovnih bazah. Poleg tega lahko potencialni regulator z uporabo vizualiziranega grafa na preprost način preveri ali imajo stranke (naslovi in transakcije na Ethereum verigi blokov) ustrezna potrdila. Banks and other financial institutions today have to satisfy a whole range of regulatory requirements that focus on customer due diligence and preventing money laundering. A potential solution for the scalable and efficient implementation of customer screening processes is the concept of self-sovereign identity (SSI) using decentralized Identifiers (DID) and verifiable credentials. Based on the problem, the requirements of a practical solution were defined, which served as a starting point for the design of the architecture using UML diagrams and the selection of appropriate technologies used in the implementation. As part of the thesis, we created an application that represents a practical demonstration of the use of SSI to meet the requirements of customer due diligence laws and know your customer (KYC) guidelines to conduct transactions on the Ethereum blockchain. The functionalities of SSI were developed using the Veramo framework and the ethr DID method, which is based on the Ethereum blockchain. With the aim of enabling a visual review of the compliance of transactions with the aforementioned legislation, the application then stores data about executed transactions and metadata about verifiable credentials to the local Neo4j database, which is used to visualize blockchain data in the form of a graph. We have found that the implementation of SSI using DID and verifiable credentials based on the ethr DID method provides a simple and efficient mechanism for issuing digital credentials that can be used to demonstrate compliance with customer verification laws. We highlighted the distinct advantage of reusing issued credentials, the impossibility of falsifying issued credentials and the fact that issued credentials are store exclusively on user's personal device and not in any centralized databases. In addition, a potential regulator can easily check whether clients (addresses and transactions on the Ethereum blockchain) have the appropriate certificates using the visualized graph.

V tem diplomskem delu obravnavamo integracijo algoritma SICS v programsko okolje R. Gre za algoritem namenjen reˇsevanju problema podgrafenga izomorfizma, ki se nanaˇsa na iskanje vzorcev manjˇsega grafa v veˇcjem. Algoritem je na testiranjih dosegel boljˇse rezultate od predhodnih algoritmov za reˇsevanje tega problema. Implementiran je v jeziku C++, kar mu omogoˇca hitrejˇse izvajanje. Ker smo ˇzeleli algoritem uporabljati v programskem okolju R smo ga morali tja integrirati. Rezultat te integracije je paket SICS, ki se nahaja na Githubu in je javno dostopen. Deluje tako, da ga namestimo v naˇse razvojno okolje, nato pa ga uporabljamo kot knjiˇznico z eno funkcijo. Funkcija kot vhod sprejme dva grafa in razliˇcne parametre za izvajanje, kot izhod pa vrne seznam s preslikavami vozliˇsˇc med vhodnima grafoma. In this diploma thesis we will deal with integration of algorithm SICS into R program environment. This algorithm was created for solving the problem of subgraph isomorphism, which refers to pattern matching problem between smaller and bigger graph. In the benchmarks an algorithm performed better the previous algorithms for solving this problem. Algorithm is implemented in C++ programming language which enables him to perform faster. Since we wanted to use the algorithm in R software environment, we had to integrate it there. The result of this integration is the SICS package which is located on Github and is publicly available. It works such that we install it first in our development environment and from then on we use it as a library with single function. The function accepts two and various execution parameters graphs as input , and returns a list with node mappings between the input graphs as an output.

Najprej se seznanimo s tropskim polkolobarjem, polinomi nad tropskim polkolobarjem in tropskimi matrikami. Glavna tema je simetrični Barvinokov rang, eden izmed mnogih možnih rangov tropskih matrik. Preučimo matrike z rangom $1$ in tiste z neskončnim rangom ter si ogledamo transformacijo matrik, ki ohranja rang. Poiščemo tudi zgornjo mejo za simetrični Barvinokov rang, pri čemer ugotovimo, da rang lahko preseže velikost matrike. Pri obravnavi ranga si pomagamo tudi s teorijo grafov in na ta način zgornjo mejo še nekoliko izboljšamo. Teorijo grafov uporabimo tudi pri obravnavi primera matrike z rangom, večjim od njene velikosti. First we get familiar with the tropical semiring, polynomials over tropical semiring and tropical matrices. The main theme is the symmetric Barvinok rank, one of the many possible ranks of tropical matrices. We examine matrices with rank $1$ and those with infinite rank and look at the transformation of matrices that preserve rank. We also find the upper bound for the symmetric Barvinok rank, noting that the rank can exceed the size of the matrix. When dealing with rank, we also use graph theory to improve the upper limit a bit. Graph theory is also used to consider an example of a matrix with a rank greater than its size.

ZX-račun je nov pristop k formalizaciji kvantnega računalništva. Kvantna vezja in procese predstavimo z barvnimi diagrami z dodatnimi pravili za poenostavljanje, kar omogoči opis vsakega kvantnega vezja. Ogledamo si tudi več različic ZX-računa, ki omogočijo predstavitev različnih modelov kvantnega računalništva. Diagrame lahko pretvorimo tudi v matrike. Prikažemo tudi nekaj uporab ZX-računa, na primer kvantno teleportacijo in poenostavljanje vezij. ZX-calculus is a new approach to the formalization of quantum computing. Quantum circuits are represented with coloured diagrams with added simplification rules. Using ZX-calculus, we can describe any quantum circuit. We also explore several fragments of ZX-calculus and their use in describing different computational models. The diagrams can also be converted to matrices. We also show a few applications, such as the circuit optimisation and quantum teleportation.

Problem usmerjanja vozil s kapaciteto je NP-poln kombinatorični problem. Poleg njegove uporabnosti za dostavne službe se lahko nanj učinkovito preslika tudi veliko drugih problemov. Za reševanje problema uporabim rekurenčno nevronsko mrežo GRU z mehanizmom pozornosti. Po fazi učenja, ki traja toliko časa kot uporaba stohastičnih optimizacijskih algoritmov na več tisoč primerih, dobimo na majhnih grafih primerljivo dobre rezultate, na večjih grafih pa se zaradi povečevanja kompleksnosti problema nevronski model ne uči več dovolj hitro in je slabši. Med vložitvami grafov, ki sem jih preizkusil, dajeta najboljše rezultate node2vec in GraRep. The capacitated vehicle routing problem is an NP-complete combinatorial problem. In addition to its usefulness for delivery services, many other problems can be efficiently mapped to it. To solve the problem, I use the GRU recurrent neural network with the attention mechanism. After a learning phase that lasts as long as using stochastic optimization algorithms on thousands of cases, we get comparatively good results on small graphs. On larger graphs the neural models do not learn fast enough and produce worse results due to an increasing problem complexity. Among the tested graph embedding methods, node2vec and GraRep give the best results.

Matroidi so struktura v kombinatoriki, ki jo je prvi predstavil Hassler Whitney leta 1935, pri kateri se pojme kot so neodvisna mnozica, cikel, baza, rang, minor, dual in druge naravno posplosi in uporablja. Matroide lahko deniramo na vec nacinov, pri tem pa izhajamo predvsem iz terminologije uporabljene v teoriji grafov in linearne algebre. Glede na to, kako matroide deniramo, jih lahko uporabimo pri razlicnih kombinatoricno-optimizacijskih problemih, kot sta problem pakiranja in pokritja ter pozresna metoda. Matroids are a combinatorical structure, rst introduced by Hassler Whitney in 1935, that generalizes and uses notions such as independent set, cycle, base, rank function, minor, duality and others. Matroids can be dened in dierent ways, mostly using terminology used in graph theory and linear algebra. Based on the denition used, we can use matroids in a variety of problems from the elds of combinatorics and optimization, such as the packing and covering problems, as well as the greedy method.

Trikotniki v grafu so podgrafi, sestavljeni iz treh povezanih vozlišč. Število trikotnikov je računsko zahtevna statistika, ki se pogosto uporablja v analizi velikih omrežij in v raznih primerih uporabe, kot so recimo odkrivanje skupnosti v omrežju, zaznavanje vsiljive vsebine, odkrivanje skritih tematskih struktur. Cilj diplomskega dela je pregled in primerjava algoritmov za štetje trikotnikov. Na začetku predstavimo problem, definicije in nekaj primerov uporabe štetja trikotnikov. Nato predstavimo algoritme za točno štetje trikotnikov, zatem pa še algoritme za približno štetje. Na koncu sledi še primerjava hitrosti in kratek zaključek. Triangles in a graph are subgraphs composed of three connected nodes. The number of triangles is a computationally intensive statistic that is often used in the analysis of large networks and in various use cases, such as discovering communities in a network, detecting spam, discovering hidden thematic structures. The aim of the thesis is to review and compare algorithms for counting triangles. At the beginning we present the problem, definitions and some examples of the use of counting triangles. Then we present algorithms for exact counting of triangles, and then algorithms for approximate counting. Finally, there is a comparison of speed and a short conclusion.

V diplomski nalogi predstavljamo interaktivno aplikacijo, ki vizualizira delovanje nekaterih algoritmov za iskanje najkrajših poti na grafih. Iz precej širokega nabora algoritmov smo izbrali Dijkstrov, Bellman-Fordov, Floyd-Warshallov, D'Esopo-Papeov in Fredman-Tarjanov algoritem. V besedilu teoretično predstavljamo njihovo delovanje in uporabo na različnih področjih, navajamo pa tudi njihovo psevdokodo. Predstavljamo tudi delovanje aplikacije in primere delovanja za posamezne algoritme. Aplikacijo smo izdelali kot didaktički pripomoček, namenjen tako učiteljem kot študentom. In this diploma thesis, we present an interactive application for visualizing algorithms for finding shortest paths in graphs. From a fairly large set of algorithms, we selected the Dijkstra, Bellman-Ford, Floyd-Warshall, D'Esopo-Pape, and Fredman-Tarjan algorithm. We describe them informally and in pseudocode. Tha application was designed as a didactic tool, both for teachers and for students.

V okviru diplomske naloge smo obdelali problem vizualizacije podatkov, ki zaradi količine podatkov ali kompleksnosti grafov in orodij velikokrat ne pride dosti do izraza. Konkretno smo se osredotočili na podatke v proizvodnji, saj obstaja veliko sistemov za upravljanje proizvodnje (MES), s katerimi lahko vizualno spremljamo njen razvoj. Predstavili smo tri orodja, s katerimi smo razvili svoj sistem za upravljanje proizvodnje. Podrobneje smo opisali podatkovno bazo in shranjevanje podatkov ter spletni vmesnik Node-RED, v katerem smo razvili jedro sistema za komunikacijo med posameznimi procesi in aplikacijami. Na koncu smo na spletni aplikaciji Grafana predstavili rezultat sistema in njegov namen. Prikazali smo linijske in tabelarne grafe, nekaj razširitev za popestritev posameznih grafov ter osnovne in napredne funkcije, ki jih spletna aplikacija ponuja uporabniku. Pri razvoju sistema smo predstavili smiselnost uporabe Grafane in opisali njen razvoj, ter zakaj je ena izmed boljših izbir za vizualizacijo podatkov v današnjem času. In the scope of this BSc thesis, we described the problem of data visualization, which due to the amount of data or the complexity of graphs often does not show its full potential. We mainly focused on production company data, because there are a lot of Manufacturing Execution Systems (MES), which provide us the overlook on our production. We have presented three tools that can be connected and use them to create our own data visualization system. We have described in detail ArangoDB database and storing of the data. We also described a programming interface called Node-RED, where we built the core of the system for communication between Grafana and the database. In the end, we showed the finished visualization system and all the graphs made in Grafana. We presented line and table graphs, some extensions to diversify individual graphs, and the basic and advanced functions that Grafana offers to the user. In system development, we presented the meaningfulness of using Grafana and why it is one of the best choices for data visualization.

Max-plus algebra spada med tista področja matematike, katerih razvoj se je začel relativno pozno, zato postaja vse bolj zanimiva za raziskovalce, novejše raziskave na tem področju pa kažejo tudi na njeno večstransko uporabnost. Ker ima zaradi lastnosti svojih operacij prednost pri reševanju nekaterih problemov, so jo uporabili tudi pri sestavi voznih redov. V magistrskem delu si podrobno ogledamo koncept max-plus algebre in njenih lastnosti. Poleg tega vidimo tudi, s katerimi algoritmi in pod katerimi predpostavkami je mogoče izračunati lastne vrednosti in njim pripadajoče lastne vektorje matrik. Preučimo tudi, kako so na Nizozemskem z njeno pomočjo sestavili železniške vozne rede, in si ogledamo algoritme, uporabljene v ta namen. Potem s tem načinom pripravimo tudi analogno analizo za poenostavljeno slovensko železniško omrežje. Max-plus algebra is one of the areas of mathematics that started developing relatively late. So it is becoming increasingly interesting for researchers. Recent research in this area also indicates its multifaceted applicability. Because it has, due to the nature of its operations, an advantage in solving some problems, it has also been used in compiling timetables. In the master's thesis we look closely at the concept of max-plus algebra and its properties. In addition, we also examine with which algorithms and under which assumptions is it possible to calculate eigenvalues and their associated eigenvectors of matrices. We also look at how railway timetables were put together in the Netherlands with the help of max-plus algebra and which algorithms were used for this purpose. With this method we then prepare an analogous analysis for the simplified Slovenian railway network.

Povezanost grafa nam pove, koliko povezav oziroma vozlišč moramo odstraniti, da graf postane nepovezan. Tako poznamo povezavno povezanost in vozliščno povezanost grafa. Na začetku bom predstavil nekaj izrekov, ki se nanašajo na povezanost grafov. Nato bom opisal algoritme za preverjanje povezanosti grafov, ki služijo tudi kot orodje za preverjanje uspešnega razbitja grafov. V zadnjem delu pa bom najprej predstavil reševanje problema minimalnega prereza z algoritmom za največji pretok, nato pa še druge naprednejše in bolj prilagojene algoritme za ta problem. V zaključku bom povzel vse ključne ugotovitve. Diplomska naloga tako predstavlja osnovni pregled problema povezanosti grafov. Graphs connectivity tells us how many edges or vertices must be removed from a graph so that the graph becomes disconnected. This induces the notations of the edge and vertex connectivity of a graph. In this thesis, I will first present some of the theorems related to graph connectivity. Then I will describe algorithms for checking whether or not a graph is connected, which can also be used to check whether or not a graph has been successfully split. Next, I will show how the min-cut problem is solved using the algorithm for maximum flow. Then, I will continue with presentation of some advanced and more adapted algorithms for the considered problem. Finally, I will conclude the thesis with a summary of the key findings. The thesis is thus a basic overview of the problem of graph connectivity.

V magistrskem delu obravnavamo pojem spektra grafa, ki predstavlja eno od orodij za proučevanje kombinatorične strukture grafov in ga lahko uporabimo pri reševanju raznovrstnih problemov, od izrazito teoretičnih do takšnih z možnostjo uporabe v drugih znanstvenih vedah. Spekter grafa definiramo kot množico lastnih vrednosti neke pripadajoče sosednostne matrike. V delu določimo spektre nekaterih standardnih družin grafov (polni grafi, prazni grafi, polni dvodelni grafi, grafi zvezde, cikli, poti,...). Med drugim ugotovimo, da so prazni grafi edini grafi, ki imajo eno samo lastno vrednost, da imajo polni grafi natanko dve različni lastni vrednosti, lastne vrednosti dvodelnih grafov pa so vedno simetrične. Obravnavamo tudi različne lastnosti lastnih vrednosti grafa, predvsem največje, katere velikost omejimo glede na števili vozlišč in povezav grafa. V nadaljevanju se osredotočimo na drevesa, ki so definirana kot povezani grafi brez ciklov. Drevesa oziroma gozdove določenega reda uredimo glede na njihovo gostost s pomočjo Lovász-Pelikanove relacije preko lastnosti karakterističnih polinomov. V razdelku o krepko regularnih grafih dokažemo, da so to natanko grafi s tremi različnimi lastnimi vrednostmi, nato pa z uporabo lastnosti spektra krepko regularnih grafov predstavimo klasifikacijo Mooreovih grafov premera 2. Srečamo se tudi z Izrekom o prijateljstvih, ki ob preoblikovanju v vsakdanje življenje pravi: če v skupini ljudi velja, da imata poljubna dva človeka natanko enega skupnega prijatelja, potem v tej skupini obstaja človek, ki je prijatelj z vsemi ljudmi iz skupine, ter ta izrek tudi dokažemo. V zadnjem razdelku obravnavamo še energijo grafa, ki je definirana kot vsota absolutnih vrednosti lastnih vrednosti grafa. Pri tem določimo energijo nekaterih standardnih družin grafov, preverimo kakšne so zgornje meje za vrednost energije in kdaj so te meje dejansko tudi dosežene. Grafom, ki dosežejo zgornjo mejo za vrednost energije, pravimo grafi z maksimalno energijo. V delu predstavimo rezultate Koolena in Moultona, da so takšni povezani grafi natanko polni grafi in krepko regularni grafi. In my thesis I deal with the notion of the graph spectrum that represents one of the tools for examining combinatorial structure of graph and can be used for solving different problems, including theoretical ones and those with applications in other sciences. The spectrum of a graph is defined as the set of graph eigenvalues, which are obtained as eigenvalues of a corresponding adjacency matrix. In the thesis spectra of some standard graph families is computed (complete graphs, empty graphs, complete bipartite graphs, star graphs, cycles, paths,...). Among other results we see that empty graphs are the only ones with a single eigenvalue, that complete graphs have exactly two distinct eigenvalues and that the eigenvalues of bipartite graphs are always symmetric. A discussion of diverse properties of graph eigenvalues follows, where the focus is on the properties of the largest eigenvalue, which is bounded by the numbers of graph vertices and edges. Later the emphasis is on trees, that is, connected graphs without cycles. Trees and forests of specific order are partially ordered according to their density by the Lovász-Pelikan relation. In the section on strongly regular graphs it is proved that these are exactly the graphs with three distinct eigenvalues. Then the classification of Moore graphs with diameter 2 is presented by the use of strongly regular graphs' properties. This is followed by proof of the Friendship theorem, which translated into the everyday life, goes: if it's true that in a group of people any two random persons have exactly one common friend, then there is a person in this group who is everybody's friend. In the final section we define graph energy as a sum of absolute values of the graph eigenvalues. The energy of some standard graph families is discussed, as well as the upper bounds for the energy values. The graphs that attain the upper bound for the energy value are called the maximum energy graphs. We present result of Koolen and Moulton that such connected graphs are exactly complete graphs and strongly regular graphs.

Ideja dela je spoznati se z osnovnimi pojmi teorije grafov, kot so omrežje, pretok in maksimalni pretok ter predstaviti algoritem potisni-povišaj za iskanje maksimalnega pretoka v omrežju. Algoritem je tudi implementiran, pokazana pa je tudi njegova časovna zahtevnost in pravilnost delovanja. Uporabnost iskanja maksimalnih pretokov je ponazorjena z dvema primeroma iz vsakdanjega življenja. The idea of this work is to get used to basic concepts of graph theory, e.g. network, flow and maximum flow. The core is an explanation of push-relabel algorithm for finding maximum flow through a network. The algorithm is also implemented and its time complexity and correctness are proven. It is also shown with two examples how one can use maximum flows in real life.

V magistrskem delu preučujemo lastne vrednosti realnih simetričnih matrik. Zanima nas najmanjše možno število $q(G)$ različnih lastnih vrednosti vseh matrik, katerih ničelno-neničelni vzorec pripada vnaprej predpisanemu grafu $G$. Za različne družine grafov $G$ izračunamo $q(G)$. Pri tem si pogledamo tudi lastnosti spojev grafov ter kartezičnih, tenzorskih in krepkih produktov grafov. V posebnem nas zanimajo grafi $G$ na $n$ točkah, za katere velja $q(G)=1,2,n-1$ ali $n$. The aim of this work is to present the properties of eigenvalues of real symmetric matrices. We are interested in finding the minimum number of distinct eigenvalues $q(G)$ of all matrices whose zero-nonzero pattern belongs to a given graph $G$. For some families of graphs $G$ we calculate $q(G)$. We mention the properties of the join of two graphs and also Cartesian, tensor and strong products of graphs. In particular, we are interested in graphs $G$ on $n$ points, for which $q(G)=1,2, n-1$ or $n$.

Pojem pakirnega kromatskega števila prihaja iz področja načrtovanja frekvenc v brezžičnih omrežjih. Pri pakiranju k-barv grafa G, morajo biti vozlišča grafa z barvo i paroma na večji razdalji kot si. Magistersko delo proučuje različne metode za računalniško iskanje pakirnega kromatskega števila za različne neskončne mreže. V delu predstavimo nov algoritem za iskanje pakirnega kromatskega števila, s katerim nam uspe izboljšati zgornje meje različnih neskončih mrež. The notion of packing chromatic number comes from the area of frequency planning in wireless networks. The nodes in a k-color packing of graph G with the color i must be pairwise at a distance greater than si. The thesis discusses different methods for computer searching the packing chromatic number for different lattices. We present a new algorithm for searching the packing chromatic number, with which we were able to improve the upper bounds of different lattices.

V projektnem delu smo proučevali načine za nadzorovanje računalniškega sistema. Opisali smo dogodke, ki jih je treba spremljati, ter na kak način je treba reagirati na te dogodke. Predstavljeni so vsi osnovni elementi, ki sestavljajo učinkovit sistem za nadzorovanje, to so metrike, podatkovna baza, vizualizacija podatkov ter proženje obvestil ob kritičnih trenutkih. Predstavili smo, kako zgraditi uporabno orodje za nadzor računalniškega sistema s pomočjo odprtokodnih programov. In the final project work, we studied ways to control the computer system. We have described the events to be monitored and how to react to those events. All basic elements that make up an effective monitoring system, such as metrics, databases, data visualization and triggering of notifications at critical moments, are presented. We presented how to build a useful tool for monitoring the computer system using open source programs.

V teoriji grafov drevo pomeni kombinatoričen objekt, ki ga običajno definiramo kot povezan graf brez ciklov. V nalogi je predstavljen problem preštevanja različnih dreves s podanim številom vozlišč. Podani so štirje dokazi znamenitega Cayleyevega izreka za število označenih dreves: dokaz s Prüferjevo bijektivno konstrukcijo, dokaz s preštevanjem zakoreninjenih dreves na dva načina J. Pitmana, dokaz z rekurzivno formulo za število označenih gozdov in dokaz z uporabo Kirchhoffove zveze med determinantami matrik in vpetimi drevesi. V zadnjem delu je izpeljan novejši rezultat A. China in ostalih, o verjetnosti, da je naključno izbrano drevo v polnem grafu vpeto drevo. Posebej je obravnavano obnašanje limitne vrednosti verjetnosti, ko število vozlišč polnega grafa raste čez vse meje. Dobljeni rezultat je presenetljiv in lep. In graph theory, trees are combinatorial objects usually defined as connected graphs without cycles. In this thesis, the problem of counting different trees with a given number of vertices is presented. Four proofs of a celebrated theorem on the number of labeled trees by A. Cayley are given: by using a bijective construction due to H. Prüfer, by double counting of labeled rooted trees due to J. Pitman, by establishing a recursion on the number of labeled forests, and finally, by applying a relation between determinants and spanning trees due to H. Kirchhoff. In the final part, a recent result by A. Chin et al. is presented on the probability that a randomly picked tree in a complete graph is a spanning tree. In particular, the limit of this value as the number of vertices approaches infinity is observed. The result obtained is both surprising and beautiful.

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. 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.

V diplomski nalogi smo analizirali naloge z računalniškega tekmovanja Bober, ki se nanašajo na grafe. V prvem delu naloge smo opisali algoritme iz teorije grafov, ki jih pogosto uporabljamo v računalništvu. Nato smo pregledali naloge s tekmovanja Bober in izbrali tiste, ki so povezane s teorijo grafov. Izbrane naloge smo razvrstili v skupine na tri različne načine: najprej glede na uporabljen algoritem iz teorije grafov, nato glede na abstraktnost grafa, ki se v nalogi pojavi, na koncu pa še glede na abstraktnost same naloge. In thesis we analyzed graph-theoretic tasks in Bebras competition. First we described graph-theoretic algorithms, which are commonly used in computer science. Then we chose tasks from Bebras competition challenges which refer to graph theory and classified selected tasks in groups in three different ways: first depending on used algorithm from graph theory, then according to the abstractness of graph that appears in the task, and in the end also according to abstractness of the entire task.

V diplomski nalogi obravnavamo segmentacijo slik s pomočjo največjega pretoka. V prvem delu podrobneje predstavimo problem največjega pretoka in njemu dualen problem najmanjšega prereza. Predstavimo tudi dva alogritma za reševanje teh dveh problemov, to sta algoritem Forda in Fulkersona in Diničev algoritem. V drugem delu diplomske naloge predstavimo pojem segmentacije slik in naštejemo nekaj metod, s katerimi se segmentacija izvaja. Nekatere od njih tudi opišemo. To so pragovna metoda, metoda razvrščanja v skupine, metoda regij in segmentacija na grafih. V zadnjem poglavju si podrobno pogledamo segmentacijo na grafih. Sliko predstavimo z uteženim grafom in na temu grafu poiščemo največji pretok oziroma najmanjši prerez. S pomočjo prereza potem ločimo slikovne pike na tiste, ki pripadajo ospredju in tiste, ki pripadajo ozadju. Vse algoritme predstavimo s psevdokodo in analiziramo njihovo časovno zahtevnost. Na koncu predstavimo tudi probleme, ki se pojavljajo pri tovrstni segmentaciji. In this thesis we consider image segmentation using maximum flow. In the first part of the thesis we present in detail the maximum flow problem and its dual problem, the minimum cut problem. We describe two algorithms for solving these two problems, the Ford-Fulkerson algorithm and Dinic algorithm. In the second part of the thesis we introduce the concept of image segmentation and we list some methods that are used for image segmentation. We describe some of them: the thresholding method, clustering methods, the region-growing methods and segmentation on graphs. In the last chapter we present in more detail segmentation on graphs using maximum flow. We represent a given image with a weighted graph. Then we find maximum flow and minimum cut in this graph. Using minimum cut we can separate pixels to those that belong to the foreground and those that belong to the background. Pseudo code is given for all the algorithms used and their time complexity is analyzed. At the end of the thesis we discuss some problems that arise in this kind of segmentation.

Grafe običajno uporabljamo za opisovanje podatkov z visoko stopnjo medsebojne povezanosti oz. odvisnosti ali v primerih, ko so informacije o povezavah med podatki, kar imenujemo tudi topologija podatkov, pomembnejše kot podatki sami. Pogosto so implementacije grafa in operacij nad grafom izključno programske. Programske implementacije so konvencionalnim procesorjem v veliko breme, saj tipično ne izkoriščajo pomnilniške lokalnosti. Pri delu z grafi se tako poraja potreba po učinkoviti strojni implementaciji podatkovne strukture. Delo obravnava računalniško arhitekturo, ki je rezultat izkoriščanja grafu inherentnega paralelizma in referenčne lokalnosti, ki jo povzroča njegova matrična reprezentacija. Začetna poglavja vsebujejo nekaj nauka o grafih in algebri za delo z grafi. Naslednje poglavje podaja teoretično zasnovo organizacije in arhitekture procesorja ter govori o premislekih in spoznanjih med njegovim snovanjem. Delo se zaključi z nekaj podrobnostmi o implementaciji procesorja v vezju FPGA in predlogom o integraciji vseh komponent sistema v smiselno celoto oz. konfiguracijo. Graphs are frequently used in cases where data to be described is densely interconnected or the information about said connections, also referred to as topology of the data, is more important than the data itself. Common solutions to graph processing and computation often rely on software, which in itself is a burden to the conventional widespread computer architecture. Henceforth, the need for an efficient hardware implementation of graph structures and their manipulation arises. This work is a treatise on hardware accelerated graph computation. It provides some knowledge about graphs and graph algebra, for use in what endeavours in the matter follow. It conveys some information on graph data structure and graph database. The latter is followed by the conception of the graph processor architecture and the reasoning behind it. Lastly, some details of a suitable implementation using an FPGA circuit are given and some common protocols are described to achieve a good overall integration as well as the integration of the processor itself.

Namen tega magistrskega dela je bila povezava teorije in prakse pridobljene tekom študija telekomunikacij, pri čemer je rezultat moral biti uporaben izdelek. Zaradi tega je bilo kot osnova vzeto preprosto omrežje, predstavljeno na primeru železniške makete, pri kateri je bila potrebna digitalizacija in avtomatizacija procesov. Omrežje predstavljeno na maketi je bilo tekom naloge modelirano z grafom omrežja, kjer imajo povezave le dve stanji: prosto ali zasedeno. Nad grafom omrežja je bil zgrajen sistem, ki na podlagi željenega urnika sam izračuna idealne poti izbranega vlaka ter to prikaže v uporabniku prijaznem uporabniškem vmesniku, medtem ko avtomatsko vodi vlake po maketi. Dodatno je bila razvita (in mestoma predelana že obstoječa) elektronika, ki omogoča komunikacijo računalnika z železniško maketo in obratno. The purpose of this masters thesis is to connect the theoretical and practical knowledge obtained during the study of telecommunications. The result needs to be a functional product. That is why a simple network represented on a model railway layout was taken as the basis. The layout needed to be fully digitized and automated. The network of the railway layout was modelled as a network graph, where the connections (vertices) only have two states: free or occupied. A system that could calculate the best route given a desired timetable was implemented above the network graph. That system also automatically drives the trains and visualizes everything to the user in a user interface. Electronics that allows the communication between the computer and the model railway layout was developed in addition to that. Some existing open-source electronics was remade.

Igra Hanojski stolp spada v področje razvedrilne matematike. Rešujemo jo tako, da premikamo diske iz začetne palice na končno palico po določenih pravilih. Cilj igre je uporabiti najmanjše število premikov. V diplomskem delu obravnavamo Hanojski stolp z usmerjenimi premiki diskov, kar pomeni, da obstajajo omejitve pri premikih. Ločimo pet različnih primerov Hanojskega stolpa, ki jih ponazorimo z digrafi. Vsak digraf ima tri vozlišča, med katerimi obstajajo usmerjene povezave. V prvem delu bomo najprej predstavili Hanojski stolp in podali osnovne definicije o grafih. V naslednjem poglavju se bomo osredotočili na rekurzivno in iterativno rešitev problema. Jedro diplomskega dela predstavljajo optimalne rešitve za vsak digraf ter izračunano število premikov. V zaključku bomo z digrafi stanj vizualizirali prepovedane, dovoljene ter uporabljene premike pri iskanju optimalne rešitve. Končna ugotovitev kaže na to, da podan algoritem za reševanje Hanojskega stolpa z omejenimi premiki daje optimalne rešitve problema. Vsaka druga rešitev daje nujno večje število premikov. Za vsak digraf bomo zapisali natančno formulo za izračun števila premikov. The game the Tower of Hanoi falls within the area of recreational mathematics. We solve it by moving discs from the initial position to the final position according to certain rules. The objective is to use minimal number of moves. In this graduation thesis we deal with the Tower of Hanoi with forbidden moves, which means that there are certain limited moves. We investigate five different cases of Hanoi Tower, which are represented by digraphs. Every digraph is a digraph on three vertices, between which there can be directed edges. In the first part we will introduce the Tower of Hanoi and present basic definitions of graphs. In the next chapter we will deal with the recursive and the iterative solution. The focus of this graduation thesis is on optimal solution of every digraph and calculated number of moves. In the last chapter we will visualize forbidden, allowed and used moves in the search of the optimal solution. The final results show, that the given algorithm for solving Hanoi Tower with forbidden moves provides optimal solution of the problem. Moreover, every distinct solution takes strictly more moves than the given algorithm. We will write down a precise formula for the number of moves for every digraph.

Pri poučevanju in učenju delovanja električnih vezij se zelo pogosto srečujemo z grafično predstavitvijo elementov in topologije vezja. Za dobro uporabniško izkušnjo dela z električnimi vezji pa mora biti predstavitev kvalitetno pripravljena. To še posebej velja pri učenju na daljavo, ki obenem zahteva tudi komuniciranje v realnem času, zato je za tako spletno aplikacijo pomembna tudi pravilna izbira primerne platforme. V pričujočem delu so predstavljeni obstoječi urejevalniki vezij in predlagana rešitev - aplikacija SONCE, ki je izdelana na platformi Meteor. Opisuje njeno namestitev, delovanje, uporabo pri nameščanju komponent, njihovem medsebojnem povezovanju v vezje ter možnim naknadnim urejanjem vezja, elementov in povezav. Prikazanih je več slik zaslona za različna stanja aplikacije, izpostavljen je pregled orodij za lastnosti vezja, kot so ime, opis, opis vezja (angl. netlist), graf vezja ter druge. Podana je uporaba s spletnim gostovanjem, ki omogoča skupinsko delo, predvidene izboljšave ter izvozni formati. While learning electrical circuits we are very often faced with graphical presentation of elements and topology of circuits. To achieve a good user experience presentations must be prepared well. This is especially true for distance learning, which additionally requires communication in real time. As a consequence, a corrected choice of the appropriate platform for the web application is important. This work surveys existing circuit editors and a novel solution - web application SONCE, build using the Meteor platform. The work describes installation and operations of the application, its usage while adding and connecting components into a circuit and possible subsequent editing of a circuit, elements and connections. Futhermore, screen shots for different states of application are shown, exposing overview of characteristics of the circuit, such as texts, netlist, chart of circuit and others. Finally, advantiges of web hosting usage is demonstrated and export formats are described.

Danes je v procesni avtomatizaciji večina industrijskih procesov vodena s pomočjo programirljivih logičnih krmilnikov ali krajše – PLC-jev. Ti za delovanje poleg dodatne strojne opreme potrebujejo program, ki glede na vhodne podatke upravlja z elementi procesa. Za reševanje različnih problemov se uporablja različne programske jezike in pristope. V diplomskem delu je predstavljen eden od načinov realizacije sekvenčno vodenih programov in sicer s programskim orodjem TIA Portal podjetja Siemens. Uvodni del diplomskega dela obsega predstavitev razvoja programiranja in osnovnih jezikov programiranja, ki jih opisuje standard IEC 61131-3. V drugem delu so predstavljeni osnove programskih jezikov in osnovna programska oprema, uporabljena za programiranje industrijskih PLC-jev. V zadnjem delu diplomskega dela je na praktičnem primeru prikazan in razdelan način programiranja sekvenčnih programov z osnovnimi in namenskim jezikom. Prikazan način je le eden od mnogih, ki se jih uporablja za različne rešitve problemov. Primer je namenjen prikazu načina programiranja in ni primeren za uporabo v živem procesu. Z nastavljenimi spremenljivkami za preverjanje napak in pogojev ga lahko razširimo in dopolnimo za vodenje industrijskih procesov. Today, most of automated industrial processes are controlled by programmable logic controllers or shorter – PLCs. Apart from additional hardware, their operation requires a program which in line with input data controls process elements. To solve different problems, different program languages and approaches are used. This thesis shall present one of the techniques used to realize sequentially driven programs, namely a Siemens TIA Portal program tool. The introductory part of the thesis includes a presentation of the development of programming and of basic program languages, as described by the standard IEC 61131-3. The second part shall present the basics of program languages as well as basic software used for industrial PLC programming. In the last part of the thesis we can find a technique of sequential software programming using the base and dedicated program languages, illustrated and structured on a practical example. The principle shown is only one of the ways in which different problems can be solved. The example is intended to illustrate the programming technique and is not suitable to be used in a living process. Setting variables for checking errors and conditions it can be expanded and supplemented to be used for industrial process control purposes.

Del kontrolnega sistema za pospeševalnik delcev je vizualizacija procesov na uporabniškem vmesniku za končne uporabnike. Uporabniški vmesnik izdelamo z uporabo sistema SCADA, na njem pa prikazemo stanja procesov in naprav pomembnih za pospeševalnik. Ko pri izmenjavi podatkov z napravami, ki jih uporabimo za vizualizacijo stanj procesov, naletimo na komunikacijski protokol, ki ga sistem SCADA ne pozna, je nasa naloga, da razvijemo rešitev, ki bo protokol razumela in vizualizirala prejete podatke. Za specifičen problem je rešitev grafični prikazovalnik podatkov v realnem času. Ob izdelavi aplikacije opišemo celoten razvojni proces od predstavitve širše slike pospeševalnikov delcev do problema, zahtev, načrtovanja, implementacije in testiranja. Part of the particle accelerator control system is visualization of processes on a graphical user interface (abbr. GUI ) for end users. GUI is made by using a SCADA system and displays states of processes and devices important to the particle accelerator. When encountered with a non-supported communication protocol and which content needs to be visualized, it is our task to develop a solution which understands the protocol and visualizes the content. For a specific problem a solution for it is a realtime graphical data viewer. In addition to making the application, a detailed description of the whole development process is given, from the big picture of particle accelerators to the specifications and requirements, architecture design, implementation and testing.

Namen diplomskega dela je bil izdelava napovednega modela, s katerim bi se lahko napovedovala sprememba lastništva v podjetju. Model je rezultat analize omrežja družbenikov, ki so zgrajena na podatkih o družbenikih in njihovi prisotnosti v podjetjih. Lastništvo je v bistvu stopnja vozlišča v omrežjih, ki so bila analizirana. V procesu grajenja modela je bistvenega pomena obdelava podatkov in njihova predstavitev v podobi omrežja. To je bilo narejeno s pomočjo programskega jezika Java in programskih vmesnikov OWL in Gephi. Dobljena omrežja v formi grafov je bilo treba naprej analizirati. Nadaljnja analiza je poskrbela za pridobitev mere pomembnosti vozlišč v omrežju, ker je bila njihova uporaba ključnega pomena v procesu napovedovanja. Dobljene mere so osnova za različne statistične metode, metode podatkovnega rudarjenja in metode strojnega učenja. Ugotovitve, pridobljene iz teh metod so pripeljale korak bližje do zamišljenega modela. Končni rezultat je napovedni model, ki je lahko osnova za namizno ali spletno aplikacijo, ki bi lahko služila za napovedovanje, ne le spremembe lastništva, ampak tudi drugih podatkov. The purpose of this thesis was the realization of a prediction model, with which we could predict the change of ownership in a network. The prediction model is a result of the analysis process of board collaboration networks, where the networks are in fact a representation of data for stockholders and their presence in a certain company. The ownership is represented with a node's degree in the networks which were analyzed. In the model realization process, data processing and their proper representation in the form of a network is essential. For that purpose, we used the Java programming language, coupled with the Application programming interfaces (APIs) OWL and Gephi. The resulting networks, represented as graphs, needed to be further analyzed in order for us to acquire the node importance metrics in the network, which were crucial for the prediction process. The acquired metrics are the basis for various statistical, data mining and machine learning methods. The results of those methods lead us to the creation of the model that we imagined in the first place. The end result can be the basis for a desktop or a web application who could predict not just ownership change, but also other data.

V jeziku Erlang smo s pomočjo knjižnice napisane v jeziku C, ki uporablja vmesnik OpenMP implementirali algoritem, ki uporablja tako vzporedno kot porazdeljeno računanje za iskanje ciklov v grafu, ki predstavlja dolžnike. Te cikle nato uporabimo za izvedbo pobotov med dolžniki. Cilj naloge je bil ugotoviti, ali je Erlang primeren za implementacijo razdeljevalnika za porazdeljen sistem. Po testiranju na naključno zgrajenih grafih majhnega sveta smo prišli do zaključka, da Erlang v čisti obliki za tako nalogo ni primeren in je potrebno poiskati druge rešitve. Using Erlang and a library written in C using OpenMP we implemented an algorithm that utilizes both parallel and distributed computing to find cycles in a graph which represents debtors. These cycles are then used to perform debt reconciliation between debtors. In the thesis we attempt to establish whether Erlang is suitable for the implementation of a work distribution component in a distributed system. After testing on random generated small-world graphs we conclude that Erlang in it's pure form is not appropriate for that task.

V diplomskem delu obravnavamo problem podgrafnega izomorfizma in njegovo integracijo v sistem ALGator. Iskanje izomorfnih podgrafov je dandanes prisotno na večih znanstvenih področjih, zato se vseskozi pojavljajo novi algoritmi za reševanje problema. Podrobneje smo opisali Ullmannov algoritem, izboljšani Ullmannov algoritem in algoritem RI, ki je najnovejši izmed naštetih. Njihove implementacije, katere so primerne za iskanje izomorfizmov tako na usmerjenih kot neusmerjenih neoznačenih grafih, smo zaradi integracije v sistem ALGator napisali v programskem jeziku Java. Sistem je namenjen predvsem raziskovalcem na področju razvoja algoritmov, saj omogoča enostavno testiranje njihove učinkovitosti in analizo pridobljenih rezultatov. Funkcionalnosti sistema smo v praksi uporabili na izbranemu problemu. Poleg definicije problema smo v projekt v ALGator-ju vključili vse implementirane algoritme (izboljšani Ullmannov algoritem je podan v dveh različicah) in opazovali njihovo učinkovitost. Eksperiment smo izvedli na več kot 50000 različnih parih grafov. Z analizo rezultatov v ALGator-ju smo pokazali, da je algoritem RI v primerjavi z ostalimi tremi algoritmi najhitrejši. Na drugi strani se je najslabše izkazal Ullmannov algoritem, njegovi izboljšani različici pa sta se v določenih scenarijih celo približala algoritmu RI. Z integracijo problema v sistem ALGator smo predstavili njegove zmogljivosti in navedli predloge za izboljšave. This thesis deals with a subgraph isomorphism problem and its integration into ALGator system. Detection of isomorphic subgraph is present in many scientific fields nowadays, therefore new problem solving algorithms constantly appear. We focus on a detailed description of Ullmann algorithm, improved Ullmann algorithm and RI algorithm, the most recent among listed. Those algorithms, which are suitable for isomorphism detection in directed or undirected unlabeled graphs, were implemented in Java programming language for the purpose of integration into ALGator. The system is intended for the use of algorithm development researchers, providing simplified testing of algorithm's efficiency and analysis of testing results. We have applied system functionalities on the selected problem. In addition to a problem definition we have included all the implemented algorithms into ALGator project (improved Ullmann algorithm is given in two versions) and observed their efficiency. We have executed the experiment on more than 50000 different pairs of graphs. The analysis of testing results with ALGator shows, that RI algorithm is the fastest one among all four algorithms. On the other hand Ullmann algorithm performed the worst, while the performance of its improved versions were even comparable with RI algorithm in certain scenarios. By integrating the problem into ALGator we have presented its capabilities and proposed some improvements.

Diplomsko delo se ukvarja z učinkovitim iskanjem prodajno-nakupnih poti med trgovalnimi elementi na trgu (borzah), ki so finančno ugodne za trgovca. V ta namen predstavlja učinkovito podatkovno strukturo (graf) za hrambo podatkov o odnosih med trgovalnimi elementi in vrsto metod za iskanje po njej. Delo se začne z neinformiranim izčrpnim preiskovanjem, se dotakne mogočega informiranega iskanja in ugotovi dovolj dober način za tako zmanjšanje iskalnega prostora, da je mogoče izčrpno preverjanje vseh veljavnih poti. To doseže z uporabo algoritma za iskanje elementarnih ciklov v grafu. This thesis deals with efficient search of such chaining of trades on exchanges (stock markets), that are financially beneficial for the trader. I introduced efficient data structure (graph) for storage of data in form of relations between trading items and variety methods for search of beneficial trade paths on it. I started with uninformed exhaustive search, investigated possible informed searching methods and found a way to reduce search space so much that exhaustive evaluation of valid paths is possible. I achieved this with help of an algorithm for enumerating all elementary circuits in a graph.

Predstavili smo postopek izdelave dinamične spletne strani "Info točka". Spletna aplikacija je implementirana v Microsoftovem ogrodju ASP.NET s pomočjo programskega jezika C#. V diplomskem delu smo pregledno predstavili tehnologije jQuery, CSS in HTML. Opisali smo tudi Dijkstrov algoritem za iskanje najkrajše poti po podanem obteženem grafu. V praktičnem delu te diplomske naloge smo opisali razvoj in funkcionalnost spletne aplikacije "Info točka". Uporabnost aplikacije smo demonstrirali na objektu G2 Fakultete za elektrotehniko, računalništvo in informatiko, Univerze v Mariboru. Ta aplikacija omogoča prikazovanje informacij o izbranem objektu, omogoča pa tudi lažje orientiranje v objektu s pomočjo grafičnega prikazovanja najkrajše poti do želenega oziroma izbranega cilja. We presented the process of creating dynamic web page "Info Point". This web application is implemented in the Microsoft ASP.NET Framework, using C# programming language. In this thesis, we presented and explained all the tehnologies we used like jQuery, HTML and CSS. We also described the Dijkstra algorithm for searching the shortest path through a given weighted graph. In the practical part of this thesis, we described the developement and functionality of the web aplication "Info Point". We have demonstrated the usefullness of this application with floormaps from the G2 object of Faculty of Electrical Engineering and Computer Science, University of Maribor. This application allows you to display information about the rooms in the object, but also allows easier orientation in the object with the help of graphic displaying the shortest path to the desired or selected destination.

Diplomska naloga obravnava števila mavrične in krepke mavrične povezanosti v grafih. Na začetku predstavimo osnovne pojme teorije grafov, ki so potrebni za razumevanje nadaljne snovi. V nalogo so vključena števila mavričnih in krepkih mavričnih barvanj za nekatere dobro znane grafe. Vključena so tudi števila mavrične povezanosti s predpisanimi vrednostmi. Konec pa vključuje mavrično in krepko mavrično barvanje krepkega in leksiografskega produkta. This thesis focuses on the rainbow connection number and strong rainbow connection number in the graph. We start by presenting the basic concepts of graph theory needed to understand the thesis. The task included the rainbow connection number and strong rainbow connection number of some well known graphs. The rainbow connection number with the prescribed values are also included. At the end we study rainbow connection number and strong rainbow connection number on strong and lexicographic product.

Glavna tema diplomskega dela je obravnava skoraj medianskih grafov, koles in dvodelnih koles ter uporaba le-teh v vsakdanjem življenju. V prvem delu so opisane opredelitve osnovnih pojmov, kot so osnovne definicije grafov, polnih grafov, dvodelnih grafov, kock ter hiperkock. Sledi predstavitev osnovnih pojmov o skoraj medianskih grafih ter relaciji Θ in δ. V drugem delu so prikazane in opisane lastnosti koles in dvodelnih koles. V zadnjem delu pa se predstavljena teorija poveže z vsakodnevnim življenjem skozi slike obokov v različnih cerkvah po Sloveniji in po svetu. Ti oboki so predstavljeni v obliki grafov ter njihovih lastnosti. Končna ugotovitev kaže na to, da je teorija grafov področje matematike, ki ga lahko vsesplošno uporabljamo in srečujemo vsak dan. The main topic of this diploma work are almost-median graphs, wheels, bipartite wheels and how to use all that in our daily life. In the first part we describe definitions of basic concepts like basic definitions of graphs, full graphs, bipartite graphs, cubes and hypercubes.Then follows basics concepts about almost-median graphs and relations Θ and δ. In the following chapter we show and describe information about wheels and bipartite wheels. In the last chapter we join definitions with our daily life throught pictures of diferent churces in Slovenija and around the world. Vaults of churces are presented throught graphs and there definitions. We can conclude that theory of graphs is a part of mathematica that can be used every day and can make math closer to us.

Benzenoidni graf je končen povezan v ravnino vložen graf brez presečnih vozlišč, v katerem je vsako lice omejeno s pravilnim šestkotnikom z dolžino stranice ena. Benzenoidni graf G je elementaren, če vsaka povezava pripada nekemu 1-faktorju grafa G. Šestkotnik h elementarnega benzenoidnega grafa je reducibilen, če tudi po odstranitvi mejnih povezav in vozlišč tega šestkotnika, graf ostane elementaren benzenoidni graf. Karakteriziramo reducibilne šestkotnike elementarnega benzenoidnega grafa. Karakterizacija je osnova za algoritem, s katerim se ugotovi zaporedje reducibilnih šestkotnikov, ki dekompozirajo graf iz te družine, v času O(n2). Poleg tega je predstavljen algoritem, ki dekompozira elementarni benzenoidni graf z največ eno perikondenzirano komponento v linearnem času. A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-faktor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagon of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagon that decomposes a graph of this class in O(n2) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.

V uvodu bomo spoznali pojme, ki so bistveni za razumevanje diplomske naloge. Tako se bomo seznanili z definicijo števne množice, izvedeli nekaj o grafih in drevesih, spoznali metodi iskanja v neskončnih drevesih, predstavljena pa je tudi rekurzija oz. rekurzivna zveza. V poglavju Preštevanje racionalnih števil bomo spoznali načine, s katerimi lahko dokažemo števnost racionalnih števil. To so: osnovni zgled, Calkin - Wilfovo drevo, preštevanje racionalnih števil s pomočjo največjega skupnega delitelja ter s pomočjo razcepa na prafaktorje. In the beginning we will present the terms that are crucial for the understanding of this diploma thesis. We will present the definition of a countable set, explain graphs and trees and show two methods of searching within the infinite trees. We will also define recursion which is also called the recursive connection. In the chapter Counting the rationals we will show different proofs showing that rationals are countable. These are: the basic example, Calkin-Wilf tree, counting the rationals with the help of the greatest common divisor and with the help of splitting the numbers on primes.