Introducción a la teoría de grafos: conceptos, algoritmos y aplicaciones
- Fecha de recepción oficial de la propuesta: 2022-12-16
- Fecha decisión editorial: 2024-04-10
- Tipo de revisión por pares: Simple - ciego
La editorial declara haber utilizado algún sistema de búsqueda de plagio.
Autores: Ismael Gutiérrez García, Yesneri Maider Zuleta Saldarriaga
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.
Palabras Clave:
Teoría de grafosColoración de grafosárboles teoría de grafosCategorías:
- MAT030000. MATEMÁTICAS > Estudio y enseñanza
- PB. Matemáticas
- JNU. Enseñanza de una materia específica
- 519.5. Ciencias naturales y matemáticas > Matemáticas > Probabilidades y matemática aplicada > Matemática Estadística
Ismael Gutiérrez García.
Yesneri Maider Zuleta Saldarriaga.
Matemática
Magister en Matemática
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
- ID: SIMEHEBOOKF8F7DHJ8A8ID7GIF7BGI
- Año de Publicación: 2024
- Presentación: PDF (Digital: descarga y online)
- Número absoluto de páginas: 164 Páginas
- ISBN13: 9789587896312
- PVP: COP 25000