- ŠIFRA PROJEKTA: J1-9110 (B)
- NASLOV PROJEKTA: Prehodnost v točkovno tranzitivnih grafih
- PROJEKTNA EKIPA: dr. Klavdija Kutnar/ dr. Krész Miklós (vodja za InnoRenew CoE), Michael David Burnard
- TRAJANJE: 1. 7. 2018 – 30. 06. 2021
- FTE: 0,1 FTE za InnoRenew CoE v 2020
- FINANCIRANJE: Javna agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
- SESTAVA PROJEKTNE SKUPINE
- PARTNER IN KOORDINATOR PROJEKTA: Univerza na Primorskem, Inštitut Andrej Marušič (Slovenija)
- PARTNERJI: InnoRenew CoE (Slovenija); Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije (Slovenija); Univerza v Ljubljani, Pedagoška fakulteta (Slovenija)
Teorija grafov je eno od najpomembnejših raziskovalnih področij v diskretni matematiki. Večinoma zato, ker grafi zagotavljajo optimalne modele različnih realnih situacij. Na V naravoslovnih in družbenih vedah na primer modelirajo odnose med družbami, podjetji itd. V računalništvu predstavljajo komunikacijske mreže, organiziranost podatkov, računalniških naprav in še veliko več. V statistični fiziki lahko grafi predstavljajo lokalne povezave med interakcijskimi deli sistema. In ne nazadnje, v matematiki jih zaradi naravne metrike uporabljamo v geometriji in topologiji kot tudi v teoriji skupin, posebej preko tako imenovanih Cayleyjevih grafov, ki nastajajo iz skupin. Pogosto ugotovimo, da so grafi, ki kažejo optimalno vedenje, zelo simetrične strukture, kar spada v veliko skupino avtomorfizmov.
Visoko simetrične strukture, obravnavane v tem projektu, so točkovno tranzitivni grafi s posebnim poudarkom na Cayleyjevih grafih, ki so jih naredili v 19. stoletju, da bi raziskali lastnosti skupin. V projektu je obravnavana prehodnost grafov s posebnim poudarkom na obstoju Hamiltonovih ciklov in poti.
Glavne dejavnosti InnoRenew CoE pri projektu
Razvoj in implementacija algoritmov za generiranje prehodnih grafov s podanimi lastnostmi ter algoritemski razvoj in implementacija za iskanje hamiltonskih poti in ciklov, zlasti v točkovno tranzitivnih grafih.
