If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is.
John Louis von NeumannJ1-2452 - Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Vodja projekta: prof. dr. Bojan Mohar.
Temeljni znanstveno-raziskovalni projekt.
Vodja projekta: prof. dr. Bojan Mohar.
Naslov projekta: Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Šifra projekta: J1-2452
Veda: Naravoslovno matematične vede
Trajanje projekta: 01. 09. 2020 - 31. 08. 2023.
Cenovna kategorija: C
Letni obseg projekta: 1,4 FTE
Sodelujoči organizaciji:
1554 - Univerza v Ljubljani, Fakulteta za matematiko in fiziko
2547 - Univerza v Mariboru, Fakulteta za naravoslovje in matematiko
Projekt sofinancira: Javna agencija Republike Slovenije za raziskovalno dejavnost.
Vsebinski opis projekta:
Grafovske modele je moč najti vsepovsod in naraščajoča popularnost raziskav v teoriji grafov je presegla staro prepričanje, da so grafi zgolj matematične diskretne strukture. Gradnja modelov z uporabo zelo velikih grafov se uporablja v najrazličnejšihpodročjih znanosti in tehnike. Klasična teorija grafov obdeluje majhne grafe in njihove lastnosti, a druga področja znanosti dandanes potrebujejo razvoj orodij za delo z zelo velikimi grafi, neskončnimi grafi, slučajnimi grafi in še bolj kompleksnimi objekti,kot so neskončne družine grafov ali grafovske limite. Tako topološka kot geometrijska teorija grafov se ukvarjata s problemi v takšnih družinah objektov, raziskujeta njihovo strukturo in uporabo v teoretičnih in praktičnih problemih optimizacije, algoritmovin podatkovnih struktur.
V sklopu projekta se bomo ukvarjali s strukturnimi, optimizacijskimi in algoritmičnimi problemi v geometrijskih in topoloških predstavitvah grafov. V prvem delovnem paketu bomo raziskovali strukturo predstavitev končnih grafov, ki jih lahko razumemo bodisikot topološke bodisi kot geometrijske strukture. Nadaljevali bomo naše raziskave o strukturi prekrižno kritičnih grafov, širini vložitev grafov in triangulacij v ploskvah. V drugem delovnem paketu bomo obravnavali teorijo limit optimalnih (oz. lokalno optimalnih)grafovskih risb v zvezi z različnimi modeli slučajnih risb grafov. Z razvito strukturno teorijo limit grafovskih risb si obetamo alternativen pogled na asimptotično (morda celo eksaktno) verzijo domneve Harary-Hill-Guy iz leta 1963 in/ali domneve Turan-Zarankiewicziz leta 1954. S povezavo z geometrijskimi risbami grafov si obetamo napredek v razumevanju Sylvestrovega problema o štirih točkah iz leta 1865. Tretji delovni paket se bo ukvarjal z uporabo strukturnih rezultatov prvih dveh delovnih paketov pri modeliranjuin razvoju algoritmov. Kot primer konkretnih povezav navedemo uporabo grafovskih razdalj v problemih usmerjanja tokov, uporabo geometrijskih presečnih grafov pri problemih premikanja agentov in analize slik, limitni grafovski objekti pa se povezujejo s Hebbovimučenjem, psihološkimi modeli optimalne izkušnje in učenjem nevronskih mrež.
Med orodji, ki jih bomo uporabljali pri delu na projektu, naj naštejemo Erdősevo verjetnostno metodo, Robertsonovo in Seymourjevo teorijo strukture grafov s prepovedanim minorjem, Szemerédijevo lemo o regularnosti in novejšo teorijo grafovskih limit, ki joje prvenstveno razvil L. Lovász. Omenjene rezultate bomo prepletli s strukturnimi rezultati grafovskih vložitev in grafovskih risb, ki smo jih razvili sodelavci projekta in njihovi soavtorji (mostovi v grafih, teorija tlakovcev, šiv grafov, specialne podatkovnestrukture za predstavitve geometrijskih grafov). V okviru projekta bomo združili znanja projektne skupine in širili meje znanja na teh grafovskih raziskovalnih problemih.
Sestava projektne skupine: povezava na SICRIS
Bibliografske reference: povezava na SICRIS