Metraipolis › archive › dc_719e98ddfa08

Problema del ciclo hamiltoniano — Wikipedia (es)

Source: Wikipedia (es)
Original: https://es.wikipedia.org/wiki/Problema_del_ciclo_hamiltoniano
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T16:05:52.110Z
SHA-256 of the archived text: d0e5ee90d6c0c17133aa49b50fff24004eff4244d98b9ca242bf8a63218acbcb
Stable URL of this page: https://metraipolis.com/documento/dc_719e98ddfa08

How to cite

Problema del ciclo hamiltoniano — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Problema_del_ciclo_hamiltoniano (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_719e98ddfa08 (Metraipolis archive dc_719e98ddfa08, sha256 d0e5ee90d6c0c17133aa49b50fff24004eff4244d98b9ca242bf8a63218acbcb)

BibTeX

@misc{dc719e98ddfa08,
  title = {Problema del ciclo hamiltoniano — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Problema_del_ciclo_hamiltoniano},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_719e98ddfa08; sha256 d0e5ee90d6c0c17133aa49b50fff24004eff4244d98b9ca242bf8a63218acbcb},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Problema_del_ciclo_hamiltoniano. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En teoría de grafos, el Problema del ciclo hamiltoniano y el Problema del camino hamiltoniano tratan de determinar si un ciclo hamiltoniano o un camino hamiltoniano existen en un determinado grafo. Existe una íntima relación entre ambos, de los que se conoce que son NP-completos. Un ciclo hamiltoniano, es a su vez, un ciclo que pasa una y solo una vez por todos los nodos (vértices) del grafo. Cuando hablamos de grafos ponderados, que poseen pesos o costos en sus aristas, se sabe que el ciclo hamiltoniano de menor costo es a su vez también la solución al problema del viajante (TSP, del inglés Travelling Salesman Problem). Si un grafo (G) tiene un vértice de grado 1, automáticamente sabemos que no puede ser hamiltoniano. Para saber si un grafo es Hamiltoniano o no, debemos aplicar el Teorema de Dirac, que se enuncia: "Sea G = (V,E) un grafo conexo con |V| ≥ 3. Si deg(v) ≥ |V|/2 para todo v∈V, entonces G es hamiltoniano." Para facilitar la comprensión del mismo podríamos ver el Teorema de Dirac del modo siguiente: Sea un grafo al que llamaremos G, con sus vértices y aristas, conexo, y con n.º total de vértices mayor o igual a 3. Es decir, el grafo a tratar debe cumplir todas estas características para poder continuar aplicando el Teorema, si no las cumple entonces no será Hamiltoniano. Ahora bien, suponiendo que se cumplen dichas características, proseguimos: Si el grado de cada uno de los vértices de este grafo es mayor o igual que la mitad del número total de vértices, y esto se cumple para todos y cada uno de los vértices de G, entonces este grafo es Hamiltoniano.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Problema del ciclo hamiltoniano» — https://es.wikipedia.org/wiki/Problema_del_ciclo_hamiltoniano
Wikidata Q9062938 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q9062938
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Problema_del_ciclo_hamiltoniano?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 147558858, consultata il 2026-10-07T15:39:09.313Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d911ab252b8a0b2455b913e33d713a248fc69e0ce9c8383d9ae4d812326a4daa