Hamiltonian path problem (original) (raw)
En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema ciclo de Hamilton son problemas de determinar si un camino hamiltoniano o un ciclo de Hamilton existe en un grafo dado (ya sea dirigido o no dirigido). Ambos problemas son NP-completo.
| Property | Value |
|---|---|
| dbo:abstract | En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema ciclo de Hamilton son problemas de determinar si un camino hamiltoniano o un ciclo de Hamilton existe en un grafo dado (ya sea dirigido o no dirigido). Ambos problemas son NP-completo. (es) Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Die Frage, ob ein solcher Kreis in einem gegebenen Graphen existiert, ist ein wichtiges Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem ein Kreis gesucht wird, der alle Kanten genau einmal durchläuft, ist das Hamiltonkreisproblem NP-vollständig. Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Eine Verallgemeinerung des Hamiltonkreisproblems ist das Problem des Handlungsreisenden, bei dem nach einem kürzesten Hamiltonkreis in einem Graphen mit Kantengewichten gefragt wird. (de) In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer). (en) ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。 (ja) Задача про гамільтонів шлях і задача про гамільтонів цикл — це задачі визначення, чи існує гамільтонів шлях або гамільтонів цикл у заданому графі (орієнтованому або неорієнтованому). Обидві задачі NP-повні. (uk) No campo matemático da teoria dos grafos o Problema do caminho hamiltoniano e o Problema do ciclo hamiltoniano são problemas de determinar se um Caminho hamiltoniano ou um Ciclo hamiltoniano existe em um dado grafo (direcionado ou não direcionado). Ambos os problemas são NP-completos. (pt) Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны. (ru) 图论中的经典问题哈密顿路径问题（台湾作漢米頓路徑問題）（Hamiltonian path problem）与哈密顿环问题（台湾作漢米頓環問題）（Hamiltonian cycle problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。 (zh) |
| dbo:wikiPageID | 149646 (xsd:integer) |
| dbo:wikiPageLength | 14643 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1053285848 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monte_Carlo_algorithm dbr:Barnette's_conjecture dbr:Regular_graph dbr:DNA_computing dbr:Undirected_graph dbr:Decision_problem dbr:Degree_(graph_theory) dbc:NP-complete_problems dbr:Complete_graph dbr:Mathematics dbr:Christos_Papadimitriou dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:Leonard_Adleman dbr:Complexity_class dbr:PPA_(complexity) dbr:Travelling_salesman_problem dbr:W._T._Tutte dbr:K-vertex-connected_graph dbr:Karp's_21_NP-complete_problems dbr:Lattice_graph dbr:Dynamic_programming dbc:Hamiltonian_paths_and_cycles dbr:Directed_graph dbr:Graph_theory dbr:Hamiltonian_path dbr:Handshaking_lemma dbr:Big_O_notation dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Edge_contraction dbr:Planar_graph dbr:Inclusion–exclusion_principle dbr:SAT_solver dbr:FNP_(complexity) dbr:Universal_vertex dbr:Brute_force_search dbr:Held-Karp_algorithm dbr:Bridgeless_graph dbr:Tutte_path |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Commons_category_inline dbt:Reflist dbt:Short_description dbt:Tmath |
| dct:subject | dbc:NP-complete_problems dbc:Hamiltonian_paths_and_cycles dbc:Computational_problems_in_graph_theory |
| gold:hypernym | dbr:Problems |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Attribute100024264 yago:Condition113920835 yago:Course100038262 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:PsychologicalFeature100023100 yago:WikicatHamiltonianPathsAndCycles yago:YagoPermanentlyLocatedEntity dbo:Disease yago:State100024720 yago:Way100415676 |
| rdfs:comment | En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema ciclo de Hamilton son problemas de determinar si un camino hamiltoniano o un ciclo de Hamilton existe en un grafo dado (ya sea dirigido o no dirigido). Ambos problemas son NP-completo. (es) ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。 (ja) Задача про гамільтонів шлях і задача про гамільтонів цикл — це задачі визначення, чи існує гамільтонів шлях або гамільтонів цикл у заданому графі (орієнтованому або неорієнтованому). Обидві задачі NP-повні. (uk) No campo matemático da teoria dos grafos o Problema do caminho hamiltoniano e o Problema do ciclo hamiltoniano são problemas de determinar se um Caminho hamiltoniano ou um Ciclo hamiltoniano existe em um dado grafo (direcionado ou não direcionado). Ambos os problemas são NP-completos. (pt) Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны. (ru) 图论中的经典问题哈密顿路径问题（台湾作漢米頓路徑問題）（Hamiltonian path problem）与哈密顿环问题（台湾作漢米頓環問題）（Hamiltonian cycle problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。 (zh) Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Die Frage, ob ein solcher Kreis in einem gegebenen Graphen existiert, ist ein wichtiges Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem ein Kreis gesucht wird, der alle Kanten genau einmal durchläuft, ist das Hamiltonkreisproblem NP-vollständig. (de) In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. (en) |
| rdfs:label | Hamiltonkreisproblem (de) Problema del camino Hamiltoniano (es) Hamiltonian path problem (en) ハミルトン閉路問題 (ja) Problema do caminho hamiltoniano (pt) Задача о гамильтоновом пути (ru) 哈密顿路径问题 (zh) Задача про гамільтонів шлях (uk) |
| owl:sameAs | freebase:Hamiltonian path problem yago-res:Hamiltonian path problem wikidata:Hamiltonian path problem dbpedia-de:Hamiltonian path problem dbpedia-es:Hamiltonian path problem dbpedia-ja:Hamiltonian path problem dbpedia-pt:Hamiltonian path problem dbpedia-ro:Hamiltonian path problem dbpedia-ru:Hamiltonian path problem dbpedia-sr:Hamiltonian path problem dbpedia-tr:Hamiltonian path problem dbpedia-uk:Hamiltonian path problem dbpedia-zh:Hamiltonian path problem https://global.dbpedia.org/id/57xAp |
| prov:wasDerivedFrom | wikipedia-en:Hamiltonian_path_problem?oldid=1053285848&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Hamiltonian_path_problem |
| is dbo:wikiPageRedirects of | dbr:Directed_Hamiltonian_cycle_problem dbr:Hamiltonian_Path_Problem dbr:Algorithms_for_solving_the_Hamiltonian_path_problem dbr:Hamilton_path_problem dbr:Hamiltonian_cycle_problem dbr:Directed_Hamiltonian_circuit_problem |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:List_of_graph_theory_topics dbr:DNA_computing dbr:Degree-constrained_spanning_tree dbr:Escherichia_coli_in_molecular_biology dbr:1994_in_science dbr:Game_of_the_Amazons dbr:Optical_computing dbr:Computational_complexity_theory dbr:Minimum_degree_spanning_tree dbr:Spanning_tree dbr:Travelling_salesman_problem dbr:Held–Karp_algorithm dbr:Karp's_21_NP-complete_problems dbr:Lateral_computing dbr:Path_cover dbr:Escherichia_coli dbr:Goishi_Hiroi dbr:Graph_theory dbr:Knight's_tour dbr:List_of_NP-complete_problems dbr:Directed_Hamiltonian_cycle_problem dbr:HCP dbr:Hamiltonian_path dbr:Hamiltonian_Path_Problem dbr:Cograph dbr:Average-case_complexity dbr:Soumitro_Banerjee dbr:Algorithms_for_solving_the_Hamiltonian_path_problem dbr:Longest_path_problem dbr:Nerode_Prize dbr:The_Art_of_Computer_Programming dbr:Subgraph_isomorphism_problem dbr:NP-completeness dbr:Peptide_computing dbr:Hamilton_path_problem dbr:Hamiltonian_cycle_problem dbr:Directed_Hamiltonian_circuit_problem |
| is foaf:primaryTopic of | wikipedia-en:Hamiltonian_path_problem |