Estas notas son el 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. El contenido de esta asignatura trata sobre la Matemática Discreta, la parte de las Matemáticas dedicada al estudio de las conjuntos discretos. Para precisar el concepto de «discreto», sin entrar en definiciones rigurosas, podemos consultar el diccionario de la Real Academia de la Lengua Española.

Aquí encontramos que una cantidad discreta es aquella que consta de unidades o partes separadas unas de otras, como los árboles de un monte, los soldados de un ejército, los granos de una espiga, etc. Lo discreto puede verse como lo contrario a lo continuo, que el diccionario nos define de la siguiente forma: una cantidad continua es la que consta de unidades o partes que no están separadas unas de otras, como la longitud de una cinta, el área de una superficie, etc. Dicho de otro modo, lo discreto se puede contar y lo continuo se puede medir. Hablamos de contar el número de soldados, pero no de contar la longitud de una cinta.

Lo mismo se diría a la inversa, hablamos de medir la longitud de una cinta, pero no de medir el número de soldados. Aunque medir surge de una generalización del concepto de contar, entendemos cosas distintas. Al medir presuponemos que se puede obtener cualquier valor, pero no al contar. Así, ligado al concepto de discreto aparece el conjunto de los números naturales, N = {1, 2, 3, 4, . . .}, cuyos elementos nos resultan familiares, ya que van asociados a la idea de contar. Podríamos contar un número finito de cosas, pero también un número infinito de ellas. Podemos hablar entonces de un infinito asociado a los números naturales, que se llama infinito numerable, a diferencia de otros infinitos como el de los números reales R. Para aclarar un poco más esta idea podemos pensar en la representación de los números reales como los puntos de una recta. Una característica de este conjunto de números es que no existen huecos entre ellos, entre dos números reales cualesquiera existe una infinidad de números reales. Sin embargo, los números naturales están uniformemente espaciados en esa imaginaria recta.

Por ejemplo, entre el 1 y el 2 hay un salto de una unidad y no existen otros números naturales comprendidos entre ellos. Esta es la diferencia entre los números naturales N y los números reales R, entre las Matemáticas de lo discreto y las Matemáticas de lo continuo, entre la Matemática Discreta y el Cálculo. 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, etc. 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.

Prueba de ello es que aparece en la mayoría de los planes de estudio de las enseñanzas de Matemáticas e Ingeniería. Otros indicativos que dan fe de la vitalidad de la Matemática Discreta es el número de publicaciones recientes (en papel o digitales) sobre cualquiera de las disciplinas citadas anteriormente o la amplitud y variedad de sus aplicaciones. Como muestra, se pueden consultar las páginas dedicadas a la Matemática Discreta en la enciclopedia virtual Wikipedia, [26], [27] o la correspondiente página del proyecto MathWorld, [28], o cualquiera de las numerosas referencias y enlaces que en ellas aparecen. Las notas que presentamos a continuación 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. Somos conscientes de que el texto es incompleto pues no incluye algunos temas tan atractivos como la aritmética modular y sus aplicaciones en criptografía.

No obstante, la selección de temas incluídos en este libro tiene gran interés y numerosas aplicaciones. Además, se ha pretendido escribir un texto autocontenido y que no requiera al lector de conocimientos matemáticos profundos. Se ha hecho un esfuerzo por presentar los temas de forma sencilla, pero rigurosa. 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, como en cualquier libro de Matemáticas, 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 [13, 16, 17].

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.

En cuanto a las referencias, no hemos pretendido dar un listado exhaustivo de textos relacionados con la Matemática Discreta. Como hemos comentado anteriormente, se trata de una extensa y activa rama de las Matemáticas, donde podemos encontrar tanto textos clásicos, publicaciones de divulgación o artículos de investigación. La bibliografía que hemos incluido al final del texto ha sido seleccionada simplemente por nuestra experiencia personal: son los libros que hemos manejado para preparar e impartir las clases. En cuanto a los libros clásicos, que podrían considerarse como libros de texto para seguir un curso de Matemática Discreta, podemos destacar los de Biggs [2], Foulds [8], García Merayo [10], Grimaldi [14], Kalmanson [15], Rosen [23] o Tucker [24]. Hemos citado también otras publicaciones, más enfocadas a apoyar la docencia relacionada con la Matemática Discreta, como [4], [6], [9] o [11]. Las referencias electrónicas que hemos incluido son una pequeña muestra de lo que el lector puede encontrar por su cuenta buscando en Internet. Una lista más amplia de referencias electrónicas puede encontrarse en [9].

Por último no debemos olvidarnos de aquellas personas que de un modo u otro han contribuído a que estas notas sean una realidad. Especialmente Mari Carmen Mínguez, cuyas notas manuscritas de la asignatura de Matemática Discreta para la Licenciatura en Matemáticas han sio el embrión de lo que aquí se presenta. Juan Luis Varona, por sus sugerencias y su inestimable ayuda en la resolución de problemas relacionados con el LATEX. José Luis Ansorena, Manuel Bello, Óscar Ciaurri y Pilar Benito, quienes, sin saberlo, han sido fuente de inspiración para alguno de los problemas que se incluyen. Finalmente, el resto de compañeros del Departamento de Matemáticas y Computación por hacer nuestro trabajo agradable