Iemiélichev V.A., Miélnikov O.I., Sarvánov V.I., Tyshkiévich R.Ió. Lecciones de teoría de grafos

448 с. (Spanish).

Белая офсетная бумага

Мягкая обложка

Аннотация

Esta obra constituye una extensa y detallada introducción a la teoría de grafos. La estructura del libro permite utilizarlo como instrumento en el estudio de las ciencias del comportamiento (cibernética, teoría de la información, teoría de sistemas, teoría de juegos), la teoría de conjuntos, la teoría de matrices, la teoría de grupos y otras disciplinas matemáticas. Los autores han dedicado una atención especial a la aplicación de la teoría de grafos... (Подробнее)

Índice

A nuestros lectores				9
Prólogo				10
Introducción				14
Capítulo 1. Conceptos básicos				16
1.1. Deﬁnició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 automorﬁsmos de un grafo				53
1.12. «Casi todo» grafo				58
Ejercicios				63
Capítulo 2. Árboles				66
2.1. Deﬁnició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. Isomorﬁsmo 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áﬁca				245
8.2. Criterios de sucesión gráﬁca				248
8.3. Realización de conectividad máxima para una sucesión gráﬁca				254
8.4. Realización hamiltoniana de una sucesión gráﬁca				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. Deﬁniciones 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. Deﬁniciones 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

Об авторе

Olieg Isidórovich Miélnikov

Doctor en Pedagogía, Doctor en Ciencias Físico-Matemáticas, profesor de la Universidad Estatal de Bielorrusia, laureado del Premio Estatal de la República de Bielorrusia. Sus intereses científicos se concentran alrededor de la teoría de grafos y la enseñanza de la matemática discreta en la enseñanza media y superior.