| A nuestros lectores | 9
|
| Prólogo | 10
|
| Introducción | 14
|
| Capítulo 1. Conceptos básicos | 16
|
| 1.1. Definición de grafo | 16
|
| 1.2. Subgrafos | 25
|
| 1.3. Operaciones con grafos | 27
|
| 1.4. Recorridos, circuitos, componentes conexas | 30
|
| 1.5. Grados de los vértices de un grafo | 35
|
| 1.6. Matrices relacionadas con un grafo | 36
|
| 1.7. Grafos regulares | 41
|
| 1.8. Características métricas de un grafo | 44
|
| 1.9. Teorema de König | 47
|
| 1.10. Grafo de línea | 49
|
| 1.11. Grupo de automorfismos de un grafo | 53
|
| 1.12. «Casi todo» grafo | 58
|
| Ejercicios | 63
|
| Capítulo 2. Árboles | 66
|
| 2.1. Definición de árbol | 66
|
| 2.2. Teorema de Kirchhoff | 71
|
| 2.3. Bosque de expansión de peso mínimo | 74
|
| Ejercicios | 78
|
| Capítulo 3. Matroides y transversales | 80
|
| 3.1. Elementos de la teoría de matroides | 80
|
| 3.2. Matroide dual | 85
|
| 3.3. Ejemplos de matroides | 88
|
| 3.4. Isomorfismo de matroides | 91
|
| 3.5. Representaciones de matroides | 92
|
| 3.6. Matroides binarios | 98
|
| 3.7. Transversales | 107
|
| 3.8. Algoritmo voraz | 113
|
| 3.9. Unión e intersección de matroides | 116
|
| Ejercicios | 122
|
| Capítulo 4. Independencia y recubrimientos | 124
|
| 4.1. Conjuntos independientes y recubrimientos | 124
|
| 4.2. Cliques | 134
|
| 4.3. Problemas del clique, del encaje isomorfo y del subgrafo isomorfo | 138
|
| 4.4. Interpretación de los conjuntos independientes | 140
|
| 4.5. Emparejamientos | 146
|
| 4.6. Emparejamientos en un grafo bipartito | 148
|
| 4.7. Grafos bipartitos y familias de subconjuntos | 153
|
| 4.8. Emparejamientos y recubrimientos | 155
|
| Ejercicios | 157
|
| Capítulo 5. Conectividad | 159
|
| 5.1. Conectividad por vértices y conectividad por aristas | 159
|
| 5.2. Grafos biconexos | 164
|
| 5.3. Teorema de Menger | 173
|
| Ejercicios | 177
|
| Capítulo 6. Planaridad | 178
|
| 6.1. Grafos planos y grafos planares | 178
|
| 6.2. Caras de un grafo plano. Fórmula de Euler | 181
|
| 6.3. Grafos triangulares | 186
|
| 6.4. Criterios de planaridad | 188
|
| 6.5. Dualidad y planaridad | 199
|
| 6.6. Algoritmo de encaje de un grafo en el plano | 206
|
| 6.7. Características de los grafos no planares | 215
|
| Ejercicios | 219
|
| Capítulo 7. Recorridos | 224
|
| 7.1. Grafos eulerianos | 224
|
| 7.2. Grafos hamiltonianos | 229
|
| Ejercicios | 242
|
| Capítulo 8. Sucesiones de grados | 244
|
| 8.1. Sucesión gráfica | 245
|
| 8.2. Criterios de sucesión gráfica | 248
|
| 8.3. Realización de conectividad máxima para una sucesión gráfica | 254
|
| 8.4. Realización hamiltoniana de una sucesión gráfica | 257
|
| 8.5. Grafos divididos | 259
|
| 8.6. Grafos umbrales | 261
|
| 8.7. Descomposición umbral de un grafo | 266
|
| 8.8. Conjunto de grados de un grafo | 271
|
| Ejercicios | 273
|
| Capítulo 9. Coloraciones | 275
|
| 9.1. Coloración válida | 275
|
| 9.2. Estimaciones del número cromático | 279
|
| 9.3. Polinomio cromático | 286
|
| 9.4. Coloración de aristas | 290
|
| 9.5. Relación entre las descomposiciones de un grafo en matroides y sus coloraciones | 295
|
| 9.6. Coloración de grafos planares | 298
|
| 9.7. Problema de los cuatro colores | 304
|
| 9.8. Otros enfoques de la coloración de grafos | 308
|
| 9.9. Grafos perfectos | 312
|
| 9.10. Grafos cordales | 317
|
| Ejercicios | 323
|
| Capítulo 10. Grafos dirigidos | 325
|
| 10.1. Definiciones básicas | 325
|
| 10.2. Grado de salida y grado de entrada | 330
|
| 10.3. Recorridos | 333
|
| 10.4. Caminos simples | 337
|
| 10.5. Base y núcleo | 341
|
| Ejercicios | 345
|
| Capítulo 11. Hipergrafos | 347
|
| 11.1. Definiciones y propiedades fundamentales | 347
|
| 11.2. Conjuntos independientes | 353
|
| 11.3. Coloraciones | 356
|
| 11.4. Realización de un hipergrafo | 360
|
| Ejercicios | 366
|
| Capítulo 12. Algoritmos | 369
|
| 12.1. Conceptos y resultados preliminares | 369
|
| 12.2. Búsqueda en profundidad | 376
|
| 12.3. Búsqueda de las componentes biconexas | 380
|
| 12.4. Bosque de expansión de peso mínimo | 389
|
| 12.5. Caminos simples más cortos | 398
|
| 12.6. Emparejamientos máximos y problema de asignación | 410
|
| 12.7. Problemas intratables | 421
|
| Ejercicios | 431
|
| Bibliografía | 433
|
| Índice de autores | 435
|
| Índice de materias | 437
|
Vladímir Alexiéevich Yemiélichev Doctor en Ciencias Físico-Matemáticas, profesor de la Universidad Estatal de Bielorrusia, laureado del Premio Estatal de la República de Bielorrusia, miembro de la Academia de Ciencias de Nueva York, miembro del consejo de redacción de varias revistas teórico-científicas internacionalmente reconocidas. Sus intereses científicos están relacionados con la optimización discreta, la combinatoria poliédrica, la teoría de grafos, la estabilidad y la regularización de problemas discretos con múltiples criterios. Es autor y coautor de varias monografías dedicadas a estas temáticas.
Olieg Isidórovich Miélnikov Dóktor en Ciencias Físico-Matemáticas y Pedagogía. Profiéssor de la Facultad de Mecánica y Matemática de la Universidad Estatal de Bielorrusia. Laureado del Premio Estatal de la República de Bielorrusia. Reconocido especialista en teoría de grafos y métodos de enseñanza de la matemática discreta en la educación media y superior.
O. I. Miélnikov es autor y coautor de los libros «Teoría de grafos en problemas recreativos resueltos», «Lecciones de teoría de grafos», «Teoría de grafos para todos» (editados en español en Editorial URSS; 2011,2026); son de destacar, asimismo, sus libros «Aventuras en el país de los grafos» (URSS, 2006), «La enseñanza de la matemática discreta» (URSS, 2008), «Exercises in graph theory», «Informática. Métodos de algoritmización», «Matemática para economistas con aplicación del paquete Mathcad». Por su libro «Lecciones de teoría de grafos» fue galardonado con el Premio Estatal de la República de Bielorrusia.
Vladímir Ivánovich Sarvánov 
Reguina Iósifovna Tyshkévich 
