Hamiltonian path
http://dbpedia.org/resource/Hamiltonian_path an entity of type: Place
في نظرية التعقيد وفي نظرية المخططات، تحديد مسار هاملتونياني هو أحد مسائل NP الكاملة. وهناك عدة نسخ لهذه المسألة من بينها:
rdf:langString
그래프 이론에서 해밀턴 경로(Hamilton經路, 영어: Hamiltonian path)는 모든 꼭짓점을 한 번씩 지나는 경로이다.
rdf:langString
Ś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.
rdf:langString
在圖論中，哈密顿路径（台湾作漢米頓路徑）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（台湾作漢米頓環），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
rdf:langString
مسار هاملتونياني
rdf:langString
Camí hamiltonià
rdf:langString
Hamiltonovská cesta
rdf:langString
Hamiltonweg
rdf:langString
Camino hamiltoniano
rdf:langString
Lintasan Hamilton
rdf:langString
Hamiltonian path
rdf:langString
Chaîne hamiltonienne
rdf:langString
Cammino hamiltoniano
rdf:langString
해밀턴 경로
rdf:langString
ハミルトン路
rdf:langString
Ścieżka Hamiltona
rdf:langString
Hamiltonpad
rdf:langString
Caminho hamiltoniano
rdf:langString
Гамильтонова цепь
rdf:langString
Hamiltonväg
rdf:langString
哈密頓路徑
rdf:langString
Гамільтонів шлях
rdf:langString
Bondy–Chvátal Theorem
rdf:langString
Dirac's Theorem
rdf:langString
Ghouila–Houiri
rdf:langString
Meyniel
rdf:langString
Rahman–Kaykobad
xsd:integer
244437
xsd:integer
1096468787
rdf:langString
Hamiltonian Cycle
rdf:langString
HamiltonianCycle
rdf:langString
في نظرية التعقيد وفي نظرية المخططات، تحديد مسار هاملتونياني هو أحد مسائل NP الكاملة. وهناك عدة نسخ لهذه المسألة من بينها:
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
그래프 이론에서 해밀턴 경로(Hamilton經路, 영어: Hamiltonian path)는 모든 꼭짓점을 한 번씩 지나는 경로이다.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Ś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.
rdf:langString
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.
rdf:langString
在圖論中，哈密顿路径（台湾作漢米頓路徑）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（台湾作漢米頓環），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。
rdf:langString
A strongly connected simple directed graph with vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to
rdf:langString
A graph is Hamiltonian if and only if its closure is Hamiltonian.
rdf:langString
A simple graph with vertices is Hamiltonian if every vertex has degree or greater.
rdf:langString
A simple graph with vertices has a Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than .
rdf:langString
A simple graph with vertices is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is or greater.
rdf:langString
A strongly connected simple directed graph with vertices is Hamiltonian if every vertex has a full degree greater than or equal to .
xsd:nonNegativeInteger
18318
