Geometrijske tehnike za traženje pseudo-klika u grafu

master's thesis

• Title (english): Geometric techniques for finding pseudo-cliques in a graph
• Author: Ana Carević
• Mentor: Pavle Goldstein (mentor)
• Committee member: Pavle Goldstein (predsjednik povjerenstva)
• Committee member: Zoran Vondraček (član povjerenstva)
• Committee member: Goran Muić (član povjerenstva)
• Committee member: Snježana Lubura Strunjak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2024-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: maksimalna klika; euklidski prostor; graf
• Language: croatian
• URN:NBN: urn:nbn:hr:217:759855
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Embargoed access; Embargo expiration date: 2024-09-13
• Created on: 2024-03-13 07:54:40