Jelenlegi hely

Adattudomány, hálózatok és modellezés szeminárium

Félév: 
2018/19 II.félév
Helyszín: 
Árpád tér 2. II. em. 220. sz.
Dátum: 
2019-04-25
Időpont: 
14:00-15:00
Előadó: 
Bogdan Zavalnij (Rényi Intézet)
Cím: 
A gráfokkal való modellezés erősségéről
Absztrakt: 

A matematika egyik (tudománytörténeti) vívmánya, hogy a világ bonyolult dolgait tudja a saját eszközeivel hatékonyan modellezni. Előadásunk egy ilyen modellt próbál bemutatni, nevezetesen a gráfokkal való modellezést. Bemutatunk és részletezünk néhány problémát, amely hatékonyan megfogalmazható mint gráfprobléma, és ahol a megoldást a gráf egy maximális vagy k-klikkje szolgáltatja.

A bevezető példák után bemutatunk több átfogalmazást, ahol a gráfok színezése vezethető vissza klikk keresésre. Ezen példákhoz hasonlóan bemutatjuk, ahogy a hipergráfok esetén is alkalmazhatóak ezek a
technikák, és összevetjük a lehetséges megoldásokat. Bemutatjuk, hogy az elemzett technikák segítségével hogy lehet megoldani bonyolult, nyitott kérdéseket.

Annak céljából, hogy bemutassuk a gráf-átfogalmazások valóban sokrétű erősségét meg egy speciális esetet mutatunk be. A gráfszínezések LP átfogalmazásánál ismert módszer van arra, hogy bizonyos
szimmetriatöréseket is meg lehessen az LP egyenlőtlenségekben fogalmazni. Megmutatjuk, hogy ezen szimmetriatörések a gráfátfogalmazásokban is lehetségesek. Az így kapott gráfok meglepő
tulajdonsággal bírnak: bár nagyobb gráfokról van szó, mégis könnyebb a bennük a k-klikk feladat megoldása.