Prólogo 7
1. Algunos problemas modelados con grafos 9
2. Definiciones básicas sobre grafos 15
2.1. Algunos tipos de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2. Propiedades de los vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3. Algunas familias de grafos no dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4. Operaciones entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5. Isomorfía entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3. Representación matricial de grafos y conexión 41
3.1. Recorridos en grafos no dirigidos y dirigidos . . . . . . . . . . . . . . . . . . . . . . . 41
3.2. Matriz de adyacencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3. Matriz de incidencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4. Matriz laplaciana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5. Conexión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4. Grafos eulerianos, hamiltonianos y planos 63
4.1. Circuitos eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2. Algoritmos para hallar circuitos eulerianos . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3. Circuitos hamiltonianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4. Algoritmo para determinar todos los caminos hamiltonianos . . . . . . . . . . . . . . 72
4.5. Grafos planos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5. Emparejamientos y cubrimientos 83
5.1. Emparejamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2. Un algoritmo para aumentar un emparejamiento . . . . . . . . . . . . . . . . . . . . 89
5.3. Cubrimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.4. Algunos algoritmos de cubrimiento por vértice . . . . . . . . . . . . . . . . . . . . . 93
5.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6. Árboles 97
6.1. Árbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2. Árboles enraizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3. Algunos algoritmos para obtener un árbol generador mínimo . . . . . . . . . . . . . 104
6.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7. Coloración de grafos 121
7.1. Coloreando vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2. Algunas aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.3. Coloreando aristas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.4. Algunos algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
8. ANEXOS 147
8.1. Principio de inducción matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.2. Principio de adición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.3. Principio de las cajas o principio del palomar . . . . . . . . . . . . . . . . . . . . . . 152
