Elementos de matemática discreta

Elements of discrete mathematics

La matemática discreta engloba varias disciplinas: lógica proposicional, álgebra de Boole, combinatoria, teoría de conjuntos, estructuras algebraicas, teoría de autómatas finitos, grafos y árboles, entre otros. Aunque estas áreas no formaban un cuerpo estructurado, el auge de la informática y todo lo relacionado con los procesos digitales han convertido a la matemática discreta en una las ramas de la matemática de más interés.

El capítulo inicial de este libro tiene por objeto introducir las nociones básicas de la aritmética. En concreto, se presentan los números enteros y sus propiedades elementales. En el segundo capítulo se hace un repaso a la combinatoria, con los principios básicos de enumeración y las técnicas más clásicas: variaciones, combinaciones, permutaciones, entre otros.

En los capítulos tres y cuatro se presentan técnicas de enumeración más elaboradas, como las basadas en funciones generadoras y relaciones de recurrencia. Su aplicación más inmediata es la construcción de algoritmos para resolver de manera eficaz numerosos problemas, como pueden ser los de clasificación y búsqueda.

El capítulo quinto comienza con una introducción a la terminología y a los elementos básicos de la teoría de grafos. Contiene también alguno de los problemas clásicos de dicha teoría, como la existencia de circuitos eulerianos o ciclos hamiltonianos, los grafos planos y sus aplicaciones o la coloración de grafos.

Finalmente, en el capítulo seis se analizan los árboles, un tipo particular de grafos con una estructura particularmente simple y para los que existen resultados específicos, no aplicables a un grafo en general. A pesar de su aparente sencillez, los árboles tienen un gran número de aplicaciones, que van desde los algoritmos de búsqueda y clasificación de la información hasta problemas de optimización en investigación operativa.