MatDis

Matemática Discreta

Índice general
Prólogo

1

Capítulo 1. Números Enteros
1.1. Aritmética
1.2. Ordenando los enteros
1.3. Definiciones recursivas
1.4. El principio de inducción
1.5. Cociente y resto
1.6. Divisibilidad
1.7. El máximo común divisor y el mínimo común múltiplo
1.8. Factorización en primos
1.9. Ejercicios

3
3
5
7
9
12
14
15
19
22

Capítulo 2. Funciones y conteo
2.1. Funciones2.2. Funciones Suryectivas, Inyectivas y Biyectivas
2.3. Conteo
2.4. El Principio de las Casillas
2.5. ¿Finito o Infinito?
2.6. Ejercicios

25
25
26
29
31
32
35

Capítulo 3. Principios de conteo
3.1. Los principios de adición y multiplicación
3.2. Funciones, palabras y selecciones
3.3. Inyecciones como selecciones ordenadas sin repetición
3.4. Números binomiales
3.5. Selecciones desordenadas conrepetición
3.6. El teorema del binomio
3.7. Ejercicios

37
37
39
41
42
46
48
51

Capítulo 4. Aritmética Modular
4.1. Congruencias
4.2. Ecuación lineal de congruencia

53
53
56
iii

ÍNDICE GENERAL

iv

4.3. Teorema de Fermat
4.4. El criptosistema RSA
4.5. Ejercicios

57
58
60

Capítulo 5. Grafos
5.1. Grafos y sus Representaciones
5.2. Isomorfismo de grafos
5.3. Valencias
5.4. Caminos y ciclos
5.5.Árboles
5.6. Coloreando los vértices de un grafo
5.7. El algoritmo greedy para coloración de vértices
5.8. Ejercicios

61
61
63
66
67
71
73
75
78

Capítulo 6. Árboles
6.1. Contando las hojas de un árbol con raíz
6.2. Árboles expandidos y el problema MST
6.3. Ejercicios

81
81
84
88

Capítulo 7. Apéndice I
Más principios de conteo
7.1. Contando conjuntos de pares
7.2. El principio del tamiz

91
91
94Capítulo 8. Apéndice II
La función de Euler
8.1. La función de Euler
8.2. Una aplicación aritmética del principio del tamiz

97
97
100

Capítulo 9. Apéndice III
Permutaciones
9.1. Permutaciones
9.2. Ejercicios

103
103
106

Capítulo 10. Apéndice IV
Grafos planares
10.1. Grafos Planares
10.2. El problema del agua-luz-gas
10.3. El teorema de los cuatro colores

109
109
113
115

ÍNDICE GENERAL

vCapítulo 11. Apéndice V
Ejercicios adicionales
11.1. Números enteros
11.2. Funciones y conteo
11.3. Combinatoria
11.4. Congruencias
11.5. Grafos y árboles

119
119
123
124
126
129

Índice alfabético

137

Prólogo

Este cuadernillo tiene la intención de introducir a los alumnos en temas de matemática
discreta. Esta basado en el libro Discrete Mathematics de N. L. Biggs, Oxford University Press,1993. Tiene aportes de A. Tiraboschi y un apéndice de grafos planares escrito por D. Penazzi.

1

CAPíTULO 1

Números Enteros
1.1.

Aritmética

Todo lector de este libro conoce los enteros. En una etapa muy temprana de nuestras vidas
conocemos los números enteros positivos o “números naturales”
1, 2, 3, 4, 5, . . .
Más adelante introducimos el 0 (cero), y los enteros negativos
−1, −2, −3, −4, −5,. . .
En matemática generalmente no nos preocupamos por el significado lógico y/o filosófico de estos
objetos, pero necesitamos saber las propiedades que se supone que tienen. Si todos parten de
las mismas suposiciones entonces todos llegarán a los mismos resultados. Estos supuestos son los
llamados axiomas.
El punto de vista adoptado en este libro es el señalado antes. Aceptamos sin reparo queexiste un conjunto de objetos llamados enteros conteniendo los enteros positivos y los negativos,
y el cero, familiares en nuestra temprana educación y experiencia. El conjunto de enteros se
denotará por el símbolo especial Z. Las propiedades de Z serán dadas por una lista de axiomas,
a partir de las cuales seremos capaces de deducir todos los resultados sobre números enteros
que necesitaremos enlas cuestiones subsiguientes. Empezaremos listando aquellos axiomas que
tratan la suma y la multiplicación.
Adoptaremos las notaciones usuales a + b para la suma de dos enteros a y b, y a × b (o
frecuentemente solo ab) para su producto. Pensamos en + y × como operaciones que a un par
de enteros a y b les hacen corresponder un entero a + b y otro a × b. El hecho de que a × b y a + b
son enteros, y...