prikaz prve stranice dokumenta Geometrijske tehnike za traženje pseudo-klika u grafu
Embargo period 2024-09-13
master's thesis
Geometrijske tehnike za traženje pseudo-klika u grafu
Zagreb: University of Zagreb, Faculty of Science, 2024. urn:nbn:hr:217:759855
Carević, Ana
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Carević, A. (2024). Geometrijske tehnike za traženje pseudo-klika u grafu (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević, Ana. "Geometrijske tehnike za traženje pseudo-klika u grafu." Master's thesis, University of Zagreb, Faculty of Science, 2024. https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević, Ana. "Geometrijske tehnike za traženje pseudo-klika u grafu." Master's thesis, University of Zagreb, Faculty of Science, 2024. https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević, A. (2024). 'Geometrijske tehnike za traženje pseudo-klika u grafu', Master's thesis, University of Zagreb, Faculty of Science, accessed 24 August 2024, https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević A. Geometrijske tehnike za traženje pseudo-klika u grafu [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2024 [cited 2024 August 24] Available at: https://urn.nsk.hr/urn:nbn:hr:217:759855

A. Carević, "Geometrijske tehnike za traženje pseudo-klika u grafu", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2024. Available at: https://urn.nsk.hr/urn:nbn:hr:217:759855

Metadata
TitleGeometrijske tehnike za traženje pseudo-klika u grafu
Title (english)Geometric techniques for finding pseudo-cliques in a graph
AuthorAna Carević
MentorPavle Goldstein (mentor)
Committee memberPavle Goldstein (predsjednik povjerenstva)
Committee memberZoran Vondraček (član povjerenstva)
Committee memberGoran Muić (član povjerenstva)
Committee memberSnježana Lubura Strunjak (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2024-02-28, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U ovom diplomskom radu bavili smo se problemom pronalaženja klika u grafovima. Implementirani algoritam rješava problem korištenjem geometrijskog pristupa. Ideja algoritma je bila sortirati udaljenosti vrhova grafa od neke određene točke iz koje iščitamo kliku, a njezinom maksimizacijom dobijemo traženu maksimalnu kliku u grafu. Na početku smo naveli pojmove koje koristimo u radu, a zatim smo na skupu vrhova grafa definirali metriku te smo izometrički uložili graf u euklidski prostor. Naš algoritam smo proveli na 17 primjera uz različite veličine grafova, različite vjerojatnosti bridova i različite veličine klika. Za sve generirane primjere algoritam je uspješno pronašao klike, iako veličine klika nisu bile znatno veće od očekivanih.
Abstract (english)
This thesis is concerned with finding cliques in graphs. We present a solution to this problem by developing a geometric approach. Given a graph \(G=(V,E) \), we construct a finite metric space \( (X,d) \) and consider an isometric embedding of \(X\) into \(\mathbb{E}^n\). Using the properties of the embedded object, we construct a suitable order on \(V\), that enables us to find large cliques efficiently, and these can easily be extended to either maximal cliques or pseudo-cliques. After introducing the necessary mathematical objects and notions, we give a detailed description of our method. We test our algorithm on 17 random matrices of various sizes and properties. The largest maximal clique has been successfully detected in each case, although its size was only slightly larger than expected.
Keywords
Languagecroatian
URN:NBNurn:nbn:hr:217:759855
Study programmeTitle: Mathematical Statistics
Study programme type: university
Study level: graduate
Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
Type of resourceText
File originBorn digital
Access conditionsEmbargoed access
Embargo expiration date: 2024-09-13
Terms of useLicence In copyright icon
Created on2024-03-13 07:54:40