Jurij Kovic: Predstavitev grafov in hipergrafov s polinomi
Datum objave: 25. 10. 2009
Seminar za diskretno matematiko
Torek, 27. 10. 2009, od 10h do 12h, Plemljev seminar, Jadranska 19
Predstavitev grafov in hipergrafov s polinomi
Temo bomo obravnavali najprej teoreticno, nato pa se aplikativno.
I. TEORIJA
Prvi del bo posvecen vprasanju moznosti vpeljave bijektivne korespondence
med grafi in hipergrafi ter polinomi v vec spremenljivkah:
1. Dotaknili se bomo zgodovine tega vprasanja.
2. Grafom in hipergrafom bomo priredili polinome v vec spremenljivkah.
3. Iskanje obratne transformacije - ki bi polinomom v vec spremenljivkah
priredila grafe oziroma hipergrafe - nas bo pripeljalo do razlicnih
razsiritev pojma hipergrafa.
Drugi del bo namenjen samim hipergrafom in njihovim razsiritvam.
1. Na kratko bomo predstavili pomen hipergrafov v teoriji grafov.
2. Podali bomo preprostejso pojmovno interpretacijo hipergrafov.
3. Na tej podlagi bomo vpeljali preprostejso graficno ponazoritev
hipergrafov.
V tretjem delu bomo ugotavljali, kako se bijektivna korespondenca med
grafi oziroma hipergrafi in polinomi odraza na operacijah in
transformacijah nad njimi.
1. Nekaj osnovnih operacij nad grafi (disjunktna unija, produkt,
kartezicni produkt) bomo predstavili z ustreznimi operacijami nad
njihovimi polinomi.
2. Videli bomo, kako lahko s preprostimi transformacijami polinomov
opisemo razlicne spremembe v grafih oziroma hipergrafih.
3. S pomocjo osnovnih operacij nad polinomi (produkt, paricialni odvodi)
bomo definirali nekaj novih operacij nad grafi in hipergrafi.
II. APLIKACIJA
V cetrtem delu bomo omenili mozne prakticne aplikacije predstavitve grafov
oziroma hipergrafov s polinomi.
1. Pokazali bomo, kako lahko grafe in hipergrafe uporabimo kot matematicni
model situacij, v katerih posamezniki sodelujejo v projektih, posvecenih
skupnemu cilju.
2. Videli bomo, kako lahko polinom grafa oziroma hipergrafa uporabimo za
oceno stopnje usklajenosti delovanja taksnega sistema, in posledicno za
izboljsanje te usklajenosti.
3. Videli bomo, kako lahko eno od vpeljanih razsiritev hipergrafov (ki
vodi tudi do posplositev pojma mnozic in multimnozic) uporabimo kot
matematicni model konfliktnih situacij, v katerih si lahko cilji
posameznih skupin, ki sodelujejo v razlicnih projektih, nasprotujejo.
