Camí hamiltoniano

Camí hamiltoniano

Un cicle hamiltoniano en el grafo d'un dodecaedre. El grafo del dodecaedre és hamiltoniano com el restant de grafos de sòlits platònics

Tres eixemples de cicles hamiltonianos en un gràfic de celosía quadrada 8x8

En teoria de grafos, un camí hamiltoniano en un grafo és un camí (és dir, una successió d'arestes adjacents), que visita tots els vèrtiços del grafo una sola volta. Si ademés el primer i últim vèrtiç visitat coincidix, el camí és un cicle hamiltoniano.

El problema de trobar un cicle (o camí) hamiltoniano en un grafo arbitrari se sap que és NP-complet i com tal apareix en la llistadels 21 problemes NP-complets de Karp.

El nom prové del matemàtic irlandés sir William Rowan Hamilton (1805-65), que va propondre viajar a vint ciutats del món, representades com els vèrtiços d'un dodecaedre regular, seguint les arestes del dodecaedre.

No obstant, els cicles i camins actualment denominats hamiltonianos varen aparéixer molt abans. Segons pareix, ya en el IX el poeta indi Rudrata nomena el cridat camine del cavall. Es tracta d'una successió de moviments del cavall sobre un arcidriche de manera que esta peça, el cavall, visite tots i cada u dels escaques una sola volta. Es tracta, en conseqüència, de trobar un camí hamiltoniano en un grafo els vèrtiços del qual són els escaques d'un arcidriche de manera que dos vèrtiços són adjacents si i només si es pot passar d'un a un atre per mig d'un moviment de cavall.

Definició

1. Un camí sense vèrtiços repetits que recorre tots els vèrtiços del grafo es diu camí hamiltoniano.
2. Un camí hamiltoniano que siga un circuit es diu circuit hamiltoniano.
3. Un grafo que té un circuit hamiltoniano es diu grafo hamiltoniano.

Para grafos dirigits, o dígrafs, les definicions corresponents tenen en conte que les arestes estan dirigides.

1. Un camí dirigit en un dígraf és camí dirigit hamiltoniano si visita tots els vèrtiços del dígraf sense repetir cap.
2. Un cicle dirigit hamiltoniano en un dígraf és un camí dirigit hamiltoniano que és cicle.
3. El grafo dirigit és dígraf hamiltoniano si conté un cicle dirigit hamiltoniano.

Al contrari que en el cas dels grafos eulerianos, no es coneix cap caracterisació dels grafos hamiltonianos.

Des de després, tots els grafos hamiltonianos són conexos pero no tots els grafos conexos són hamiltonianos.

Eixemples

• Tots els grafos cicles són hamiltonianos.
• Els grafos complets en més de dos vèrtiços són hamiltonianos.
• Tots els campeonats posseïxen camins dirigits hamiltonianos. Es pot consultar la demostració en [Theorem 2.2.1].
• Tots els sòlits platònics (el tetraedre, la gaveta, l'octaedre, el dodecaedre i l'icosaedre), considerats com grafos, són hamiltonianos.
• Entre els grafos eulerianos els cal són hamiltonianos i els cal no ho són, i entre els grafos hamiltonianos els cal són eulerianos i els cal no ho són.

  

  Grafos: G₁, G₂, G₃ i G₄

  1. El grafo G₁ és euleriano i hamiltoniano.
  2. El grafo G₂ és euleriano i no és hamiltoniano.
  3. El grafo G₃ és no euleriano i és hamiltoniano.

• El grafo G₄ és no euleriano i no és hamiltoniano.