Co-funded by:
Mentored by:

Prehodnost v točkovno tranzitivnih grafih

Opis projekta

 

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.

Bibliografski kazalci