Camí hamiltonià
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.
Referències[modifica]
- ↑ Diccionari terminològic de sistemes d'informació geogràfica. Primera edició. Barcelona: ICC, Institut Cartogràfica de Catalunya, 2012. ISBN 978-84-393-8863-0.
- ↑ Dirac, G. A. «Some Theorems on Abstract Graphs» (en anglès). Proceedings of the London Mathematical Society, s3-2, 1, 1952, pàg. 69–81. DOI: 10.1112/plms/s3-2.1.69.
 |
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Camí hamiltonià |