Resumen:
Un grafo es una estructura que sirve para representar un conjunto de objetos y relaciones que existen entre ellos. Esta formulación abstracta y de carácter general resulta particularmente útil para modelar una amplia variedad de problemas que en principio parecen ser de naturaleza bien diferente. Existen numerosas cuestiones relacionadas al estudio de los grafos, en este trabajo nos concentramos en un área denominada coloreo de grafos. La elección del nombre proviene tanto de motivos históricos relacionados al problema original como también por razones de representación gráfica a modo didáctico. Pero a pesar del término, el proceso de coloreo se trata de realizar un etiquetado de los elementos del grafo (vértices o aristas) para poder así agruparlos en distintas clases que permitan cumplir con ciertas restricciones. Llamaremos coloreo clásico a la formulación original y más sencilla de este problema, pero veremos también variantes del problema de coloreo que permiten tratar cuestiones más complejas. El problema de coloreo es también interesante de un punto de vista algorítmico debido a que se trata de un problema NP-Completo, es decir que obtener una solución exacta requiere de demasiado tiempo de cómputo, independientemente de cuan poderosa sea la computadora utilizada. Como consecuencia se estudian tanto técnicas para reducir la velocidad de cómputo como también métodos para obtener soluciones sub-óptimas. El objetivo de este trabajo es hacer una recopilación del los principales resultados en cada una de estas áreas para mostrar cual es el estado actual del desarrollo en este campo.
Citación:
---------- APA ----------
Cerisola, Franco. (2019). Estado del arte sobre el problema de coloreo de grafos y sus variantes. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000721_Cerisola
---------- CHICAGO ----------
Cerisola, Franco. "Estado del arte sobre el problema de coloreo de grafos y sus variantes". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/seminario_nMAT000721_Cerisola
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000721_Cerisola.pdf
Distrubución geográfica
