Jako regularni grafovi

diplomski rad

• Autor: Luka Crnoja
• Mentor: Vedran Krčadinac (mentor)
• Član povjerenstva: Vedran Krčadinac (predsjednik povjerenstva)
• Član povjerenstva: Ozren Perše (član povjerenstva)
• Član povjerenstva: Boris Širola (član povjerenstva)
• Član povjerenstva: Maja Resman (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2018-11-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Tema ovog diplomskog rada su jako regularni grafovi. Diplomski rad je podijeljen u četiri poglavlja i dodatak. U prvom poglavlju cilj je upoznati se s definicijom jako regularnog grafa i osnovnim uvjetima koji vrijede za svaki jako regularan graf. Dani su primjeri nekih jako regularnih grafova i njihovi parametri. Slike grafova prate sadržaj prvog poglavlja. U drugom poglavlju proučavamo spektar jako regularnih grafova. Nalazimo formulu za kratnosti njegovih svojstvenih vrijednosti, koje moraju biti nenegativni cijeli brojevi. Ovaj rezultat se naziva uvjet cjelobrojnosti i daje nam snažan kriterij za nepostojanje jako regularnog grafa. U trećem poglavlju otkrivamo dva sljedeća kriterija za egzistenciju jako regularnih grafova: apsolutnu među i Kreinove uvjete. U četvrtom poglavlju koristimo sve prethodno dobivene rezultate o jako regularnim grafovima. Cilj je napraviti tablicu dopustivih parametara \((v,k,\lambda,\mu)\) koji zadovoljavaju nužne uvjete iz prvog poglavlja i uvjet cjelobrojnosti. Uspoređujemo našu tablicu s Brouwerovom tablicom jako regularnih grafova i nalazimo da ona sadrži točno iste parametre za \(v \leq 50\). Također su dane informacije o egzistenciji i broju jako regularnih grafova. Dodatak sadrži kod napisan u programskom paketu Maxima koji smo koristili za izradu tablice dopustivih parametara jako regularnih grafova.

Sažetak (engleski)

The topic of this thesis are strongly regular graphs. The thesis is divided into four sections and an appendix. In the first section, the goal is to get acquainted with the definition of a strongly regular graph and the basic conditions that apply. We give examples of some strongly regular graphs and their parameters. Pictures of the graphs accompany the contents of the first section. In the second section we study the spectrum of strongly regular graphs. We find formulae for the multiplicity of their eigenvalues, which must be integers. This result is referred to as the integrality condition, and provides a powerful non-existence criterion for strongly regular graphs. In the third section two further existence criteria for strongly regular graphs are presented: the absolute bound and the Krein conditions. In the fourth section all of the previous results about strongly regular graphs are put to use. The goal is to make a table of admissible parameters \((v,k,\lambda,\mu)\) satisfying the necessary conditions from the first section and the integrality condition. We compare our table with A. E. Brouwer’s table of strongly regular graphs, and find that it contains exactly the same parameters for \(v \leq 50\). Information about the existence and the number of strongly regular graphs is also given. The appendix contains code in the computer algebra system Maxima we used to make the table of admissible parameters of strongly regular graphs.

• Ključne riječi: jako regularni grafovi; uvjet cjelobrojnosti; apsolutna međa; Kreinovi uvjeti; Brouwerova tablica; Maxima
• Ključne riječi (engleski): strongly regular graphs; integrality condition; absolute bound; Krein conditions; Brouwer’s table; Maxima
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:008421
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-03-26 12:57:18