Introducción a la teoría de grafos: conceptos, algoritmos y aplicaciones

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