Regularidades a partir de matrices de adyacencia de grafos específicos que se pueden obtener a partir de ciclos Hamiltonianos.
Abstract
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).
Abstract
In this degree work, an analysis of the adjacency matrices of Hamiltonian cycles has been carried out. This analysis begins with the exploration of its properties and regularities through the study of the adjacency matrices of graphs with an even and odd number of vertices. As a result of this degree work, definitions have been established, such as sequences of vertices, shifts, base matrices and also two theorems, which are composition of cycles and existence of cycles of vertices in even order with their respective demonstrations. . These definitions and theorems arise from generalized patterns that characterize the structure of Hamiltonian cycles that are explained in the development of the document. Furthermore, an algorithm is developed based on the established definitions and theorems, which aims to find a Hamiltonian cycle and thus provide a solution to the TSP (Salesman's Problem).
Collections
Except where otherwise noted, this item's license is described as https://creativecommons.org/licenses/by-nc-nd/4.0/