Ханой графигі - Википедия - Hanoi graph

Ханой графигі

Жылы графтар теориясы және рекреациялық математика, Ханой графиктері болып табылады бағытталмаған графиктер оның шыңдары. мүмкін күйлерін білдіреді Ханой мұнарасы басқатырғыштар, және олардың шеттері күйлер арасындағы жұптық қозғалыстарды білдіреді.

Құрылыс

Сөзжұмбақ бекітілген мұнаралар жиынтығына мөлшерінің өсу ретімен орналастырылған әр түрлі көлемдегі дискілер жиынтығынан тұрады. дискілер қосулы мұнаралар белгіленеді .[1][2] Жұмбақтың әр күйі әр диск үшін бір мұнараны таңдау арқылы анықталады, сондықтан графикте бар төбелер.[2]

Сөзжұмбақтың қозғалыстарында бір мұнарадағы ең кішкентай диск не иесіз мұнараға, не ең кішкентай дискісі үлкен мұнараға ауыстырылады. Егер бар болса иесіз мұнаралар, рұқсат етілген қозғалыстар саны

ол максимумнан ауытқиды (қашан нөлге немесе бірге және нөлге дейін) (барлық дискілер бір мұнарада болған кезде және болып табылады ). Сондықтан градус Ханой графигіндегі шыңдар максимумнан ауытқиды минимумға дейін .Шеттердің жалпы саны[3]

Үшін (дискілер жоқ) басқатырғыштың бір күйі және графиктің бір шыңы бар , Ханой графигі ыдырауы мүмкін кіші Ханой графигінің көшірмелері , ең үлкен дискіні орналастырудың әрқайсысы үшін бір. Бұл көшірмелер бір-бірімен тек ең үлкен диск қозғалатын күйде ғана байланысады: бұл мұнарадағы жалғыз диск, ал басқа мұнара жоқ.[4]

Жалпы қасиеттері

Әр Ханой графигінде а Гамильтон циклі.[5]

Ханой графигі Бұл толық граф қосулы төбелер. Олардың құрамында толық графиктер, барлық үлкен Ханой графиктері бар кем дегенде талап етеді кез-келген түстер графикалық бояу. Олар дәл боялған болуы мүмкін әр дискі бар мұнаралардың индекстерін қосу арқылы және қосынды модулін қолдану арқылы түстер түс ретінде.[3]

Үш мұнара

Бастап жұмыс жасағаннан бері жақсы зерттелген Ханой графиктерінің ерекше жағдайы Скорер, Гранди және Смит (1944)[1][6] үш мұнаралы Ханой графиктерінің жағдайы, . Бұл графиктер бар 3n төбелер.Олар тиындық графиктер ( байланыс графиктері дискілерге ұқсайтын орналасуы бар, жазықтықтағы қабаттаспайтын блок дискілері) Сиерпинский үшбұрышы. Бұл келісімді құрудың бір әдісі - сандарын орналастыру Паскаль үшбұрышы а тармақтарында алты бұрышты тор, бірлік аралықпен және нөмірі тақ болатын әр нүктеге бірлік дискіні қойыңыз диаметрі осы графиктердің және Ханой мұнарасы басқатырғышының стандартты түріне дейінгі шешім ұзындығы (онда дискілер барлығы бір мұнарадан басталып, барлығы бір мұнараға ауысуы керек) .[2]

Үш мұнара

Сұрақ, Web Fundamentals.svgМатематикадағы шешілмеген мәселе:
Графиктердің диаметрі қандай? үшін ?
(математикадағы шешілмеген мәселелер)

Үшін , Ханой графиктерінің құрылымы онша жақсы түсінілмеген және бұл графиктердің диаметрі белгісіз.[2]Қашан және немесе қашан және , бұл графиктер жоспардан тыс.[5]

Әдебиеттер тізімі

  1. ^ а б Хинц, Андреас М .; Клавжар, Санди; Петр, Цирил (2018), «2.3 Ханой Графиктері», Ханой мұнарасы - мифтер мен математика (2-ші басылым), Чам: Биркхаузер, б. 120, дои:10.1007/978-3-319-73779-9, ISBN  978-3-319-73778-2, МЫРЗА  3791459
  2. ^ а б в г. Имрих, Уилфрид; Клавжар, Санди; Ралл, Дуглас Ф. (2008), «2.2 Ханой Графиктері», Графика теориясының тақырыптары: Графиктер және олардың декарттық өнімі, Уэллсли, MA: A K Peters, 13-15 б., ISBN  978-1-56881-429-2, МЫРЗА  2468851
  3. ^ а б Аретт, Даниэль; Дори, Сюзанна (2010 ж.), «Ханой графиктерін бояу және есептеу», Математика журналы, 83 (3): 200–209, дои:10.4169 / 002557010X494841, МЫРЗА  2668333
  4. ^ Стюарт, Ян (2003), «1 тарау: Арыстан, Лама және салат жапырақтары», Сіз мені қабылдаған тағы бір тамаша математика, Mineola, NY: Dover Publications, ISBN  0-486-43181-9, МЫРЗА  2046372
  5. ^ а б Хинц, Андреас М .; Париж, Даниэль (2002), «Ханой графиктерінің жоспарлылығы туралы», Mathematicae экспозициялары, 20 (3): 263–268, дои:10.1016 / S0723-0869 (02) 80023-8, МЫРЗА  1924112
  6. ^ Скорер, Р. С .; Грунди, П.М.; Смит, C. A. B. (1944 шілде), «Кейбір бинарлық ойындар», Математикалық газет, 28 (280): 96, дои:10.2307/3606393