Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтағы жол, әрбір төбеге дәл бір рет кіретін, Гамильтондық жолдардың сипаттамасы.
Path in a graph that visits each vertex exactly once
the nature of Hamiltonian paths
Графтар теориясының математикалық саласында, Гамильтондық жол (немесе іздеме жол) – бұл бағытталмаған немесе бағытталған графтың ішіндегі әрбір төбеге дәл бір рет кіретін жол. Гамильтондық цикл (немесе Гамильтондық схема) – әрбір төбеге дәл бір рет кіретін цикл. Жақын орналасқан төбелерден басталып, аяқталатын Гамильтондық жолға бір қанатын қосып Гамильтондық цикл жасауға болады, ал Гамильтондық циклден кез келген қанатын алып тастау арқылы Гамильтондық жол құруға болады. Мұндай жолдар мен циклдардың графтарда бар-жоғын анықтау есептері NP-толық; толық мәліметтер үшін Гамильтондық жол мәселесін қараңыз. Гамильтондық жолдар мен циклдар Уильям Роуэн Гамильтонның құрметіне аталған, ол икозиандық ойынды ойлап тапқан, ол қазір Гамильтонның жұмбағы деп те аталады, және бұл ойын додекаэдрдің қабырғалық графында Гамильтондық циклді табуға байланысты. Гамильтон бұл мәселені икозиандық есептеу арқылы шешкен, бұл алгебралық құрылым біртұтас түбірлерге негізделген және кватерниондармен (сонымен қатар Гамильтонның өзі ойлап тапқан) көптеген ұқсастықтары бар. Бұл шешім кездейсоқ графтарға қолданылмайды. Гамильтонның есімімен аталғанына қарамастан, полиэдрдегі Гамильтондық циклдарды бір жыл бұрын Томас Киркман зерттеген, ол әсіресе Гамильтондық циклдары жоқ полиэдрдің мысалын келтірген. Одан да ертерек, шахмат тақтасындағы аттың графындағы Гамильтондық циклдар мен жолдар, яғни аттың саяхаты, 9-шы ғасырда Үнді математигі Рудрата және шамамен сол кездегі Ислам математигі әл-Адли ар-Румимен зерттелген. 18-шы ғасырдағы Еуропада аттың саяхаты туралы еңбектерді Абрахам де Муавр және Леонард Эйлер жариялаған.
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP complete; see Hamiltonian path problem for details. Hamiltonian paths and cycles are named after William Rowan Hamilton, who invented the icosian game, now also known as Hamilton's puzzle, which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the icosian calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). This solution does not generalize to arbitrary graphs. Despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by Thomas Kirkman, who, in particular, gave an example of a polyhedron without Hamiltonian cycles. Even earlier, Hamiltonian cycles and paths in the knight's graph of the chessboard, the knight's tour, had been studied in the 9th century in Indian mathematics by Rudrata, and around the same time in Islamic mathematics by al Adli ar Rumi. In 18th century Europe, knight's tours were published by Abraham de Moivre and Leonhard Euler.
Анықтамалар
Гамильтондық жол немесе іздеме жол – графтың әрбір төбесін дәл бір рет басып өтетін жол. Гамильтондық жол бар граф іздеме граф деп аталады. Егер графтың кез келген екі төбесі арасында Гамильтондық жол болса, онда граф Гамильтондық байланысты деп айтылады. Гамильтондық цикл, Гамильтондық контур, төбелік айналу немесе граф циклы – әрбір төбеден дәл бір рет өтетін цикл. Гамильтондық цикл бар граф Гамильтондық граф деп аталады. Осыған ұқсас түсініктер бағытталған графтар үшін де қолданылады, онда жолдың немесе циклдың әрбір қабырғасы (арқасы) тек бір бағытта ғана (яғни, төбелер жебелермен байланысқан және қабырғалар "құйрықтан басына" бағытталған) жүріледі. Гамильтондық жіктелу – графтың қабырғаларын Гамильтондық циклдарға жіктеу. Гамильтондық лабиринт – логикалық жұмбақтың бір түрі, онда берілген графтың бірегей Гамильтондық циклын табу міндеті тұрады.
A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a traceable graph. A graph is Hamiltonian connected if for every pair of vertices there is a Hamiltonian path between the two vertices. A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can only be traced in a single direction (i. e., the vertices are connected with arrows and the edges traced "tail to head"). A Hamiltonian decomposition is an edge decomposition of a graph into Hamiltonian circuits. A Hamilton maze is a type of logic puzzle in which the goal is to find the unique Hamiltonian cycle in a given graph.
Қасиеттері
Кез келген Гамильтон циклы оның бір қабырғасын жою арқылы Гамильтон жолына айналуы мүмкін, бірақ Гамильтон жолын Гамильтон циклына тек оның соңғы төбелері жақын болған жағдайда ғана кеңейтуге болады. Барлық Гамильтон графтары екі байланысты, бірақ екі байланысты граф Гамильтон граф болуы міндетті емес (мысалы, Петерсен графигін қараңыз). Эйлер графигі G (әр төбесінің жұп дәрежедегі байланысқан графигі) міндетті түрде Эйлер айналымын, G-нің әр қабырғасынан дәл бір рет өтетін жабық жолды қамтиды. Бұл айналым L(G) сызықтық графигіндегі Гамильтон циклына сәйкес келеді, сондықтан кез келген Эйлер графигінің сызықтық графигі Гамильтондық болады. Сызықтық графтарда Эйлер айналымдарына сәйкес келмейтін басқа да Гамильтон циклдары болуы мүмкін, әсіресе кез келген Гамильтон графтарының сызықтық графтары L(G) графтары Гамильтондық болуы мүмкін, G графигі Эйлер графигі болса да. Турнир (екіден астам төбесі бар) Гамильтондық болып табылады, егер және тек қана ол берік байланысқан болса. n төбесі бар толық бағытталмаған графиктегі әр түрлі Гамильтон циклдарының саны және n төбесі бар толық бағытталған графиктегі саны (n – 1)!. Бұл санаулар бастапқы нүктесінен басқа бірдей циклдар бөлек есептелмейді деп ескереді.
Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to a Hamiltonian cycle only if its endpoints are adjacent. All Hamiltonian graphs are biconnected, but a biconnected graph need not be Hamiltonian (see, for example, the Petersen graph). An Eulerian graph G (a connected graph in which every vertex has even degree) necessarily has an Euler tour, a closed walk passing through each edge of G exactly once. This tour corresponds to a Hamiltonian cycle in the line graph L(G), so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph L(G) of every Hamiltonian graph G is itself Hamiltonian, regardless of whether the graph G is Eulerian. A tournament (with more than two vertices) is Hamiltonian if and only if it is strongly connected. The number of different Hamiltonian cycles in a complete undirected graph on n vertices is and in a complete directed graph on n vertices is (n – 1)!. These counts assume that cycles that are the same apart from their starting point are not counted separately.
Гамильтон циклы полиномы
Берілген салмақты бағытталған графтың (оның қабырғаларына белгілі бір өрістен салмақтар тағайындалған) Гамильтон циклдерінің алгебралық өрнегі – оның салмақты жапсарлас матрицасының Гамильтон циклының полиномы, ол графтың Гамильтон циклдерінің қабырға салмақтарының көбейтінділерінің қосындысы ретінде анықталады. Бұл полином, қабырға салмақтарының функциясы ретінде, граф Гамильтондық болса және тек сонда ғана нөлге тең болмайды. Оны есептеудің және тұрақтыны есептеудің есептеу қиындығы арасындағы байланысты Григорий Коган көрсетті.
An algebraic representation of the Hamiltonian cycles of a given weighted digraph (whose arcs are assigned weights from a certain ground field) is the Hamiltonian cycle polynomial of its weighted adjacency matrix defined as the sum of the products of the arc weights of the digraph's Hamiltonian cycles. This polynomial is not identically zero as a function in the arc weights if and only if the digraph is Hamiltonian. The relationship between the computational complexities of computing it and computing the permanent was shown by Grigoriy Kogan.