Elementos de matemática discreta

Sinopsis

La Matemática Discreta es la parte de la Matemática dedicada al estudio de los conjuntos discretos. Estas notas, fruto de varios años de docencia impartiendo la asignatura Matemáticas III, de la titulación en Ingeniería Industrial de la Universidad de La Rioja, sirven de iniciación a algunas de las ramas englobadas dentro de la Matemática Discreta, fundamentalmente las técnicas para contar y la teoría de grafos y árboles. Cada capítulo comienza introduciendo los resultados teóricos, salpicados de numerosos ejemplos. Además, cada capítulo tiene un apartado con problemas resueltos, y al final de cada tema hay una colección de problemas propuestos. El capítulo inicial tiene por objeto introducir las nociones básicas de la Aritmética. En concreto, se presentan los números enteros y sus propiedades elementales. Aunque se comienza con conceptos realmente básicos, se obtienen resultados y aplicaciones que ya no resultan evidentes, como la demostración por inducción o las consecuencias que se deducen del algoritmo de la división, como, por ejemplo, la resolución de ecuaciones diofánticas. 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, etc.). Una parte importante de este capítulo es la amplia colección de problemas, tanto resueltos como propuestos, que el lector puede encontrar. 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.