Dekompozicije potpunog grafa u trokutove

undergraduate thesis

• Title (english): Complete graph decompositions in triangles
• Author: Martina Majdiš
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Josip Žubrinić (član povjerenstva)
• Committee member: Vlatko Crnković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-08-31, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problemima dekompozicije grafova bave se mnogi matematičari već dugi niz godina. Dekompozicije grafova korisne su računarstvo, ali i brojna druga područja. Za dekompoziciju potpunih grafova u trokute točno se zna kako dobiti valjanu dekompoziciju, a u ovom radu ne bavimo se samo takvim konstrukcijama nego i algoritamskim pristupom tom problemu. Da bismo ga mogli jasnije objasniti i algoritme koji su korišteni za njegovo rješavanje, objašnjene su i dekompozicije općenito te Steinerov sustav trojki. Uspoređujemo vrijeme potrebno pojedinom algoritmu za rješavanje dekompozicije i vizualno prikazujemo rezultate.

Abstract (english)

Graph decomposition problems have been studied by many mathematicians over a long period of time. These decompositions are useful to us in computer science and various other fields. For the decomposition of complete graphs into triangles, we know how to obtain a valid decomposition. However, in this paper, we will not only consider such constructions but also take an algorithmic approach to the problem. In order to explain this problem and algorithms used to solve it in a more clear manner, decompositions in general along with Steiner triple systems will be further explained. This will be compared through the time required for each algorithm to solve the decomposition and finally we will visually present the results.

• Keywords: Steinerov sustav trojki; potpuni graf; dekompozicija; algoritmi; iscrpna pretraga
• Keywords (english): Steiner triple system; complete graph; decomposition; algorithms; brute-force search
• Language: croatian
• URN:NBN: urn:nbn:hr:168:380104
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-10-11 09:37:44