Regularidades a partir de matrices de adyacencia de grafos específicos que se pueden obtener a partir de ciclos Hamiltonianos.
En este trabajo de grado, se ha llevado a cabo un análisis de las matrices de adyacencia de ciclos Hamiltonianos. Este análisis se inicia con la exploración de sus propiedades y regularidades a través del estudio de las matrices de adyacencia de grafos con cantidad de vértices par e impar. Como resu...
- Autores:
-
Parra Correa, Jonnathan
Devia Cruz, Juan Pablo
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2023
- Institución:
- Universidad Pedagógica Nacional
- Repositorio:
- Repositorio Institucional UPN
- Idioma:
- spa
- OAI Identifier:
- oai:repository.pedagogica.edu.co:20.500.12209/19060
- Acceso en línea:
- http://hdl.handle.net/20.500.12209/19060
- Palabra clave:
- Ciclos Hamiltonianos
Matrices de adyacencia
Regularidades
Propiedades
Problema del viajante de comercio
Hamiltonian cycles
Adjacency matrices
Regularities
Properties
Traveling salesman problem
- Rights
- openAccess
- License
- https://creativecommons.org/licenses/by-nc-nd/4.0/
Summary: | En este trabajo de grado, se ha llevado a cabo un análisis de las matrices de adyacencia de ciclos Hamiltonianos. Este análisis se inicia con la exploración de sus propiedades y regularidades a través del estudio de las matrices de adyacencia de grafos con cantidad de vértices par e impar. Como resultado de este trabajo de grado, se han establecido definiciones, tales como las secuencias de vértices, los corrimientos, las matrices bases y además dos teoremas, los cuales son composición de ciclos y existencia de ciclos de vértices en orden par con sus respectivas demostraciones. Estas definiciones y teoremas surgen a partir de patrones generalizados que caracterizan la estructura de los ciclos Hamiltonianos que se explican en el desarrollo del documento. Además se desarrolla un algoritmo basados en las definiciones y teoremas establecidas, él cual tiene como objetivo hallar un ciclo Hamiltoniano y así dar una solución al TSP(Problema del viajante de comercio). |
---|