Projekti / Programi
Sodobni in novi metrični koncepti v teoriji grafov
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.05 |
Naravoslovje |
Matematika |
Teorija grafov |
| Koda |
Veda |
Področje |
| P110 |
Naravoslovno-matematične vede |
Matematična logika, teorija množic, kombinatorika |
| Koda |
Veda |
Področje |
| 1.01 |
Naravoslovne vede |
Matematika |
metrična teorija grafov; najkrajše poti; metrične dimenzije; delne kocke; orientirani matroidi; konveksnost; pakirno kromatično število
Raziskovalci (20)
Organizacije (3)
Povzetek
Grafi tvorijo naraven matematični model za impresiven spekter problemov, ki segajo preko tako različnih področij, kot so biologija, računalništvo, operacijske raziskave in številna področja v družboslovju. V posebnem so grafi temeljni model v raziskavah kompleksnih omrežij in velikih podatkov, ki sta vroči temi v sodobni znanosti. V mnogih izmed teh raziskav predstavljajo razdalje in ustrezni metrični koncepti ključno informacijo, ki jo želimo izvedeti o obravnavanih omrežjih. Notranja metrična struktura grafov je torej kjučni razlog, da je metrična teorija grafov centralno področje teorije grafov. Glavni cilj projekta je slediti aktualnim trendom v metrični teoriji grafov ter hkrati biti korak spredaj s predlaganjem in raziskovanjem konceptov, ki bodo prinesli nova dognanja, modelirali aplikacije in začrtali nove smeri raziskovanja na področju.
Glavni cilj projekta je raziskovanje na naslednjih področjih metrične teorije grafov:
(1) Najkrajše poti in njihove uporabe. Krepko geodetsko število bomo raziskovali iz različnih zornih kotov, v posebnem bomo poskušali natančno določiti ali izboljšati najboljše dosedaj znane meje krepko geodetskega števila rešetkam podobnih grafov. Raziskovali bomo tudi problem splošne lege na grafih Sierpińskega in na pomembnih povezovalnih omrežjih kot so to hiperkocke, rešetke in njihovi podrazredi.
(2) Metrične dimenzije. Študirali bomo, kako struktura grafov vpliva na metrično, povezavno metrično in mešano metrično dimenzijo. Raziskovanje kritičnih grafov bo pomagalo pri razumevanju vpliva strukture na vrednosti dimenzij. Zanimalo nas bo, kako se povezavno metrična in mešana dimenzija vedeta na produktih grafov. Raziskovali bomo tudi izračunljivostne vidike obeh dimenzij. Študirali bomo delitveno dimenzijo in k-metrično antidimenzijo. V posebnem domnevamo, da je delitvena dimenzija korenskega produkta dveh grafov navzgor omejena z vsoto delitvenih dimenzij faktorskih grafov minus ena.
(3) Metrično definirani razredi grafov. Študirali bomo različne razrede, med njimi bo poudarek na komplementih kock, delnih kockah in natančnih razdaljnih grafih. Komplemente kock bomo uporabili za nadaljnje razumevanje strukture posplošenih Fibonaccijevih kock in sorodnih razredov. Uporabili bomo zvezo med orientiranimi matroidi in delnimi kockami, da bi odgovorili na nekatera odprta vprašanja o orientiranih matroidih ter po drugi strani analizirali posledice na delnih kockah. V posebnem se bomo osredotočili na že dolgo odprta vprašanja o t.i. kotih takih struktur in o njihovi povezavi s slavno Las Vergnasovo domnevo. Natančne razdaljne grafe nameravamo študirati v povsem splošnem kontekstu.
(4) Konveksnosti. V tem sklopu bo poudarek na cestninski konveksnosti, ki jo bomo raziskovali na splošnih grafih in jo tudi primerjali z drugimi konveksnostmi. Nadalje bomo raziskovali invariante, ki so že bile obravnavane za geodetsko konveksnost, na primer število konveksnosti.
(5) Izbrani nadaljnji metrični koncepti. V tem sklopu bomo raziskovali (i) pakirno kromatično število, v posebnem kritične grafe glede na to invariant in pakirno kromatično število subkubičnih grafov; (ii) strukturo Voronojevih diagramov v grafih, v posebnem bomo raziskovali nove aplikacije Voronojevih diagramov na ravninskih grafih; (iii) radijske k-označitve, kjer načrtujemo izboljšanje meja ali določitev točnih vrednosti za število radijske k-označitve za različne družine grafov; in (iv) razdaljno pogojene poizvedbe v grafih, kjer bomo iskali nove podatkovne strukture, ki upravljajo z razdaljno pogojenimi poizvedbami.
Pomen za razvoj znanosti
Projekt spada med temeljne raziskave s področja matematike. Problemi, ki si jih zastavljamo, so mednarodno pomembni, kar med drugim dokazuje naša bibliografija iz zadnjega obdobja, odmevnost naših rezultatov in bibliografija, ki je predstavljena v prijavi. Iz slednje izhaja tudi, da so obravnavani problemi osrednji v metrični teoriji grafov ter da imajo številne aplikacije v drugih znanostih, v posebnem v biologiji, računalništvu, kemiji in socioloških znanostih. Razen tega predlagamo številne nove ideje in koncepte, za katere pričakujemo, da bodo odprli nova raziskovalna polja na področju metrične teorije grafov. Načrtujemo, da bodo rezultati raziskovalnega projekta objavljeni v vodilnih mednarodnih revijah s področja diskretne matematike in predstavljeni na mednarodnih znanstvenih konferencah, delno tudi kot vabljena, plenarna predavanja. S tem bomo še okrepili mednarodno vlogo slovenske teorije grafov, v posebnem njeno vlogo na področju metrične teorije grafov.
Pomen za razvoj Slovenije
The project belongs to basic research in the area of mathematics. Problems on which we plan to work are internationally important, which can in particular be justified by our bibliography from the last period, by the (citation) impact of our results, and by the bibliography presented in the application. From the latter it is evident that the problems are central in the area of metric graph theory and at the same time have applications in other scientific fields, specifically in areas like biology, computer science, chemistry, and social sciences. Moreover, we propose several new ideas and concepts which are expected to open new research areas in the field of metric graph theory. The obtained results are planned to be published in leading journals from the area of discrete mathematics and will be presented at international scientific conferences, in part as invited, plenary lectures. In this way we will further increase the international role of the Slovenian graph theory school, in particular its role in metric graph theory.
Najpomembnejši znanstveni rezultati
Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Vmesno poročilo
