Spekter grafa in njegova uporabaHrvatin, Erik (Avtor) Kuzman, Boštjan (Mentor) spekter grafadrevesakrepko regularni grafienergija grafareševanje problemovmathematicsV 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.[E. Hrvatin]20192019-05-16 03:16:46Magistrsko delo/naloga107712UDK: 519.17(043.2)COBISS_ID: 12427593sl