|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Blázsik Zoltán: Gráfok rekonstruálhatósága a pontos távolsággráfok alapján |
|
|||
|
|
||||
|
||||
Egy $G(V,E)$ gráf esetén a $G^{(k)}$ gráf jelölje a $G$ pontos $k$-távolság gráfját, aminek csúcshalmaza megegyezik $V$-vel, és két csúcsot pontosan akkor köt össze él $G^{(k)}$-ban, ha $G$-ben a távolságuk pontosan $k$ volt (a csúcsok címkézettek). Az előadásban vizsgálandó kérdést a következő játék formájában vezetném be: Alice gondol egy egyszerű gráfra, és Bob feladata a gráf rekonstruálása, amihez csupán $k\ge 2$ pozitív egészekre a $G^{(k)}$ pontos $k$-távolságok gráfok egy általa választott részét használhatja. A rekonstruáláshoz Bobnak lehetősége van elkérnie Alicetól bizonyos $k$ értékekre a gondolt gráf pontos $k$-távolság gráfjait. Az első kérdés az, hogy egyáltalán biztos-e, hogy Bob ki tudja találni a gondolt gráfot. Látjuk majd, hogy ha a gondolt gráf nem feltétlenül összefüggő, akkor nem feltétlenül tudja kitalálni. Ha Alicenak összefüggő gráfra kell gondolnia, akkor igazolható, hogy Bob mindig ki tudja találni a gráfot. (HF) Megmutatjuk, hogy a triviális kitalálhatóságnál jóval több is igazolható, mindig elég csupán konstans sok $k$-ra elkérni a $G^{(k)}$ gráfokat. Sőt igazolni fogjuk, hogy az eredményünk éles is! Az eredmények Horváth Csongorral és Zsigri Bálinttal közösek. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013
