Camí hamiltonià

De Viquipèdia
Dreceres ràpides: navegació, cerca
Un camí hamiltonià (en negre) sobre un graf (en blau).

En el camp matemàtic de la teoria de grafs, un camí hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex del graf exactament un cop. Un cicle hamiltonià (o circuït hamiltonià) és un camí hamiltonià que retorna al vèrtex de sortida. La determinació de si existeixen aquests camins i cicles als grafs és el problema del camí hamiltonià, que és un problema NP-complet.

Els camins i cicles hamiltonians deuen el seu nom al matemàtic William Rowan Hamilton, qui va inventar el joc icòsic, ara també conegut com el puzzle de Hamilton, que tracta sobre trobar un cicle hamiltonià en el graf que formen les arestes del dodecàedre. Hamilton va resoldre aquest problema fent servir el càlcul icòsic, una estructura algebraica basada en arrels d'unitat amb moltes similituds amb els quaternions (també inventats i estudiats per ell mateix). Malauradament, aquesta solució no és generalitzable a grafs arbitraris.


A Wikimedia Commons hi ha contingut multimèdia relatiu a: Camí hamiltonià Modifica l'enllaç a Wikidata