De Ita Luna, GuillermoDE ITA LUNA, GUILLERMO; 57559Zuñiga Vargas, Lilibeth2021-05-212021-05-212016-04-04https://hdl.handle.net/20.500.12371/12969“El coloreo de grafos es un tema de gran importancia, debido a las numerosas situaciones de la vida que pueden ser modeladas por este. En la actualidad no se conoce un algoritmo polinomial que resuelva el Coloreo de grafos de forma determinista y exacta, por lo que se considera como un problema en la clase de complejidad NP - completo. En esta tesis, se da una breve explicación de las definiciones básicas de la teoría de grafos, y procedimientos básicos y generales utilizados en algoritmos para el coloreo de grafos, ya que son fundamentales para la comprensión de problemas típicos en la teoría de grafos. El motivo de esta tesis es proponer un algoritmo heurístico, para calcular el número cromático de un grafo de forma eficiente, siendo esté el problema medular en el área de Coloreo de grafos”.pdfspaINGENIERÍA Y TECNOLOGÍATeoría de grafosComplejidad computacionalTesis de licenciaturaGráficas--ColoraciónopenAccessNP-Hard