Гиперкуб теориясындағы «қораптағы жылан» мәселесі – графтардағы ең ұзын жол табу. Бұл жол бұрыштар арқылы өтеді, ал бұрынғы бұрыштар қолданысқа жарамсыз деп белгіленеді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Граф теориясы мен компьютерлік ғылымдағы қораптағы жылан мәселесі гиперкубтың қабырғалары бойынша белгілі бір жолды табумен айналысады. Бұл жол бір төбеден басталып, қабырғалары арқылы мүмкіндігінше көп төбелерге жетеді. Жаңа төбеге жеткеннен кейін, бұрынғы төбе және оның барлық көршілері пайдалануға жарамсыз деп белгіленуі керек. Жол ешқашан пайдалануға жарамсыз деп белгіленген төбеге бармауы тиіс. Басқаша айтқанда, жылан – гиперкубтағы байланысты ашық жол, онда әрбір түйін жолмен байланысқан, бас (бастау) және құйрық (аяқтау) ерекшеліктерінен басқа, оның жылан ішіндегі дәл екі көршісі бар. Басы мен құйрығының әрқайсысы жылан ішінде тек бір көршіге ие. Жыланды құру ережесі – гиперкубтағы түйінге, егер ол ағымдағы түйінмен байланысқан болса және ол қазіргі түйіннен басқа, бұрын барылған жылан түйінінің көршісі болмаса, кіруге болады. Граф теориясы терминологиясында, бұл гиперкубтағы ең ұзын индукцияланған жолды табу деп аталады; оны индукцияланған кішіграф изоморфизмі мәселесінің ерекше жағдайы ретінде қарастыруға болады. Гиперкубтардағы ұзын индукцияланған циклдарды табуға қатысты ұқсас мәселе бар, ол қораптағы орам мәселесі деп аталады. Қораптағы жылан мәселесі алғаш рет , қателерді түзету кодтары теориясының ықпалымен сипатталды. Жылан немесе орам мәселесіне шешімдердің төбелері бір биттік қателерді анықтай алатын сұр код ретінде қолданылуы мүмкін. Мұндай кодтар электр инженериясында, кодтау теориясында және компьютерлік желілер топологиясында қолданылады. Бұл қолданыстарда гиперкубтың берілген өлшемі үшін мүмкіндігінше ұзын кодты жасау маңызды. Код неғұрлым ұзын болса, оның мүмкіндіктері соғұрлым тиімді болады. Ең ұзын жыланды немесе орамды табу өлшем саны артқан сайын едәуір қиынға соғады және іздеу кеңістігі ауыр комбинаторлық жарылысқа ұшырайды. Қораптағы жылан мәселесі үшін жоғарғы және төменгі шекараларды анықтауға арналған кейбір әдістерге дискретті математика мен граф теориясын қолдана отырып дәлелдеу, іздеу кеңістігін толық іздеу және эволюциялық техникаларды пайдалана отырып эвристикалық іздеу жатады.
The snake in the box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner which has been marked unusable. In other words, a snake is a connected open path in the hypercube where each node connected with path, with the exception of the head (start) and the tail (finish), it has exactly two neighbors that are also in the snake. The head and the tail each have only one neighbor in the snake. The rule for generating a snake is that a node in the hypercube may be visited if it is connected to the current node and it is not a neighbor of any previously visited node in the snake, other than the current node. In graph theory terminology, this is called finding the longest possible induced path in a hypercube; it can be viewed as a special case of the induced subgraph isomorphism problem. There is a similar problem of finding long induced cycles in hypercubes, called the coil in the box problem. The snake in the box problem was first described by , motivated by the theory of error correcting codes. The vertices of a solution to the snake or coil in the box problems can be used as a Gray code that can detect single bit errors. Such codes have applications in electrical engineering, coding theory, and computer network topologies. In these applications, it is important to devise as long a code as is possible for a given dimension of hypercube. The longer the code, the more effective are its capabilities. Finding the longest snake or coil becomes notoriously difficult as the dimension number increases and the search space suffers a serious combinatorial explosion. Some techniques for determining the upper and lower bounds for the snake in the box problem include proofs using discrete mathematics and graph theory, exhaustive search of the search space, and heuristic search utilizing evolutionary techniques.