Almacenamiento

UNIVERSIDAD POLITÉCNICA DE MADRID
FACULTAD DE INFORMÁTICA

TRABAJO FIN DE CARRERA

“COLORACIÓN DE GRAFOS”

AUTOR: Javier Muñoz Rodríguez TUTOR: Gregorio Hernández Peñalver

Coloración de grafos

Agradecimientos

Agradecimientos
Tras una ardua tarea y largo tiempo de desarrollo por fin puedo decir que he finalizado el proyecto fin de carrera. Sin duda ha sido un trabajo muy duro.Una carrera de resistencia que ha durado casi 3 años. No ha sido fácil, de verdad que no, y más al compaginarlo con un trabajo a jornada completa en el difícil mundo de la consultoría. Además, muchos acontecimientos han ocurrido durante este tiempo, como mi boda y el traslado al nuevo piso. Pero a pesar de todo, se ha realizado. Este proyecto no se habría realizado si no hubiera elegido en eltercer curso de la carrera la asignatura Teoría de Grafos, impartida por mi actual tutor del proyecto. La asignatura me gustó desde el primer día y además en su página web observé que se hacían proyectos de fin de carrera, que el profesor usaba para explicar algunos de los temas de la asignatura. Esto me llevó a decidirme por realizar un proyecto de este tipo, cuando finalizaba los estudiosuniversitarios. Está claro que no hubiera podido realizar este proyecto yo solo sin la inestimable ayuda de mi tutor Gregorio Hernández. Desde aquí agradecerle sus conocimientos sobre grafos. También agradecerle encarecidamente su paciencia y comprensión para aceptar reuniones a horas complicadas, debido a mi trabajo. El desarrollo en Java ha sido sin duda lo más complicado de realizar, ya que cuandoempecé a construir la aplicación no conocía nada sobre este lenguaje. Tras la consulta de muchos manuales e Internet, poco a poco se fue gestando la herramienta de coloración. Muchas gracias a mi amigo Sergio Pascual, por haber probado todas y cada una de las versiones previas del proyecto y aconsejarme, sobre todo, en hacer un programa amigable y de fácil manejo. Finalmente, agradecer todo el apoyorecibido por mis amigos, compañeros de trabajo y familiares. En especial a mi mujer Laura. Muchas gracias por tener tanta paciencia y ser tan comprensivos.

Coloración de grafos

Índice

Índice

1 2

INTRODUCCIÓN ..................................................................................................1 TEORÍA DEGRAFOS...........................................................................................2 2.1 2.2 2.3 2.4 2.5 2.6 INTRODUCCIÓN ..................................................................................................2 DEFINICIONES ....................................................................................................3 GENERACIÓN DE GRAFOS .................................................................................10 COLORACIÓNDE GRAFOS .................................................................................27 JUEGOS DE COLORACIÓN ..................................................................................32 ESTRUCTURAS DE DATOS PARA LA REPRESENTACIÓN DE GRAFOS ....................33

3

DISEÑO.................................................................................................................35 3.1 INTRODUCCIÓN ................................................................................................35 3.2 DISEÑO DE ALTO NIVEL ...................................................................................38 3.2.1 Definición de los límites del sistema.......................................................38 3.2.2 Diagrama de casos de uso......................................................................39 3.2.3 Descripción de los actores ......................................................................41 3.2.4 Casos de uso............................................................................................41 3.3 DISEÑO DE BAJO NIVEL ....................................................................................53 3.3.1 Algoritmos de...