Projekti / Programi
Barvanja, dekompozicije in pokritja 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 |
barvanje grafa, pretok, dekompozicija, pokritje, faktor, T-spoj
Raziskovalci (22)
Organizacije (2)
Povzetek
Po skromnih začetkih pred skoraj 300 leti je v zadnjega pol stoletja področje teorije grafov doživelo velikanski skok naprej in postalo eno izmed glavnih področij sodobnih raziskav v matematiki. Na krilih uporabnosti rezultatov v tehnologiji, se področje raziskovanja nenehno širi, dosežki zadnjih let pa so nam dali zakladnico rezultatov, metod, idej in problemov. V zadnjih desetletjih je imela slovenska šola teorije grafov pomembno vlogo pri razvoju te matematične discipline na svetovni ravni do te mere, da je njena mednarodna prepoznavnost dandanes primerljiva s šolami tehnološko najbolj razvitih držav po svetu.
Naš predlog projekta je usmerjen na določene vidike kromatične teorije grafov. Eden izmed osnovnih problemov v matematiki je razdelitev množice objektov na razrede tako, da upoštevamo določena pravila. Pri kromatični teoriji grafov želimo diskretni objekt razdeliti na enostavnejše podobjekte. Če so določena pravila enostavna, to še ne pomeni, da bo enostavno tudi reševanje z njimi povezanih problemov, ravno obratno! V okviru predlaganih raziskav se bomo osredotočili na dve moderni in obetajoči raziskovalni temi s področij barvanj povezav in pokritij grafov.
Prva (oziroma druga) tema preučuje možnosti za zagotavljanje parnostne regularnosti (oziroma lokalne iregularnosti) na grafih preko barvanj njihovih povezav. Zanimanje za prvo od omenjenih tem izhaja iz starejšega rezultata (iz leta 1978), ki podaja povezavo med nikjer-ničelnimi pretoki in pokritji po povezavah sodih podgrafov. Ta del projekta predstavlja nadaljevanje že začetega dela na lihih barvanjih povezav (oziroma lihih pokritij) grafov, kot tudi njegove posplošitve, imenovane vozliščno parnostno barvanje (pokritje) povezav.
Začetek raziskovanja druge teme sega v leto $1986$ in je povezano s konceptom, znanim pod imenom iregularna moč grafa. To področje je bilo v zadnjih 15 letih predmet velikega zanimanja, kar se kaže tudi v treh znanih domnevah: Domnevi 1-2-3 (2004), Domnevi o detekciji (2005) in Domnevi o lokalni iregularnosti (2015).
Domneve se (po vrstnem redu) nanašajo na najmanjše število barv, ki jih potrebujemo za razlikovanje glede na vsoto barv v soseščini vozlišč oziroma za razlikovanje glede na multimnožico barv v soseščini vozlišč oziroma lokalno iregularno barvanje povezav danega obarljivega grafa. Zaenkrat kaže, da trenutno znanje ne zadošča za rešitev teh domnev v celoti, zato nameravamo proučevati določene posebne vidike teh domnev na zoženih družinah grafov.
Čeprav ne izgleda, da med omenjenimi barvanji obstaja očitna povezava, je bil rezultat o vozliščno-parnostnem barvanju povezav uporabljen za dokaz trenutno najboljše zgornje meje o (lokalno) iregularnem kromatičnem indeksu grafa. Načrtujemo bolj sistematično raziskavo nakazanih povezav, da bi jih našli še več. Navadno raziskovanje različic problemov barvanja pripomore k napredku reševanja originalnega problema. V ta namen se bomo v tretjem delu projekta osredotočili na študijo seznamskih različic in različic pokritij, povezanih z zgoraj omenjenimi barvanji.
Pomen za razvoj znanosti
Teorija grafov je moderna veja matematike, ki se je znatno razširila v zadnjem stoletju po zaslugi velikega napredka tehnologije in je široko uporabna na mnogih znanstvenih področjih kot so algoritmi v računalništvu, modeliranje molekul v kemiji, modeliranje komunikacijskih omrežij ter v študiju kompleksnih omrežij. Kromatična teorija grafov, katere razvoj se je začel v letu 1852 s slavnim Problemom štirih barv, je dandanes osrednje in najbolj obsežno področje teorije grafov. V okviru projekta bomo obravnavali probleme s področja barvanj grafov, ki so tesno povezani s teorijo pretokov, dekompozicij in sorodnih tematik, ki so trenutno vroče teme raziskovanja v moderni teoriji grafov. Z objavami v znanstvenih revijah najvišjega ranga, predstavitvami rezultatov na mednarodnih konferencah ter v sklopu seminarjev raziskovalnih skupin v tujini, bomo problematiko približali širšemu krogu raziskovalcev. Naši že objavljeni rezultati kažejo, da je področje zanimivo tudi za druge
skupine, saj so članki, pa čeprav nedavni, že solidno citirani.
Pomen za razvoj Slovenije
Graph theory is a modern branch of mathematics, which has expanded significantly during the last century due to the enormous progress of technology, and it is widely applied in many diverse sciences such as algorithms in computer science, modeling molecules in chemistry, modeling communication networks, and studying complex networks. The chromatic graph theory, with its origins starting in 1852, is nowadays central and major part of graph theory. In the scope of the project, we will consider problems from chromatic graph theory which are closely related with the flow theory, graph decompositions and related thematics, which are currently hot topics in modern graph theory. By publishing our results in the scientific journal of the highest rank, presentations on international conferences and on seminars of foreign research groups, we will introduce the problematics to wider set of researchers. Our already published results show that these types of problems are interesting for various groups of researchers as our papers, yet recent, have already obtained a considerable number of citations.
Najpomembnejši znanstveni rezultati
Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
