Dekompozicije potpunog grafa u trokutove

završni rad

• Naslov (engleski): Complete graph decompositions in triangles
• Autor: Martina Majdiš
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Josip Žubrinić (član povjerenstva)
• Član povjerenstva: Vlatko Crnković (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-08-31, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: Steinerov sustav trojki; potpuni graf; dekompozicija; algoritmi; iscrpna pretraga
• Ključne riječi (engleski): Steiner triple system; complete graph; decomposition; algorithms; brute-force search
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:380104
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 09:37:44