Historia del Ecuador y los preculsores para la independizacion

Ciclo Hamiltoniano.
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
Sabeque es NPcompleto.
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. Desgraciadamente, esta solución no se generaliza a todos los grafos.
Definición
Un caminohamiltoniano es un camino que visita cada vértice exactamente una vez.
Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano ó circuito hamiltoniano si es un ciclo que visita cada vértice exactamente una vez
(Excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano es llamado grafo hamiltoniano.
Ejemplos
· El grafo completo con más de2 vértices es hamiltoniano.
· Todos los grafos con ciclos son hamiltonianos.
· Todos los sólidos platónicos, considerados como grafos, son hamiltonianos.
Notas
Cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano eliminando cualquiera de sus vértices, pero un camino hamiltoniano puede ser extendido en ciclo sólo si los vértices de los extremos son adyacentes.

Ciclohamiltoniano de menor costo
A menos que NP=P, los problemas NP-hard no tienen algoritmos polinomiales por lo que un algoritmo que los resuelva en forma exacta puede tardar un tiempo prohibitivo. Así que debemos conformarnos con algoritmos polinomiales que den soluciones aproximadas. Existen dos categorías de tales algoritmos: algoritmos de aproximación y algoritmos heurísticos. En esta seccióntratamos los primeros.

Indiquemos con A un algoritmo de tiempo polinomial aplicado a un problema de minimización NP-hard que obtiene un valor A(x) aproximado del óptimo para cada instance x del problema. Sea Opt(x) el valor óptimo. Estamos interesados en acotar el error relativo de A(x). Decimos que el problema es -aproximable si existe >0 tal que para cualquier instance x del problema:
orA(x)(1+) opt(x) (1)
Escribiremos tambien:
A(x) k opt(x) (k=1+) (1)
En el caso que se trata de un problema de maximización escribiremos:
A(x) k opt(x) donde k0.
2) Se puede satisfacer la desigualdad (1) para cualquier >0 prefijado.
3) No se puede acotar el error en la forma (1). Decimos que el problema no es aproximable.

Cuando se satisface (1) decimos que el problema esk-aproximable.
El resto de esta sección es una serie de ejemplos.




ÁRBOLES GENERADORES MÍNIMOS
Definición:
El peso de un árbol generador es la suma de los pesos de las ramas del árbol. Un árbol generador mínimo es uno con peso mínimo.
Una interpretación física de este problema es considerar los vértices de un grafo como ciudades, y los pesos de las aristas como los costos deconstrucción y mantenimiento de vías de comunicación entre las ciudades. Supongamos que queremos construir una red de comunicaciones que conecte a todas las ciudades a un costo mínimo. Entonces el problema es determinar un árbol generador mínimo.

Un procedimiento para resolver este problema se base en la observación de que entre todas las aristas en un circuito, la arista con mayor peso no está en elárbol generador mínimo. Sea "C" un circuito en un grafo pesado, y "E" la arista con el mayor peso en "C". Supongamos que "E" es una rama de un árbol generador de T. Sea del conjunto de corte correspondiente a la rama a la rama "E" como el circuito C y el conjunto de corte d deben tener un numero par de aristas en común además de la arista "E" deberán existir al menos una o más aristas que estén...