Vlastite vrijednosti grafova i konstrukcija kospektralnih grafova

master's thesis

• Title (english): Graph eigenvalues and construction of cospectral graphs
• Author: Ivan Mihovilović
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Andrea Aglić Aljinović (član povjerenstva)
• Committee member: Domagoj Kovačević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-03, Croatia

Abstract

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.

Abstract (english)

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.

• Keywords: Graf; spektar matrice; matrica susjedstva; Laplaceova matrica; kospektralni grafovi; zamjena bridova
• Keywords (english): Graph; spectrum of a matrix; adjacency matrix; Laplacian matrix; cospectral graphs; edge switching
• Language: croatian
• URN:NBN: urn:nbn:hr:168:260077
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 21:34:50