| Popis: |
Glavni cilj ovog diplomskog rada bio je iznijeti kratki pregled osnovnih pojmova teorije grafova te detaljno proučiti Smithov teorem koji tvrdi da su jedini grafovi spektralnog radijusa strogo manjeg od 2 upravo Dynkinovi dijagrami tipa A, D i E. U prva dva poglavlja iznijeli smo osnovne pojmove i rezultate teorije grafova s naglaskom na spektralnu teoriju grafova. U radu smo promatrali jednostavne, konačne i povezane grafove. U trećem poglavlju uveli smo pojam ireducibilne matrice i uspostavili vezu između povezanih grafova i njihovih ireducibilnih matrica susjedstava. Nadalje, iskazali smo Perron-Frobeniusov teorem koji, uz određene pretpostavke, tvrdi da ireducibilna matrica ima jedinstvenu pozitivnu realnu svojstvenu vrijednost s pridruženim pozitivnim svojstvenim vekorom. Definirali smo i proučavali ujednačene particije, Rayleighov kvocijent te ispreplitanje kako bismo došli do Smithovog teorema. U četvrtom poglavlju, glavni rezultat je Smithov teorem koji predstavlja grafove čija je najveća svojstvena vrijednost manja ili jednaka 2. U petom poglavlju, definirali smo sisteme korijena pridružene konačnodimenzionalnim prostim kompleksnim Liejevim algebrama i proučili njihovu prezentaciju pomoću Dynkinovih dijagrama. Potom smo prezentirali klasifikaciju spomenutih sistema korijena. Na kraju smo uočili povezanost Dynkinovih dijagrama tipa A, D i E s dijagramima iz Smithovog teorema. The main goal of this thesis was to give a brief overview of the basic notions of graph theory and to study in detail Smith’s theorem which states that the only graphs of spectral radius strictly less than 2 are Dynkin diagrams of type A, D and E. In the first two chapters, we presented the basic notions and results of graph theory with the emphasis on the spectral graph theory. In the thesis we considered a simple, finite and connected graphs. In the third chapter, we introduced the notion of an irreducible matrix and established a connection between the connected graphs and their irreducible adjacency matrices. Furthermore, we presented the Perron-Frobenius theorem which, under certain assumptions, states that the irreducible matrix possesses a unique positive real eigenvalue with positive corresponding eigenvector. We introduced and studied equitable partitions, the Rayleigh quotient and interlacing in order to establish Smith’s theorem. In the fourth chapter, the main result is Smith’s theorem which classifies all graphs whose maximum eigenvalue is less than or equal to 2. In the fifth chapter, we defined root systems associated with the finitedimensional simple complex Lie algebras and studied their presentation given by Dynkin diagrams. We then presented the classification of the aforementioned root systems. Finally, we demonstrated the correspondence between the Dynkin diagrams of type A, D and E and the diagrams from Smith’s theorem. |
