Introducción a la teoría de grafos: conceptos, algoritmos y aplicaciones
Ismael Gutiérrez García · Yesneri Maider Zuleta Saldarriaga
Editorial Universidad del Norte
Sinopsis
La teoría de grafos o teoría de gráficas es considerada una de las ramas más importantes de las matemáticas modernas. Tiene muchas aplicaciones, ya que es posible utilizar grafos para resolver problemas en diversas áreas. En este libro se dan a conocer definiciones y nociones básicas, se definen formalmente los diferentes tipos de grafos, se desarrolla el tema de representación matricial, se clasifican los distintos tipos de paseos, se introduce la idea de conexidad, se presentan algunas definiciones y resultados alrededor de los grafos eulerianos y hamiltonianos, así como los conceptos de emparejamiento y cubrimiento en un grafo, y se explica un tipo especial de grafo denominado árbol. Cada capítulo cuenta con ejemplos y una sección de ejercicios.
Sobre los autores
Ismael Gutiérrez García
Yesneri Maider Zuleta Saldarriaga
Matemática
Magister en Matemática
Contenido
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
Materias
Palabras clave
BISAC
- MAT030000. MATEMÁTICAS > Estudio y enseñanza
Thema
- PB. Matemáticas
- JNU. Enseñanza de una materia específica
Dewey
- 519.5. Ciencias naturales y matemáticas > Matemáticas > Probabilidades y matemática aplicada > Matemática Estadística
Declaración de Prestigio Académico
Lo que la editorial declara sobre la evaluación de esta obra.