Search

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. 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.

Spektralna teorija grafova je grana matematike koja je nastala pedesetih godina pro²log veka i od tada se neprestano razvija. Njen zna£aj ogleda se u brojnim primenama, naro£ito u hemiji, zici, ra£unarstvu i drugim naukama. Grane matematike, kao ²to su linearna algebra i, posebno, teorija matrica imaju vaºnu ulogu u spektralnoj teoriji grafova. Postoje razli£ite matri£ne reprezentacije grafa. Najvi ²e su izu£avane matrica susedstva grafa i Laplasova (P.S. Laplace) matrica, a zatim i Zajdelova (J.J. Seidel) i takozvana nenegativna Laplasova matrica. Spektralna teorija grafova u su²tini uspostavlja vezu izme u strukturalnih osobina grafa i algebarskih osobina njegove matrice, odnosno razmatra o kojim se strukturalnim osobinama (kao ²to su povezanost, bipartitnost, regularnost i druge) mogu dobiti informacije na osnovu nekih svojstava sopstvenih vrednosti njegove matrice. Veliki broj dosada²njih rezultata iz ovog ²irokog polja istraºivanja moºe se na¢i u slede¢im monograjama: [20], [21], [23] i [58]. Disertacija sadrºi originalne rezultate dobijene u nekoliko podoblasti spektralne teorije grafova. Ti rezultati izloºeni su u tri celine glave, od kojih je svaka podeljena na poglavlja, a neka od njih na potpoglavlja. Na po£etku svake glave, u posebnom poglavlju, formulisan je problem koji se u toj glavi razmatra, kao i postoje¢i rezultati koji se odnose na zadati problem, a neophodni su za dalja razmatranja. U ostalim poglavljima predstavljeni su originalni rezultati, koji se nalaze i u radovima [3], [4], [47], [48], [49], [50], [51] i [52]. U prvoj glavi razmatra se druga sopstvena vrednost regularnih grafova. Postoji dosta rezultata o grafovima £ija je druga po veli£ini sopstvena vrednost ograni£ena odozgo nekom (relativno malom) konstantom. Posebno, druga sopstvena vrednost ima zna£ajnu ulogu u odre ivanju strukture regularnih grafova. Poznata je karakterizacija regularnih grafova koji imaju samo jednu pozitivnu sopstvenu vrednost (videti [20]), a razmatrani su i regularni grafovi sa osobinom 2 ≤ 1 (videti [64]). U okviru ove disertacije pro²iruju se rezultati koji se nalaze u radu [64], a predstavljaju se i neki op²ti rezultati koji se odnose na vezu odre enih spektralnih i strukturalnih osobina regularnih nebipartitnih grafova bez trouglova... Spectral graph theory is a branch of mathematics that emerged more than sixty years ago, and since then has been continuously developing. Its importance is reected in many interesting and remarkable applications, esspecially in chemistry, physics, computer sciences and other. Other areas of mathematics, like linear algebra and matrix theory have an important role in spectral graph theory. There are many dierent matrix representations of a given graph. The ones that have been studied the most are the adjacency matrix and the Laplace matrix, but also the Seidel matrix and the so-called signless Laplace matrix. Basically, the spectral graph theory establishes the connection between some structrural properties of a graph and the algebraic properties of its matrix, and considers structural properties that can be described using the properties of the eigenvalues of its matrix. Systematized former results from this vast eld of algebraic graph theory can be found in the following monographs: [20], [21], [23] i [58]. This thesis contains original results obtained in several subelds of the spectral graph theory. Those results are presented within three chapters. Each chapter is divided into sections, and some sections into subsections. At the beginning of each chapter (in an appropriate sections), we formulate the problem considered within it, and present the existing results related to this problem, that are necessary for further considerations. All other sections contain only original results. Those results can also be found in the following papers: [3], [4], [47], [48], [49], [50], [51] and [52]. In the rst chapter we consider the second largest eigenvalue of a regular graph. There are many results concerning graphs whose second largest eigenvalue is upper bounded by some (relatively small) constant. The second largest eigenvalue plays an important role in determining the structure of regular graphs. There is a known characterization of regular graphs with only one positive eigenvalue (see [20]), and regular graphs with the property 2 ≤ 1 have also been considered (see [64]). Within this thesis we extend the results given in [64], and we also present some general results concerning the relations between some structural and spectral properties of regular triangle-free graphs...