Spektar grafa

završni rad

• Naslov (engleski): Graph Spectrum
• Autor: Ivana Jarni
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Marina Furkes (član povjerenstva)
• Član povjerenstva: Filip Martinović (č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: 2022-07-08, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Graf je struktura defirnirana konačnim skupom vrhova i skupom bridova. Neka svojstva grafa usko su vezana uz njegov spektar, skup svojstvenih vrijednosti matrice susjedstva grafa. U ovom je radu dan pregled osnovnih rezultata o svojstvenim vrijednostima grafa i njihovim primjenama.
Najviše svojstava grafa vezano je s najvećom, drugom po redu najvećom i najmanjom svojstvenom vrijednosti, te brojem različitih svojstvenih vrijednosti grafa. Na primjer, najveća svojstvena vrijednost se smanjuje uklanjanjem vrhova ili bridova iz grafa, dok druga po redu najveća svojstvena vrijednost daje informacije o algebarskoj povezanosti grafa, a grafovi s malim brojem svojstvenih vrijednosti često imaju svojstvo simetričnosti.
Problemi razmotreni u ovom radu koji iziskuju modeliranje pomoću grafova su klasteriranje, odnosno grupiranje podataka u svrhu podjele prema nekom kriteriju sličnosti, raspoznavanje uzoraka koje je usko povezano s klasteriranjem i modeliranje kompleksnih mreža, čija primjena je česta u mrežnom prometu. Konačno, izrađena je interaktivna aplikacija za računanje spektra grafa.

Sažetak (engleski)

A graph is a structure defined by a finite set of vertices and a set of edges. Some graph properties are closely related to its spectrum, a set of eigenvalues of the adjacency matrix. This thesis provides an overview of the basic results on the eigenvalues of graphs and their applications.
Most graph properties are related to the largest, second largest and smallest eigenvalues, and the number of different eigenvalues of the graph. For example, the largest eigenvalue is reduced by removing vertices or edges from the graph, while the second largest eigenvalue provides information about the algebraic connectivity of the graph, and graphs with a small number of eigenvalues often have the property of symmetry.
Problems discussed in this thesis that require modeling using graphs are clustering, ie. grouping data for the purpose of division according to some similarity criteria, pattern recognition that is closely related to clustering and modeling complex networks, whose application is common in network transport. Finally, an interactive application for calculating the graph spectrum was developed.

• Ključne riječi: spektar grafa; svojstvene vrijednosti; matrica susjedstva; karakteristični polinom
• Ključne riječi (engleski): graph spectrum; eigenvalues; adjacency matrix; characteristic polynomial
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:999909
• 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-01-15 10:23:53