Hamiltonian path (original) (raw)

dbo:abstract

في نظرية التعقيد وفي نظرية المخططات، تحديد مسار هاملتونياني هو أحد مسائل NP الكاملة. وهناك عدة نسخ لهذه المسألة من بينها: (ar)
En el camp matemàtic de la teoria de grafs, un camí hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex del graf exactament un cop. Un cicle hamiltonià (o circuit hamiltonià) és un camí hamiltonià que retorna al vèrtex de sortida. La determinació de si existeixen aquests camins i cicles als grafs és el , que és un problema NP-complet. Els camins i cicles hamiltonians deuen el seu nom al matemàtic William Rowan Hamilton, qui va inventar el joc icòsic, ara també conegut com el puzzle de Hamilton, que tracta sobre trobar un cicle hamiltonià en el graf que formen les arestes del dodecàedre. Hamilton va resoldre aquest problema fent servir el càlcul icòsic, una estructura algebraica basada en amb moltes similituds amb els (també inventats i estudiats per ell mateix). Malauradament, aquesta solució no és generalitzable a grafs arbitraris. (ca)
En teoría de grafos, un camino hamiltoniano en un grafo es un camino (es decir, una sucesión de aristas adyacentes), que visita todos los vértices del grafo una sola vez. Si además el primer y último vértice visitado coincide, el camino es un ciclo hamiltoniano. El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo y como tal aparece en la lista de los 21 problemas NP-completos de Karp. El nombre proviene del matemático irlandés sir William Rowan Hamilton (1805-65), que propuso viajar a veinte ciudades del mundo, representadas como los vértices de un dodecaedro regular, siguiendo las aristas del dodecaedro. No obstante, los ciclos y caminos actualmente denominados hamiltonianos aparecieron mucho antes. Al parecer, ya en el siglo IX el poeta indio Rudrata nombra el llamado camino del caballo. Se trata de una sucesión de movimientos del caballo sobre un arcidriche de manera que esta pieza, el caballo, visite todos y cada uno de los escaques una sola vez. Se trata, en consecuencia, de encontrar un camino hamiltoniano en un grafo cuyos vértices son los escaques de un arcidriche de manera que dos vértices son adyacentes si y sólo si se puede pasar de uno a otro mediante un movimiento de caballo. (es)
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. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete. 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. (en)
Lintasan Hamilton adalah lintasan yang melalui tiap verteks di dalam graf tepat satu kali. Bila lintasan itu kembali ke verteks asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton adalah sirkuit yang melalui tiap verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton. Pada tahun 1859, Matematikawan dari Irish, Sir William Rowan Hamilton mengembangkan permainan yang di beli dari perusahaan mainan di Dublin. Permainan itu dinamakan Prominent Cities. Tujuan dari permainan iu adalah mencari sirkuit sepanjang jalan yang terbentuk sehingga di dalam itu terdapat 20 kota dan dapat dilewati tepat satu kali. Penulis dapat menggambarkan alat itu dengan sebuah graf: Verteks dari graf melambangakan verteks dari alat tersebut dan panjangnya edges disamakan dengan alat tersebut. Untuk menentukan sebuah graf itu adalah Siklus Hamilton atau tidak, pastinya lebih sulit dari pada menentukan itu Eulerian. Selain itu, tidak ada cara pasti yang diketahui untuk menentukannya. Siklus dalam graf akan terbagi menjadi dua yaitu Euler dan Hamilton. Eulerian adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua edges yang ada dalam graf tersebut. Dan tidak menjadi suatu masalah jika sebuah verteks dilewati sebanyak apapun. Tetapi pada Hamilton adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua verteks dalam graf tersebut dan hanya tepat satu kali, kecuali verteks awal didatangi dua kali. Jika sebuah verteks itu telah dilewati dua atau lebih dalam suatu siklus maka siklus tesebut tidak dapat dikatakan sebagai siklus Hamiltonian. Diberikan contoh dalam suatu graf ada terdapat lima buah verteks. Di misalkan A, B, C, D, dan E. Dari siklus yang terjadi penulis dapat menentukan siklus itu Hamilton atau tidak. * Siklus 1: A – B – C – D – E * Siklus 2: A – B – C – B – D – E * Siklus 3: A – C – B – E – D * Siklus 4: A – B – E – C – B – D Dari empat siklus diatas dapat dilihat siklus 1 dan 3 adalah Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan hanya tepat satu kali. Tetapi pada siklus 2 dan 4 bukan Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan ada yang melebihi satu kali. Pada siklus 2 dan 4 muncul verteks B sebanyak dua kali. Dan itu melanggar sifat dari sebuah siklus Hamilton. Siklus Hamilton dapat ditemukan di banyak hal. (in)
그래프 이론에서 해밀턴 경로(Hamilton經路, 영어: Hamiltonian path)는 모든 꼭짓점을 한 번씩 지나는 경로이다. (ko)
Een hamiltonpad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op het pad ligt. Een gesloten hamiltonpad noemt men een hamiltoncykel of hamiltoncircuit. De naam hamiltonpad komt van de Ierse wiskundige Sir William Rowan Hamilton (1805-1865). Een graaf die een hamiltoncircuit bevat noemt men een hamiltoniaanse graaf of hamilton-graaf. Elke cykel-graaf is hamiltoniaans, evenals elke volledige graaf met 3 of meer knopen. Een graaf is hamilton-verbonden of hamilton-geconnecteerd als voor elk paar van onderscheiden knooppunten u en v er een hamiltonpad bestaat met als eindpunten u en v. De graaf bestaande uit één enkel knooppunt is triviaal hamilton-verbonden. Het bepalen of er een hamiltonpad of hamiltoncircuit bestaat in een gegeven graaf, die gericht of niet-gericht kan zijn, is een fundamenteel probleem in de grafentheorie. Dit hamiltonpadprobleem is NP-volledig. Het is een speciaal geval van het handelsreizigersprobleem; dat bekomen wordt door de afstand tussen twee steden gelijk aan één te stellen als ze aanliggend zijn, en gelijk aan twee als dat niet zo is. Als de afgelegde afstand gelijk aan het aantal steden is, is de route een hamiltonpad. Als er geen hamiltonpad is, zal de kortste route langer zijn. (nl)
Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta. Determinare se questo cammino esista è un problema NP-completo. In termini rigorosi, la determinazione di un cammino hamiltoniano è la ricerca di una permutazione dei nodi tale che per ogni dove con E si intende l'insieme di archi del Grafo. Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega l'ultimo vertice con il primo, realizzando così un ciclo che visita tutti i vertici per poi ritornare al punto di partenza. Sir William Rowan Hamilton (1805–1865) Un grafo che contenga almeno un ciclo hamiltoniano viene detto grafo hamiltoniano. Questi particolari cammini hanno preso il nome da William Rowan Hamilton che inventò un gioco da tavolo, il puzzle di Hamilton o icosian game, che consisteva nel trovare un cammino chiuso sul bordo di un dodecaedro. (it)
Ścieżka Hamiltona – ścieżka w grafie przebiegająca przez wszystkie jego wierzchołki dokładnie raz. Graf zawierający ścieżkę Hamiltona jest grafem półhamiltonowskim. Odpowiedź na pytanie, czy graf zawiera ścieżkę Hamiltona jest w teorii obliczeń problemem NP-zupełnym, tj. nie istnieją efektywne algorytmy odpowiadające na to pytanie. Wszystkie ścieżki Hamiltona można znaleźć np. przy pomocy metody kompozycji łacińskiej. Niekiedy o grafie, który posiada ścieżkę hamiltonowską oraz nie ma cyklu hamiltonowskiego, mówi się, że jest grafem trasowalnym lub grafem półhamiltonowskim. (pl)
Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou seja, passar por todos uma e uma só vez por cada. Caso esse caminho seja possível descrever um ciclo, este é denominado ciclo hamiltoniano (ou circuito hamiltoniano) em G. E, um grafo que possua tal circuito é chamado de grafo hamiltoniano. O problema de decidir se um dado grafo é hamiltoniano é completo em NP, o que significa que é pouco provável que exista um algoritmo polinomial para o problema. Outro objetivo provavelmente ambicioso demais: mostrar que o problema está em co-NP, ou seja, obter uma boa condição necessária e suficiente para existência de ciclo hamiltoniano. Um problema que envolve caminhos hamiltonianos é o problema do caixeiro viajante, em que um caixeiro deseja visitar um conjunto de N cidades (vértices), passando por cada cidade exatamente uma vez e retornando à cidade de origem, fazendo o caminho de menor tamanho possível. Em 2009 conseguiu-se uma resolução para este problema utilizando-se de bactérias na implementação do algoritmo, que historicamente costuma ter um custo de tempo de computação exponencial. (pt)
在圖論中，哈密顿路径（台湾作漢米頓路徑）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（台湾作漢米頓環），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。 (zh)

dbo:wikiPageExternalLink

dbo:wikiPageWikiLink

dbp:name

dbr:Ore's_theorem
Bondy–Chvátal Theorem (en)
Dirac's Theorem (en)
Ghouila–Houiri (en)
Meyniel (en)
Rahman–Kaykobad (en)

dct:subject

rdf:type

rdfs:comment

في نظرية التعقيد وفي نظرية المخططات، تحديد مسار هاملتونياني هو أحد مسائل NP الكاملة. وهناك عدة نسخ لهذه المسألة من بينها: (ar)
그래프 이론에서 해밀턴 경로(Hamilton經路, 영어: Hamiltonian path)는 모든 꼭짓점을 한 번씩 지나는 경로이다. (ko)
Ścieżka Hamiltona – ścieżka w grafie przebiegająca przez wszystkie jego wierzchołki dokładnie raz. Graf zawierający ścieżkę Hamiltona jest grafem półhamiltonowskim. Odpowiedź na pytanie, czy graf zawiera ścieżkę Hamiltona jest w teorii obliczeń problemem NP-zupełnym, tj. nie istnieją efektywne algorytmy odpowiadające na to pytanie. Wszystkie ścieżki Hamiltona można znaleźć np. przy pomocy metody kompozycji łacińskiej. Niekiedy o grafie, który posiada ścieżkę hamiltonowską oraz nie ma cyklu hamiltonowskiego, mówi się, że jest grafem trasowalnym lub grafem półhamiltonowskim. (pl)
在圖論中，哈密顿路径（台湾作漢米頓路徑）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（台湾作漢米頓環），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。 (zh)
En el camp matemàtic de la teoria de grafs, un camí hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex del graf exactament un cop. Un cicle hamiltonià (o circuit hamiltonià) és un camí hamiltonià que retorna al vèrtex de sortida. La determinació de si existeixen aquests camins i cicles als grafs és el , que és un problema NP-complet. (ca)
En teoría de grafos, un camino hamiltoniano en un grafo es un camino (es decir, una sucesión de aristas adyacentes), que visita todos los vértices del grafo una sola vez. Si además el primer y último vértice visitado coincide, el camino es un ciclo hamiltoniano. El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo y como tal aparece en la lista de los 21 problemas NP-completos de Karp. (es)
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. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete. (en)
Lintasan Hamilton adalah lintasan yang melalui tiap verteks di dalam graf tepat satu kali. Bila lintasan itu kembali ke verteks asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton adalah sirkuit yang melalui tiap verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton. (in)
Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta. Determinare se questo cammino esista è un problema NP-completo. In termini rigorosi, la determinazione di un cammino hamiltoniano è la ricerca di una permutazione dei nodi tale che per ogni dove con E si intende l'insieme di archi del Grafo. Sir William Rowan Hamilton (1805–1865) Un grafo che contenga almeno un ciclo hamiltoniano viene detto grafo hamiltoniano. (it)
Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou seja, passar por todos uma e uma só vez por cada. Caso esse caminho seja possível descrever um ciclo, este é denominado ciclo hamiltoniano (ou circuito hamiltoniano) em G. E, um grafo que possua tal circuito é chamado de grafo hamiltoniano. Em 2009 conseguiu-se uma resolução para este problema utilizando-se de bactérias na implementação do algoritmo, que historicamente costuma ter um custo de tempo de computação exponencial. (pt)
Een hamiltonpad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op het pad ligt. Een gesloten hamiltonpad noemt men een hamiltoncykel of hamiltoncircuit. De naam hamiltonpad komt van de Ierse wiskundige Sir William Rowan Hamilton (1805-1865). Een graaf die een hamiltoncircuit bevat noemt men een hamiltoniaanse graaf of hamilton-graaf. Elke cykel-graaf is hamiltoniaans, evenals elke volledige graaf met 3 of meer knopen. (nl)

rdfs:label

مسار هاملتونياني (ar)
Camí hamiltonià (ca)
Hamiltonovská cesta (cs)
Hamiltonweg (de)
Camino hamiltoniano (es)
Lintasan Hamilton (in)
Hamiltonian path (en)
Chaîne hamiltonienne (fr)
Cammino hamiltoniano (it)
해밀턴 경로 (ko)
ハミルトン路 (ja)
Ścieżka Hamiltona (pl)
Hamiltonpad (nl)
Caminho hamiltoniano (pt)
Гамильтонова цепь (ru)
Hamiltonväg (sv)
哈密頓路徑 (zh)
Гамільтонів шлях (uk)

is dbo:wikiPageWikiLink of