Problema del cicle hamiltoniano

En teoria de grafos, el Problema del cicle hamiltoniano i el Problema del camí hamiltoniano tracten de determinar si un cicle hamiltoniano o un camí hamiltoniano existixen en un determinat grafo. Existix una íntima relació entre abdós, dels que es coneix que són NP-complets. Un cicle hamiltoniano, és a la seua volta, un cicle que passa una i solament una volta per tots els nodos (vèrtiços) del grafo. Quan parlem de grafos ponderats, que posseïxen pesos o costs en les seues arestes, se sap que el cicle hamiltoniano de menor cost és a la seua volta també la solució al problema del viajante (TSP, de l'anglés Travelling Salesman Problem). Si un grafo (G) té un vèrtiç de grau 1, automàticament sabem que no pot ser hamiltoniano.

Per a saber si un grafo és Hamiltoniano o no, devem aplicar la Teorema de Dirac, que s'enuncia:

"Siga G = (V,I) un grafo conexo en |V| ≥ 3. Si deg(v) ≥ |V|/2 per a tot v∈V, llavors G és hamiltoniano."

Per a facilitar la comprensió del mateix podríem vore la Teorema de Dirac del modo següent: Siga un grafo al que cridarem G, en els seus vèrtiços i arestes, conexo, i en n.º total de vèrtiços major o igual a 3. És dir, el grafo a tractar deu complir totes estes característiques per a poder continuar aplicant la Teorema, si no les complix llavors no serà Hamiltoniano. Ara be, suponent que es complixen dites característiques, proseguim:

Si el grau de cada u dels vèrtiços d'este grafo és major o igual que la mitat del número total de vèrtiços, i açò es complix per a tots i cada u dels vèrtiços de G, llavors este grafo és Hamiltoniano.