Title
Spektralno prepoznavanje grafova i mreža
Creator
Jovanović, Irena M. 1981-
Copyright date
2014
Object Links
Select license
Autorstvo-Nekomercijalno-Bez prerade 3.0 Srbija (CC BY-NC-ND 3.0)
License description
Dozvoljavate samo preuzimanje i distribuciju dela, ako/dok se pravilno naznačava ime autora, bez ikakvih promena dela i bez prava komercijalnog korišćenja dela. Ova licenca je najstroža CC licenca. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/deed.sr_LATN. Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Theses Type
Doktorska disertacija
description
Datum odbrane: 2014
Other responsibilities
mentor
Stanić, Zoran. 1975-
član komisije
Cvetković, Dragoš, 1941-
član komisije
Jovanović, Boško, 1946-
Academic Expertise
Prirodno-matematičke nauke
Academic Title
-
University
Univerzitet u Beogradu
Faculty
Matematički fakultet
Alternative title
Spectral recognition of graphs and networks.
Publisher
[I. Jovanović]
Format
IX, 155 listova
description
teorija grafova-spektralna teorija grafova / graph theory-spectral graph theory
Abstract (sr)
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.
Abstract (en)
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 the 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.
Authors Key words
graf, digraf, spektar, spektralno rastojanje, zatvorena ˇsetnja, razapinju
´ca zatvorena ˇsetnja, graflet, kospektralnost, funkcija generatrisa
Authors Key words
graph, digraph, spectrum, spectral distance, closed walk, spanning
closed walk, graphlet, cospectrality, generating function
Type
Tekst
Abstract (sr)
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.
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.