Preskoči na vsebino Preskoči na navigacijo

Inštitut za matematiko, fiziko in mehaniko

Language:
RSS:
Navigacija

A mathematician is a device for turning coffee into theorems.

Paul Erdös
Nahajate se tu: Domov Raziskave in projekti Raziskovalni projekti J1-2452 - Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Akcije dokumenta

J1-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