Mooreovi grafi in posplošeni večkotnikiLavš, Luka (Avtor) Vidali, Janoš (Mentor) Mooreovi grafiMooreova mejaproblem stopnje in premeraHoffman-Singletonov grafposplošeni večkotnikigeometrija ranga 2V diplomskem delu preučujemo Mooreove grafe, ki pri dani maksimalni stopnji in premeru dosegajo teoretično zgornjo mejo za število vozlišč. Analiziramo njihove strukturne lastnosti, ki nam kasneje služijo pri analizi njihovega obstoja. Eksplicitno konstruiramo trivialne Mooreove grafe, nakar dokažemo enoličnost Hoffman-Singletonovega grafa, ki je skupaj s Petersenovim grafom, eden od dveh znanih netrivialnih Mooreovih grafov. Navedemo podrobno klasifikacijo vseh Mooreovih grafov, pri čemer v edinem nezajetem primeru, Aschbacherjevem grafu valence 57, pokažemo, da ta, če obstaja, ni razdaljno tranzitiven. V nadaljevanju obrnemo perspektivo in utemeljimo, da Mooreova meja predstavlja tudi spodnjo mejo za število vozlišč pri grafih z vnaprej določeno stopnjo in ožino. Izostritev te meje nato usmeri pozornost na dvodelne Mooreove grafe, ki naravno sovpadajo z regularnimi posplošenimi večkotniki. Analiziramo njihove konstrukcije, pri čemer se srečamo s projektivnimi ravninami, ortogonalnimi, simplektičnimi in Titsovimi posplošenimi štirikotniki ter klasičnimi posplošenimi šestkotniki. Z znanimi konstrukcijami in klasifikacijo regularnih posplošenih večkotnikov zaključimo nalogo, pri kateri smo od togega ekstremalnega problema v teoriji grafov prešli v bogato geometrijo ranga 2.20262026-09-05 08:15:07Delo diplomskega seminarja/zaključno seminarsko delo/naloga186767sl