| dbpprop:abstract
|
- In the mathematical field of graph theory, a Hamiltonian path (or traceable path), is a path in an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem which is 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.
- Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graph der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem alle Kanten genau einmal durchlaufen werden, ist das Hamiltonkreisproblem NP-vollständig, also nur mit hohem Aufwand lösbar. Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Das Hamiltonkreisproblem ist ein Spezialfall des bekannten Problem des Handlungsreisenden, bei welchem nach einem kürzesten Hamiltonkreis in einem gerichteten Graphen mit Kantengewichten gefragt wird.
- En el camp matemàtic de la teoria de grafs, un cicle hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex exactament un cop. Un cicle hamiltonià (o circuït hamiltonià) és un cicle en un graf no dirigit que visita cada vèrtex exactament un cop i retorna al vèrtex de sortida. La determinació de si existeixen aquests camins i cicles als grafs és el el problema del camí hamiltonià, que és un problema NP-complet. Els camins i cicles hamiltonians tenen aquest nom per William Rowan Hamilton, que 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 arrels d'unitat amb moltes similituds amb els quaternions (també inventats per Hamilton). Desafortunadament, aquesta solució no és generalitzable a grafs arbitraris.
- En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, 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. Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos los grafos.
- Hamiltonin polku on verkkoteoriassa polku, joka käy suuntaamattoman graafin jokaisen solmun kautta vain kerran. Hamiltonin kierros eli Hamiltonin piiri on polku, joka käy suuntaamattoman graafin kaikkien solmujen kautta ja palaa lopulta lähtöpisteeseensä. Toisin sanoen polku on suljettu. Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on NP-täydellinen ongelma. Hamiltonin polku ja kierros on nimetty irlantilaisen matemaatikon William Rowan Hamiltonin mukaan.
- En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien. Le plus petit graphe hamiltonien à n sommets est le graphe cycle <math>C_n</math>. Mais un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens. Ainsi le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. Trouver un cycle hamiltonien pour un graphe donné est un problème difficile sur le plan algorithmique, c'est-à-dire de type NP-complet. Le problème du voyageur de commerce s'apparente d'ailleurs à la recherche d'un cycle hamiltonien en ajoutant une contrainte : la minimalisation de son poids dans un graphe complet dont les arêtes sont pondérées.
- A Hamilton-út a gráfelmélet egy fogalma, nevét William Rowan Hamilton ír matematikus, fizikus és csillagászról kapta. Akkor nevezünk egy utat Hamilton-útnak, ha az a gráf minden csúcsán pontosan egyszer halad át.
- Nel campo matematico della teoria dei grafi, un cammino hamiltoniano è un cammino in un grafo non orientato che visita tutti i vertici 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 <math> (p_{0}, p_{1}, ... , p_{n-1}) </math> dei nodi tale che <math>(p_{i},p_{i+1}) \in E</math> per ogni <math> 0 \le \ i \le \ n-2</math> 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. 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.
- ハミルトン路とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。 与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP困難。与えられたグラフがハミルトングラフかどうか判定する問題については、ハミルトン閉路問題を参照のこと。
- Een hamiltonpad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op een pad ligt. De naam Hamiltonpad komt van de Ierse wiskundige Sir William Rowan Hamilton (1805-1865).
- Graf hamiltonowski to graf rozważany w teorii grafów zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim. Aby lepiej zrozumieć właściwości grafu hamiltonowskiego można się posłużyć przykładem komiwojażera, który chce odwiedzić wszystkich swoich klientów, ale tylko raz. Klienci, to wierzchołki grafu, a drogi między nimi są jego krawędziami. Jeżeli graf jest hamiltonowski, to znaczy, że komiwojażer może obejść wszystkich klientów, bez mijania drugi raz żadnego z nich i wrócić do punktu wyjścia.
- 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 com 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. Problema de Roteamento de Veículos Problema do caixeiro viajante Caminho euleriano Solução do problema utilizando bactérias
- Ошибка создания миниатюры: Invalid Parameter - white
Граф додекаэдра с выделенным циклом Гамильтона Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл. Гамильтонов путь (или гамильтонова цепь) — путь, содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом. Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
- En Hamiltongraf är inom matematik en graf som saknar Hamiltonvägar. En Hamiltonväg är en väg i en graf som innehåller varje nod exakt en gång. En Hamiltoncykel är en Hamiltonväg som börjar och slutar i samnma nod. Hamiltongrafer har många tillämpningar, bl.a. handelsresandeproblemet och springareproblemet.
- Гамільто́нів гра́ф - в математиці це граф, що містить гамільтонів шлях або гамільтонів цикл. Гамільто́нів шля́х - шлях, що містить кожну вершину графа рівно один раз. Гамільтонів шлях, початкова і кінцева вершини якого співпадають, називається гамільтоновим циклом. Гамільтонові шлях, цикл і граф названі на честь ірландського математика Вільяма Гамільтона, який вперше визначив ці класи, дослідивши задачу «кругосвітньої подорожі» по додекаедру, вузлові вершини якого символізували найбільші міста Землі, а ребра — дороги, що їх з'єднують.
- 哈密顿图，在图论中是指含有哈密顿圈的图，闭合的哈密顿路径称作哈密顿圈，含有图中所有顶的路径称作哈密顿路径。 美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等於顶点总数，那这个图一定是哈密尔顿图。 哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全问题。后来人们也证明了,找一条哈密顿路的近似比为常数的近似算法也是NP完全的. 寻找哈密顿路的确定算法虽然很难有多项式时间的,但是这并不意味着只能进行时间复杂度为O(n!*n)暴力搜索. 利用状态压缩动态规划,我们可以将时间复杂度降低到O(2^n*n^3),具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S的,到达节点j时的最短路径. 每次我们都按照点j所连的节点进行转移.
|
| rdfs:comment
|
- In the mathematical field of graph theory, a Hamiltonian path (or traceable path), is a path in an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem which is NP-complete.
- Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graph der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem alle Kanten genau einmal durchlaufen werden, ist das Hamiltonkreisproblem NP-vollständig, also nur mit hohem Aufwand lösbar.
- En el camp matemàtic de la teoria de grafs, un cicle hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex exactament un cop. Un cicle hamiltonià (o circuït hamiltonià) és un cicle en un graf no dirigit que visita cada vèrtex exactament un cop i retorna al vèrtex de sortida. La determinació de si existeixen aquests camins i cicles als grafs és el el problema del camí hamiltonià, que és un problema NP-complet.
- En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, 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.
- Hamiltonin polku on verkkoteoriassa polku, joka käy suuntaamattoman graafin jokaisen solmun kautta vain kerran. Hamiltonin kierros eli Hamiltonin piiri on polku, joka käy suuntaamattoman graafin kaikkien solmujen kautta ja palaa lopulta lähtöpisteeseensä. Toisin sanoen polku on suljettu. Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on NP-täydellinen ongelma. Hamiltonin polku ja kierros on nimetty irlantilaisen matemaatikon William Rowan Hamiltonin mukaan.
- En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien. Le plus petit graphe hamiltonien à n sommets est le graphe cycle <math>C_n</math>. Mais un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens.
- A Hamilton-út a gráfelmélet egy fogalma, nevét William Rowan Hamilton ír matematikus, fizikus és csillagászról kapta. Akkor nevezünk egy utat Hamilton-útnak, ha az a gráf minden csúcsán pontosan egyszer halad át.
- Nel campo matematico della teoria dei grafi, un cammino hamiltoniano è un cammino in un grafo non orientato che visita tutti i vertici 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 <math> (p_{0}, p_{1}, ...
- Een hamiltonpad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op een pad ligt. De naam Hamiltonpad komt van de Ierse wiskundige Sir William Rowan Hamilton (1805-1865).
- Graf hamiltonowski to graf rozważany w teorii grafów zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim.
- 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 com 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.
- Ошибка создания миниатюры: Invalid Parameter - white
Граф додекаэдра с выделенным циклом Гамильтона Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
- En Hamiltongraf är inom matematik en graf som saknar Hamiltonvägar. En Hamiltonväg är en väg i en graf som innehåller varje nod exakt en gång. En Hamiltoncykel är en Hamiltonväg som börjar och slutar i samnma nod. Hamiltongrafer har många tillämpningar, bl.a. handelsresandeproblemet och springareproblemet.
- Гамільто́нів гра́ф - в математиці це граф, що містить гамільтонів шлях або гамільтонів цикл. Гамільто́нів шля́х - шлях, що містить кожну вершину графа рівно один раз. Гамільтонів шлях, початкова і кінцева вершини якого співпадають, називається гамільтоновим циклом.
|
![[RDF Data]](/statics/sw-cube.png)
