prikaz prve stranice dokumenta Geometrijske tehnike za traženje pseudo-klika u grafu
  Preuzmi
PDF 237.05 KB
diplomski rad
Geometrijske tehnike za traženje pseudo-klika u grafu
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2024. urn:nbn:hr:217:759855
Carević, Ana
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Carević, A. (2024). Geometrijske tehnike za traženje pseudo-klika u grafu (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević, Ana. "Geometrijske tehnike za traženje pseudo-klika u grafu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2024. https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević, Ana. "Geometrijske tehnike za traženje pseudo-klika u grafu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2024. https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević, A. (2024). 'Geometrijske tehnike za traženje pseudo-klika u grafu', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 23.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:759855

Carević A. Geometrijske tehnike za traženje pseudo-klika u grafu [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2024 [pristupljeno 23.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:759855

A. Carević, "Geometrijske tehnike za traženje pseudo-klika u grafu", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2024. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:759855

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:759855
Podaci o radu
NaslovGeometrijske tehnike za traženje pseudo-klika u grafu
Naslov (engleski)Geometric techniques for finding pseudo-cliques in a graph
AutorAna Carević
MentorPavle Goldstein (mentor)
Član povjerenstvaPavle Goldstein (predsjednik povjerenstva)
Član povjerenstvaZoran Vondraček (član povjerenstva)
Član povjerenstvaGoran Muić (član povjerenstva)
Član povjerenstvaSnježana Lubura Strunjak (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2024-02-28, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Jezikhrvatski
URN:NBNurn:nbn:hr:217:759855
Studijski programNaziv: Matematička statistika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Datum isteka embarga: 2024-09-13
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2024-03-13 07:54:40