A létra és az n-prizma gráfok optimális murvázási száma Fizika, Földtudományok és Matematika

31 OTDK, Fizika, Földtudományok és Matematika Szekció, Diszkrét matematika Tagozat.

A létra és az n-prizma gráfok optimális murvázási száma

Hallgató: Papp László
Szak: Matematikus mesterképzési szak, Képzés típusa: msc, Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem, Kar: Természettudományi Kar

Témavazető: Dr. Katona Gyula Y. - docens, Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar

Algebrai és számelméleti problémák megoldása során mint bizonyítási módszert vezették be a kövezési feladatot. Később megfogalmazták a feladatot gráfelméleti nyelven is. A gráfelméleti interpretáció felvetett sok érdekes új kérédst, így a kövezési témakör saját területté nőtte ki magát a gráfelméleten belül.

A gráfok kövezése tekinthető egy játékként, melyben a gráf csúcsaira köveket teszünk, majd azokat a következő szabály szerint mozgatjuk: Egy csúcsra akkor helyezhetünk fel egy követ, ha valamelyik szomszédjáról leveszünk két követ. Ennek általánosítása a murvázás. Ekkor nem követeljük meg, hogy a két kő amit leveszünk azonos csúcson legyen.

Kövek egy kezdeti elosztását megoldhatónak nevezzük ha abból kiindulva murvázási lépések sorozatával bármelyik csúcsra követ tudunk juttatni. A legkisebb megoldható elosztás mérete az optimális murvázási szám.

Dolgozatomban gráfok optimális murvázási számait határozom meg. Két féle gráfot vizsgálok elsősorban. Ez a két gráf típus a létra és az n-prizma kerék. Mind a két gráf család elemei kisebb gráfok direktszorzataként állnak elő. A létra egy tetszőleges hosszúságú út és a két csúcsú teljes gráf direkt szorzata. Az n-prizma a létrától annyiban tér el, hogy az út helyett kör szerepel a direkt szorzatban. Ezen gráfok optimális kövezési számát már korábban meghatározták, azonban az optimális murvázási számuk eddig ismeretlen volt.

A létrára vonatkozó eredményeket végtelen leszállással igazolom. A bizonyítás során felhasználok több a területen használatos eszközt, például a kövezési súlyösszeget. Eredményként azt kapom, hogy a 2n csúcsú létra optimális murvázási száma két-harmad n körül mozog, a pontos érték n 3-mal való osztási maradékától függ.

Az n-prizmára vonatkozó formulák bizonyítása során a létrákra vonatkozó eredményeimből indulok ki majd a 2-optimális murvázási számokra való kitéréssel érek célt. Technikai lemmaként meghatározom a körök 2-optimális murvázási számának értékét is, melyre azt kapom, hogy pontosan a kör hossza.

Az n-prizma optimális murvázási számára tömör, a kör hosszának hárommal vett osztási maradékától függő formulát adok. Végül igazolom, hogy az n hosszú úgynevezett Möbius-létra gráfnak egy eset kivételével megegyezik az optimális murvázási száma az n-prizmájéval.