Spektar grafa

undergraduate thesis

• Title (english): Graph Spectrum
• Author: Ivana Jarni
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Marina Furkes (član povjerenstva)
• Committee member: Filip Martinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: spektar grafa; svojstvene vrijednosti; matrica susjedstva; karakteristični polinom
• Keywords (english): graph spectrum; eigenvalues; adjacency matrix; characteristic polynomial
• Language: croatian
• URN:NBN: urn:nbn:hr:168:999909
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-15 10:23:53