Xanoy grafigi - Hanoi graph

Xanoy grafigi ${ displaystyle H_ {3} ^ {7}}$

Yilda grafik nazariyasi va rekreatsiya matematikasi, Xanoy grafikalari bor yo'naltirilmagan grafikalar uning tepaliklari mumkin bo'lgan holatlarni ifodalaydi Xanoy minorasi jumboq, va uning qirralari davlatlar juftligi o'rtasida ruxsat etilgan harakatlarni ifodalaydi.

Qurilish

Jumboq turli xil o'lchamdagi disklar to'plamidan iborat bo'lib, ular belgilangan minoralar to'plamiga kattalashib borayotgan tartibda joylashtirilgan. ${ displaystyle n}$ disklar yoqilgan ${ displaystyle k}$ minoralar belgilanadi ${ displaystyle H_ {k} ^ {n}}$.^[1][2] Jumboqning har bir holati har bir disk uchun bitta minorani tanlash bilan belgilanadi, shuning uchun grafigi bor ${ displaystyle k ^ {n}}$ tepaliklar.^[2]

Jumboqning harakatlarida bitta minoradagi eng kichik disk yoki egasiz minoraga yoki eng kichik diski kattaroq minoraga ko'chiriladi. Agar mavjud bo'lsa ${ displaystyle u}$ egasiz minoralar, ruxsat etilgan harakatlarning soni

${ displaystyle { binom {k} {2}} - { binom {u} {2}},}$

bu maksimaldan o'zgarib turadi ${ displaystyle { tbinom {k} {2}}}$(qachon ${ displaystyle u}$ nol yoki bitta va ${ displaystyle { tbinom {u} {2}}}$ nolga teng) ${ displaystyle k-1}$ (barcha disklar bitta minora ustida bo'lganda va ${ displaystyle u}$ bu ${ displaystyle k-1}$). Shuning uchun daraja Xanoy grafigidagi tepaliklarning maksimal darajasi ${ displaystyle { tbinom {k} {2}}}$ kamida ${ displaystyle k-1}$.Qirralarning umumiy soni^[3]

${ displaystyle { frac {1} {2}} { binom {k} {2}} { bigl (} k ^ {n} - (k-2) ^ {n} { bigr)}.}$

Uchun ${ displaystyle k = 0}$ (disklar yo'q) jumboqning bitta holati va grafikning bitta tepasi mavjud ${ displaystyle k> 0}$, Xanoy grafigi ${ displaystyle H_ {k} ^ {n}}$ parchalanishi mumkin ${ displaystyle k}$ kichikroq Xanoy grafikasining nusxalari ${ displaystyle H_ {k} ^ {n-1}}$, eng katta diskning har bir joylashuvi uchun bittadan. Ushbu nusxalar bir-biriga faqat eng katta disk harakatlanishi mumkin bo'lgan holatlarda bog'langan: bu uning minorasidagi yagona disk va boshqa minorada bo'sh joy mavjud emas.^[4]

Umumiy xususiyatlar

Har bir Xanoy grafasida a Gamilton tsikli.^[5]

Xanoy grafigi ${ displaystyle H_ {k} ^ {1}}$ a to'liq grafik kuni ${ displaystyle k}$ tepaliklar. Ularda to'liq grafikalar, barcha katta Xanoy grafikalari mavjud ${ displaystyle H_ {k} ^ {n}}$ hech bo'lmaganda talab qilish ${ displaystyle k}$ har qanday rang grafik rang berish. Ular aniq rangga ega bo'lishi mumkin ${ displaystyle k}$ har bir diskni o'z ichiga olgan minoralar indekslarini yig'ish va yig'indisi modulidan foydalanib ranglar ${ displaystyle k}$ rang sifatida.^[3]

Uchta minora

Xanoy grafikalarining ma'lum bir ishi, chunki u ishlaganidan beri yaxshi o'rganilgan Skorer, Gruni va Smit (1944)^[1][6] uchta minorali Xanoy grafikalari misolida, ${ displaystyle H_ {3} ^ {n}}$. Ushbu grafikalar mavjud 3ⁿ tepaliklar.Ular tinga grafikalar (the aloqa grafikalari o'xshash bo'lgan disklar joylashuvi bilan, tekislikdagi bir-biriga to'g'ri kelmaydigan birlik disklari) Sierpinski uchburchagi. Ushbu tartibni tuzishning usullaridan biri bu raqamlarni tartibga solishdir Paskal uchburchagi a nuqtalari bo'yicha olti burchakli panjara, birlik oralig'i bilan va raqamlari g'alati bo'lgan har bir nuqtaga birlik disk qo'ying diametri ushbu grafiklardan va Xanoy minorasi jumboqining standart shakliga echimning uzunligi (unda disklar hammasi bitta minoradan boshlanadi va barchasi boshqa minoraga o'tishi kerak) ${ displaystyle 2 ^ {n} -1}$.^[2]

Uchdan ortiq minoralar

Matematikada hal qilinmagan muammo: Grafiklarning diametri qanday? ${ displaystyle H_ {k} ^ {n}}$ uchun ${ displaystyle k> 3}$? (matematikada ko'proq hal qilinmagan muammolar)

Uchun ${ displaystyle k> 3}$, Xanoy grafikalarining tuzilishi u qadar yaxshi tushunilmagan va bu grafikalarning diametri noma'lum.^[2]Qachon ${ displaystyle k> 4}$ va ${ displaystyle n> 0}$ yoki qachon ${ displaystyle k = 4}$ va ${ displaystyle n> 2}$, bu grafikalar rejadan tashqari.^[5]

Adabiyotlar