Gráfok sajátértékei

Abstract

A dolgozat második fejezetében összefoglaljuk azon lineáris algebrai és gráfelméleti alapfogalmakat, melyekre a dolgozat folyamán szükségünk lesz. A harmadik fejezetben bevezetjük az egyszerű gráfok sajátértékeinek fogalmát, majd meghatározzuk nevezetes gráfok sajátértékeit, továbbá vizsgáljuk a gráfok sajátértékeinek tulajdonságait. Külön foglalkozunk a karakterisztikus polinom együtthatóinak gráfelméleti jelentéseivel és a reguláris gráfok sajátértékeivel. Végül az utolsó fejezetben megadunk néhány alkalmazást, például a sajátértékek segítségével adunk becsléseket a kromatikus számra, meghatározzuk a feszítőfák számát, és bebizonyítjuk a barátságtételt.