Problem traženja najveće klike u grafu

završni rad

• Naslov (engleski): Maximal Clique Problem
• Autor: Ante Spajić
• Mentor: Tomislav Burić (mentor)
• Član povjerenstva: Tomislav Burić (predsjednik povjerenstva)
• Član povjerenstva: Anamari Nakić (član povjerenstva)
• Član povjerenstva: Ana Anušić (č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: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Kroz ovaj završni rad obrađuje se problem pronalaska najveće klike u grafu. Prvo se upoznaje s područjem teorije grafova, samim pojmom grafa i pojmovima usko povezanim s njime, kako bi se omogućilo razumijevanje konteksta problema. Nakon toga, obrađuje se pojam klike, algoritmi pronalaženja različitih vrsta klika, te neke zanimljive značajke tih algoritama. Na kraju dolazi analiza trenutno najpoznatijeg rješenja zadanog problema, Bron-Kerbosch algoritma, i njegova implementacija u programskom jeziku Java u obliku konzolne aplikacije i aplikacije za radnu površinu. Rad sadrži i detaljna uputstva za korištenje obje aplikacije, te primjere izvođenja.

Sažetak (engleski)

In this thesis the problem of finding the maximum clique in a graph is explained. Firstly, we get familiar with the area of graph theory, the concept of the graph and concepts and terms closely related to it, in order to better understand the context of the problem. Next, the thesis deals with the concept and the definition of a clique, algorithms used for finding different kinds of cliques and also some of the interesting characteristics of the formerly mentioned algorithms. In the end, we consider the most used algorithm for the set problem, Bron-Kerbosch algorithm, and it’s implementation in the Java programming language in the form of a console and a desktop application. The thesis contains detailed manual for the use of both applications, as well as some examples of their execution.

• Ključne riječi: klike; Bron-Kerbosch; teorija grafova; potpuna klika; najveća klika
• Ključne riječi (engleski): clique; Bron-Kerbosch; graph theory; maximum clique; maximal clique
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:680823
• 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: 2019-03-14 00:51:40