Vlastite vrijednosti grafova i konstrukcija kospektralnih grafova

diplomski rad

• Naslov (engleski): Graph eigenvalues and construction of cospectral graphs
• Autor: Ivan Mihovilović
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Andrea Aglić Aljinović (član povjerenstva)
• Član povjerenstva: Domagoj Kovačević (č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: 2024-07-03, Hrvatska

Sažetak

Graf je uređeni par G = (V, E) konačnog nepraznog skupa vrhova V i konačnog skupa E dvočlanih podskupova od V koje zovemo bridovi. Matematički pojam grafa zanimljiv je jer predstavlja prirodni apstraktni model mreža koje se pojavljuju u raznim granama inženjerstva. Proučavanjem svojstava grafa možemo donijeti zaključke o značajkama mreže koju predstavlja. U ovom radu zadatak je proučiti vlastite vrijednosti matrica pridruženih grafu. Skup svih vlastitih vrijednosti grafa G naziva se spektar grafa. Proučit će se osnovni rezultati i pojmovi vezani uz spektar grafa. Predstavit će se veze između vlastitih vrijednosti grafa i raznovrsnih svojstava grafa. Opisat će se algoritam za računanje vlastitih vrijednosti. Računalno će se implementirati metoda za konstrukciju kospektralnih grafova, onih koji imaju iste vlastite vrijednosti. Dobiveni grafovi će se analizirati i opisati. Predstavit će se razne primjene spektra grafa na rješavanje problema u inženjerstvu koji se modeliraju pomoću grafova.

Sažetak (engleski)

A graph is an ordered pair G = (V, E) of a finite nonempty set of vertices V and a finite set E of 2-subsets of V, which we call edges. The mathematical concept of a graph is interesting because it represents a natural abstract model of networks which appear in various branches of engineering. By studying the properties of a graph, we can draw conclusions about the features of the network it represents. In this thesis, the task is to study the eigenvalues of matrices associated with the graph. The set of all eigenvalues of a graph G is called the spectrum of the graph. Basic results and terms related to the graph spectrum will be studied. Connections between graph eigenvalues and various graph properties will be presented. The algorithm for calculating eigenvalues will be described. A method for the construction of cospectral graphs, those that have the same eigenvalues, will be computer implemented. The resulting graphs will be analyzed and described. Various applications of the spectrum of graphs to solve engineering problems modeled by graphs will be presented.

• Ključne riječi: Graf; spektar matrice; matrica susjedstva; Laplaceova matrica; kospektralni grafovi; zamjena bridova
• Ključne riječi (engleski): Graph; spectrum of a matrix; adjacency matrix; Laplacian matrix; cospectral graphs; edge switching
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:260077
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2024-10-12 21:34:50