(Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
| Título variante: |
Searching Hamiltonian circuits using Roberts and Flores algorithm |
| Título variante: |
Búsqueda de circuitos Hamiltonianos usando el algoritmo de Roberts y Flores |
| Fecha: |
2017-02-07 |
| Resumen: |
Des de fa més de 150 anys, quan W. R Hamilton va plantejar el concepte dels circuits hamiltonians, fins a dia d'avui, s'han descobert criteris per demostrar si un graf conté circuits hamiltonians, s'han desenvolupat algorismes per tal de trobar-los tots, però l'alta complexitat temporal que comporta resoldre aquestes qüestions en grafs no trivials fa que continuï essent un problema d'actualitat. Aquest projecte ha recopilat els principals criteris i tècniques per tal de desmostrar si un graf és hamiltonià, i també, ha desenvolupat un software per tal de trobar tots els circuits hamiltonians d'un graf utilitzant diferents algorismes, comparant els temps d'execució d'aquests i avaluant quina és la màxima complexitat que toleren utilitzant un ordinador convencional. |
| Resumen: |
For more than 150 years, When W. R Hamilton suggested the concept of Hamiltonian paths, until now, It has been discovered more judgements have proved that if a graph has Hamilitonian paths, as well as algorithms to get all the path's from the graph. However, because of the high temporal complexity that involves resolving these questions on a non trivial graph, It continues to be a problem still to be resolved. This project has gathered together the principal criteria and techniques to prove if a graph is Hamiltonian as well as the development of a software to find all Hamiltonian paths in a graph using the suggested algorithms and evaluating how is the highest complexity that they accept. |
| Resumen: |
Desde hace más de 150 años, cuando WR Hamilton planteó el concepto de los circuitos hamiltonianos, hasta día de hoy, se han descubierto criterios para demostrar si un grafo contiene circuitos hamiltonianos, se han desarrollado algoritmos para encontrarse todos, pero la alta complejidad temporal que conlleva resolver estas cuestiones en grafos no triviales hace que siga siendo un problema de actualidad. Este proyecto ha recopilado los principales criterios y técnicas para desmostrar si un grafo es hamiltoniano, y también, ha desarrollado un software para encontrar todos los circuitos hamiltonianos de un grafo utilizando diferentes algoritmos, comparando los tiempos de ejecución de éstos y evaluando cuál es la máxima complejidad que toleran utilizando un ordenador convencional. |
| Derechos: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, i la comunicació pública de l'obra, sempre que no sigui amb finalitats comercials, i sempre que es reconegui l'autoria de l'obra original. No es permet la creació d'obres derivades.  |
| Lengua: |
Català |
| Titulación: |
Grau en Enginyeria Informàtica [2502441] |
| Plan de estudios: |
Grau en Enginyeria Informàtica [958] |
| Documento: |
Treball final de grau ; Text |
| Área temática: |
Menció Tecnologies de la Informació |
| Materia: |
Grafs ;
Circuits Hamiltonians ;
Roberts i Flores ;
Força Bruta ;
Grafos ;
Circuitos Hamiltonianos ;
Fuerza Bruta ;
Graphs ;
Hamiltonian Circuits ;
Brute Force |
visitante ::
identificación
(Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
