Título

Anticoloraciones en gráficas

Autor

Luis Eduardo Urban Rivero

Colaborador

JAVIER RAMÍREZ RODRÍGUEZ (Asesor de tesis)

Rafael López-Bracho (Asesor de tesis)

Nivel de Acceso

Acceso Abierto

Resumen o descripción

114 páginas. Doctorado en Optimización.

Uno de los problemas más conocidos y estudiados de la teoría de gráficas es el problema de coloración. Un caso especial del problema de coloración supuso una de las preguntas matemáticas más controvertidas de la humanidad, conocido ahora como el teorema de los cuatro colores. Controvertida por dos razones, la dificultad para encontrar su respuesta y porque en su demostración se emplearon por primera vez computadoras. En el mismo sentido de los problemas de coloración, Berge propuso en los 70’s un problema que 30 años después provocaría la creación de una teoría bajo el nombre del problema de anticoloración. El problema de Berge versa sobre lo siguiente. Dado un tablero de ajedrez de n_n, b reinas negras y w reinas blancas. ¿Es posible colocar las reinas negras y blancas en el tablero sin que se ataquen mutuamente? En las anticoloraciones se le pide a la coloración la condición opuesta a la coloración clásica, es decir si dos vértices son adyacentes estos deben tener el mismo color. Para que esto tenga sentido se deben agregar algunas condiciones al problema, como la existencia de vértices incoloros y que las cardinalidades de las clases de color sean fijas. En esta tesis se presenta la demostración de una conjetura que deriva del problema de Berge con caballos en lugar de reinas. Además de que se proponen modelos de programación lineal entera, no lineal entera y multiobjetivo para poder resolver problemas de anticoloración con dos colores por medio de algoritmos exactos. Además de lo anterior se presenta una mejora de las heurísticas parados colores y se propone una nueva heurística basada en algoritmos genéticos. Por último, se dan las extensiones necesarias para trabajar el problema de anticoloración con más de dos colores, tanto con algoritmos exactos como con métodos heurísticos.

Editor

Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información.

Fecha de publicación

junio de 2018

Tipo de publicación

Tesis de doctorado

Recurso de información

Formato

application/pdf

Idioma

Español

Audiencia

Estudiantes

Investigadores

Repositorio Orígen

Repositorio Institucional Zaloamati

Descargas

82

Comentarios



Necesitas iniciar sesión o registrarte para comentar.