Camí hamiltonià
De Viquipèdia
En el camp matemàtic de la teoria de grafs, un cicle hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex exctament un cop. Un cicle hamiltonià (o circuït hamiltonià) és un cicle en un graf no dirigit que visita cada vèrtex exactament un cop i retorna al vèrtex de sortida. La determinació de si existeixen aquests camins i cicles als grafs és el el problema del camí hamiltonià, que és un problema NP-complet.
Els camins i cicles hamiltonians tenen aquest nom per William Rowan Hamilton, que va inventar el joc icòsic, ara també conegut com el puzzle de Hamilton, que tracta sobre trobar un cicle Hamiltonia 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 per Hamilton). Desafortunadament, aquesta solució no és generalitzable a grafs arbitraris.
