PDF de programación - Matemática discreta en Haskell

Matemática discreta en Haskell

Departamento de Ciencias de la Computación e Inteligencia Artificial

Facultad de Matemáticas

Trabajo Fin de Grado

María Dolores Valverde Rodríguez

2

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra
hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. En cualquier explotación de la obra autorizada por la licencia
hará falta reconocer la autoría.

No comercial. La explotación de la obra queda limitada a usos no comerciales.

Compartir bajo la misma licencia. La explotación autorizada incluye la creación
de obras derivadas siempre que mantengan la misma licencia al ser divulgadas.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de es-
ta licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie
una carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305,
USA.

Índice general

Agradecimientos

Abstract

Introducción

7

9

11

1 Conjuntos

1.1
1.2

.

15
El TAD de los conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Representaciones de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.1 Conjuntos como listas ordenadas sin repetición . . . . . . . . . . 17
1.2.2 Definición de conjunto . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Subconjuntos .
Igualdad de conjuntos
1.2.4
. . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.5
Subconjuntos propios . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.6 Complementario de un conjunto . . . . . . . . . . . . . . . . . . 22
1.2.7 Cardinal de un conjunto . . . . . . . . . . . . . . . . . . . . . . . 22
1.2.8 Conjunto unitario . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2.9 Unión de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2.10 Intersección de conjuntos . . . . . . . . . . . . . . . . . . . . . . . 24
1.2.11 Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.12 Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.13 Variaciones con repetición . . . . . . . . . . . . . . . . . . . . . . 26
1.2.14 Conjuntos como listas sin repetición . . . . . . . . . . . . . . . . 26
1.2.15 Definición de conjunto . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.16 Subconjuntos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.2.17 Igualdad de conjuntos
. . . . . . . . . . . . . . . . . . . . . . . . 30
1.2.18 Subconjuntos propios . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.2.19 Complementario de un conjunto . . . . . . . . . . . . . . . . . . 31
1.2.20 Cardinal de un conjunto . . . . . . . . . . . . . . . . . . . . . . . 31
1.2.21 Conjunto unitario . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.2.22 Unión de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 32

.

3

4

Índice general

1.2.23 Intersección de conjuntos . . . . . . . . . . . . . . . . . . . . . . . 33
1.2.24 Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.2.25 Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.2.26 Variaciones con repetición . . . . . . . . . . . . . . . . . . . . . . 35
Elección de la representación de conjuntos . . . . . . . . . . . . . . . . . 35

1.3

2 Relaciones y funciones
.

2.1

.

.

.

.

. .

37
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Relaciones
2.1.1 Relación binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.2
Imagen por una relación . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3 Dominio de una relación . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.4 Rango de una relación . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.5 Antiimagen por una relación . . . . . . . . . . . . . . . . . . . . . 38
2.1.6 Relación funcional . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Relaciones homogéneas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Relaciones reflexivas
. . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2 Relaciones simétricas . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.3 Relaciones antisimétricas . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.4 Relaciones transitivas . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.5 Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . 42
2.2.6 Relaciones de orden . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.7 Clases de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . 43
Funciones .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Imagen por una función . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.1
2.3.2
Funciones inyectivas
. . . . . . . . . . . . . . . . . . . . . . . . . 45
. . . . . . . . . . . . . . . . . . . . . . . 45
Funciones sobreyectivas
2.3.3
2.3.4
Funciones biyectivas
. . . . . . . . . . . . . . . . . . . . . . . . . 46
Inversa de una función . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.5

.

.

.

.

.

.

2.2

2.3

3.1
3.2

3.3
3.4

3 Introducción a la teoría de grafos

49
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Definición de grafo .
El TAD de los grafos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
.
3.2.1 Grafos como listas de aristas . . . . . . . . . . . . . . . . . . . . . 51
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Generador de grafos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Ejemplos de grafos .
.
3.4.1 Grafo nulo . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2 Grafo ciclo .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
.
3.4.3 Grafo de la amistad . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Índice general

5

3.6 Morfismos de grafos .
.

3.5

3.7

3.8

3.4.4 Grafo completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.5 Grafo bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
.
3.4.6 Grafo estrella .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.7 Grafo rueda .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.8 Grafo circulante . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4.9 Grafo de Petersen generalizado . . . . . . . . . . . . . . . . . . . 62
3.4.10 Otros grafos importantes . . . . . . . . . . . . . . . . . . . . . . . 63
Definiciones y propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5.1 Definiciones de grafos . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.2 Propiedades de grafos
. . . . . . . . . . . . . . . . . . . . . . . . 73
3.5.3 Operaciones y propiedades sobre grafos . . . . . . . . . . . . . . 73
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.6.1 Morfismos .
3.6.2 Complejidad del problema de homomorfismo de grafos . . . . . 80
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.6.3
Isomorfismos .
3.6.4 Automorfismos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Caminos en grafos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
.
3.7.1 Definición de camino . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.7.2 Recorridos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.7.3 Caminos simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.7.4 Conexión .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
.
3.7.5 Distancia . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.7.6 Caminos cerrados . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.7.7 Circuitos . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.7.8 Ciclos . .
. .
3.7.9 Grafos acíclicos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Conectividad de los grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.8.1 Estar conectados por un camino . . . . . . . . . . . . . . . . . . . 97
3.8.2 Componentes conexas de un grafo . . . . . . . . . . . . . . . . . 97
3.8.3 Grafos conexos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.8.4 Excentricidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.8.5 Diámetro . .
3.8.6 Radio .
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
.
.
3.8.7 Centro .
3.8.8 Grosor .
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.8.9 Propiedades e invariantes por isomorfismos . . . . . . . . . . . . 106

.
.
.

.
.
.

.

.

.
.
.

6

Índice general

4 Matrices asociadas a grafos

109
Generador de grafos simples . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.1
4.2 Matrices de adyacencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.2.1 Definición y propiedades . . . . . . . . . . . . . . . . . . . . . . . 110
4.2.2 Propiedades básicas de las matrices . . . . . . . . . . . . . . . . . 111
4.2.3 Propiedades de las matrices de adyacencia . . . . . . . . . . . . . 111
4.2.4 Caminos y arcos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Sistemas utilizados

.

5 Apéndices

5.1
5.2 Mapa de decisiones de diseño en conjuntos
5.3 Mapa de decisiones de diseño en grafos

117
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
. . . . . . . . . . . . . . . . 119
. . . . . . . . . . . . . . . . . . 119

Bibliografía

Indice de definiciones

121

121

Agradecimientos

Quisiera agradecer a todas las personas que me han apoyado y prestado sus co-
nocimientos a lo largo de estos cuatro años del grado. Gracias a ellos, el esfuerzo ha
merecido la pena.

En primer lugar, me gustaría de