Spekter grafa in njegova uporaba : magistrsko delo

Hrvatin, Erik (author), Kuzman, Boštjan (mentor)

V magistrskem delu obravnavamo pojem spektra grafa, ki predstavlja eno od orodij za proučevanje kombinatorične strukture grafov in ga lahko uporabimo pri reševanju raznovrstnih problemov, od izrazito teoretičnih do takšnih z možnostjo uporabe v drugih znanstvenih vedah. Spekter grafa definiramo kot množico lastnih vrednosti neke pripadajoče sosednostne matrike. V delu določimo spektre nekaterih standardnih družin grafov (polni grafi, prazni grafi, polni dvodelni grafi, grafi zvezde, cikli, poti,...). Med drugim ugotovimo, da so prazni grafi edini grafi, ki imajo eno samo lastno vrednost, da imajo polni grafi natanko dve različni lastni vrednosti, lastne vrednosti dvodelnih grafov pa so vedno simetrične. Obravnavamo tudi različne lastnosti lastnih vrednosti grafa, predvsem največje, katere velikost omejimo glede na števili vozlišč in povezav grafa. V nadaljevanju se osredotočimo na drevesa, ki so definirana kot povezani grafi brez ciklov. Drevesa oziroma gozdove določenega reda uredimo glede na njihovo gostost s pomočjo Lovász-Pelikanove relacije preko lastnosti karakterističnih polinomov. V razdelku o krepko regularnih grafih dokažemo, da so to natanko grafi s tremi različnimi lastnimi vrednostmi, nato pa z uporabo lastnosti spektra krepko regularnih grafov predstavimo klasifikacijo Mooreovih grafov premera 2. Srečamo se tudi z Izrekom o prijateljstvih, ki ob preoblikovanju v vsakdanje življenje pravi: če v skupini ljudi velja, da imata poljubna dva človeka natanko enega skupnega prijatelja, potem v tej skupini obstaja človek, ki je prijatelj z vsemi ljudmi iz skupine, ter ta izrek tudi dokažemo. V zadnjem razdelku obravnavamo še energijo grafa, ki je definirana kot vsota absolutnih vrednosti lastnih vrednosti grafa. Pri tem določimo energijo nekaterih standardnih družin grafov, preverimo kakšne so zgornje meje za vrednost energije in kdaj so te meje dejansko tudi dosežene. Grafom, ki dosežejo zgornjo mejo za vrednost energije, pravimo grafi z maksimalno energijo. V delu predstavimo rezultate Koolena in Moultona, da so takšni povezani grafi natanko polni grafi in krepko regularni grafi.

• Language: Slovenian
• Keywords: spekter grafa, drevesa, krepko regularni grafi, energija grafa, reševanje problemov, mathematics
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Publisher: [E. Hrvatin]
• Year: 2019
• Number of pages: 68 str.
• PID: 20.500.12556/RUL-107712
• UDC: 519.17(043.2)
• COBISS.SI-ID: 12427593
• Publication date in RUL: 16.05.2019

Secondary language

• Language: English
• Title: Graph spectrum and its applications

Abstract

In my thesis I deal with the notion of the graph spectrum that represents one of the tools for examining combinatorial structure of graph and can be used for solving different problems, including theoretical ones and those with applications in other sciences. The spectrum of a graph is defined as the set of graph eigenvalues, which are obtained as eigenvalues of a corresponding adjacency matrix. In the thesis spectra of some standard graph families is computed (complete graphs, empty graphs, complete bipartite graphs, star graphs, cycles, paths,...). Among other results we see that empty graphs are the only ones with a single eigenvalue, that complete graphs have exactly two distinct eigenvalues and that the eigenvalues of bipartite graphs are always symmetric. A discussion of diverse properties of graph eigenvalues follows, where the focus is on the properties of the largest eigenvalue, which is bounded by the numbers of graph vertices and edges. Later the emphasis is on trees, that is, connected graphs without cycles. Trees and forests of specific order are partially ordered according to their density by the Lovász-Pelikan relation. In the section on strongly regular graphs it is proved that these are exactly the graphs with three distinct eigenvalues. Then the classification of Moore graphs with diameter 2 is presented by the use of strongly regular graphs' properties. This is followed by proof of the Friendship theorem, which translated into the everyday life, goes: if it's true that in a group of people any two random persons have exactly one common friend, then there is a person in this group who is everybody's friend. In the final section we define graph energy as a sum of absolute values of the graph eigenvalues. The energy of some standard graph families is discussed, as well as the upper bounds for the energy values. The graphs that attain the upper bound for the energy value are called the maximum energy graphs. We present result of Koolen and Moulton that such connected graphs are exactly complete graphs and strongly regular graphs.

• Keywords: graph, algebra, graf, matematika