Spektralno prepoznavanje grafova i mreža
Spectral recognition of graphs and networks
Докторанд
Jovanović, Irena M.Ментор
Stanić, ZoranЧланови комисије
Cvetković, DragošJovanović, Boško
Метаподаци
Приказ свих података о дисертацијиСажетак
Spektralna teorija grafova je matematiˇcka teorija koja grafove prouˇcava pomo´cu
sopstvenih vrednosti i sopstvenih vektora matrica koje su im pridruˇzene. Posebno
interesantni problemi ovog istraˇzivaˇckog domena jesu problemi spektralnog prepoznavanja
grafova. Tu ubrajamo: karakterizaciju grafa sa zadatim spektrom, taˇcno
ili pribliˇzno konstruisanje grafa sa zadatim spektrom, sliˇcnost grafova i perturbacije
grafova. U disertaciji se u prvom redu razmatraju problemi sliˇcnosti grafova, gde se
razlika pravi u zavisnosti od toga da li su ili ne poredbeni grafovi istog reda.
Sliˇcnost grafova istog reda ustanovljava se izraˇcunavanjem spektralnih rastojanja,
dok se, kada je reˇc o grafovima razliˇcitog reda, izraˇcunavaju i upored¯uju
mere sliˇcnosti definisane za njihove ˇcvorove. Mere sliˇcnosti mogu i ne moraju da
budu spektralno zasnovane, a poredbeni grafovi su u tom sluˇcaju obiˇcno grafovi
sa velikim brojem ˇcvorova, pa se nazivaju mreˇzama. Disertacija sadrˇzi izvesne rezultate...
koji se odnose na Menhetn spektralno rastojanje grafova bazirano na matrici
susedstva, Laplasovoj matrici i nenegativnoj Laplasovoj matrici. Predloˇzena je nova
mera sliˇcnosti za ˇcvorove poredbenih mreˇza koja se zasniva na razlici funkcija generatrisa
za brojeve zatvorenih ˇsetnji u ovim ˇcvorovima. Brojevi zatvorenih ˇsetnji
izraˇcunavaju se, shodno novoj spektralnoj formuli, brojanjem razapinju´cih zatvorenih
ˇsetnji u grafletima odgovaraju´cih grafova.
Zapoˇceta je analiza spektralno-strukturalnih karakteristika digrafova u odnosu
na spektar matrica AAT , odnosno ATA, gde je A matrica susedstva razmatranog
digrafa. Generalizovan je pojam kospektralnosti, pa su u tom smislu dati neki
rezultati vezani za kospektralnost digrafova i multigrafova u odnosu na matricu
AAT i nenegativnu Laplasovu matricu, respektivno.
Spectral graph theory is a mathematical theory where graphs are considered by
means of the eigenvalues and the corresponding eigenvectors of the matrices that
are assigned to them. The spectral recognition problems are of particular interest.
Between them we can distinguish: characterizations of graphs with a given spectrum,
exact or approximate constructions of graphs with a given spectrum, similarity of
graphs and perturbations of graphs. In this dissertation we are primarily interested
for the similarity of graphs, where graphs with the same number of vertices and
graphs of different orders are considered.
Similarity of graphs of equal orders can be established by computation of the
spectral distances between them, while for graphs with different number of vertices
the measures of similarity are introduced. In that case, graphs under study are
usually very large and they are denoted as networks, while the measures of similarity
can be spectraly based. Some mathematical results on th...e Manhattan spectral
distance of graphs based on the adjacency matrix, Laplacian and signless Laplacian
matrix are given in this dissertation. A new measure of similarity for the vertices of
the networks under study is proposed. It is based on the difference of the generating
functions for the numbers of closed walks in the vertices of networks. These closed
walks are calculated according to the new spectral formula which enumerates the
numbers of spanning closed walks in the graphlets of the corresponding graphs.
The problem of the characterization of a digraph with respect to the spectrum
of AAT , apropos ATA, where A is the adjacency matrix of a digraph, is introduced.
The notion of cospectrality is generalized, and so the cospectrality between some
particular digraphs with respect to the matrix AAT and multigraphs with respect
to the signless Laplacian matrix is considered.