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.
Datos:Q9062938
Mayo 13, 2022
problema, ciclo, hamiltoniano, este, artículo, sección, necesita, referencias, aparezcan, publicación, acreditada, este, aviso, puesto, diciembre, 2018, teoría, grafos, problema, camino, hamiltoniano, tratan, determinar, ciclo, hamiltoniano, camino, hamiltonia. Este articulo o seccion necesita referencias que aparezcan en una publicacion acreditada Este aviso fue puesto el 8 de diciembre de 2018 En teoria 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 intima relacion 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 vertices 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 tambien la solucion al problema del viajante TSP del ingles Travelling Salesman Problem Si un grafo G tiene un vertice de grado 1 automaticamente 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 comprension del mismo podriamos ver el Teorema de Dirac del modo siguiente Sea un grafo al que llamaremos G con sus vertices y aristas conexo y con n º total de vertices mayor o igual a 3 Es decir el grafo a tratar debe cumplir todas estas caracteristicas para poder continuar aplicando el Teorema si no las cumple entonces no sera Hamiltoniano Ahora bien suponiendo que se cumplen dichas caracteristicas proseguimos Si el grado de cada uno de los vertices de este grafo es mayor o igual que la mitad del numero total de vertices y esto se cumple para todos y cada uno de los vertices de G entonces este grafo es Hamiltoniano Datos Q9062938 Obtenido de https es wikipedia org w index php title Problema del ciclo hamiltoniano amp oldid 142788093, wikipedia, wiki, leyendo, leer, libro, biblioteca,
