From Wikipedia, the free encyclopedia
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.[1] Un cicle hamiltonià (o circuit 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.[2]
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.