Invitación a la matemática discreta /
Matousek, Jirí
Invitación a la matemática discreta / Jirí Matousek, Jaroslav Nesetril. - Barcelona: Reverté, 2008 - 442 p.
CONTENIDO
1. Introducción y conceptos básicos 1
1.1. Un surtido de problemas 2
1.2. Números y conjuntos: notación 8
1.3. Inducción matemática y otras demostraciones 17
1.4. Funciones 27
1.5. Relaciones 35
1.6. Equivalencias 40
1.7. Conjuntos ordenados 43
2. Enumeración combinatoria 51
2.1. Aplicaciones y subconjuntos 51
2.2. Permutaciones y factoriales 57
2.3. Coeficientes binomiales 60
2.4. Estimación: una introducción 71
2.5. Estimación: la función factorial 80
2.6. Estimaciones: coeficientes binomiales 88
2.7. Principio de inclusión-exclusión 93
2.8. La dama del guardarropa 99
3. Grafos: una introducción 105
3.1. La noción de grafo; isomorfismo 105
3.2. Subgrafos, componentes, adyacencias 114
3.3. Secuencia de grados de un grafo 121
3.4. Grafos eulerianos 127
3.5. Un algoritmo para un recorrido euleriano 133
3.6. Grafos dirigidos eulerianos 137
3.7. 2-conectividad 142
4. Arboles 150
4.1. Definición y caracterizaciones de los árboles 150
4.2. Isomorfismo de árboles 157
4.3. Árboles generadores de un grafo 164
4.4. El problema del árbol generador minimal 169
4.5. Los algoritmos de Jarník y de Boruvka 175
5. Dibujar grafos en el plano 181
5.1. Dibujar en el plano y en otras superficies 181
5.2. Ciclos en grafos planares 189
5.3. La fórmula de Euler 196
5.4. Coloración de mapas: el problema de los cuatro colores 206
6. Doble conteo 218
6.1. Argumentos de paridad 218
6.2. Teorema de Sperner para anticadenas 228
6.3. Un resultado de la teoría extremal de grafos 235
7. Número de árboles generadores 240
7.1. El resultado 240
7.2. Una demostración vía secuencia de grados 241
7.3. Una demostración con vertebrados 244
7.4. Una demostración usando el código de Prufer 246
7.5. Una demostración con determinantes 249
8. Planos proyectivos finitos 258
8.1. Definición y propiedades básicas 258
8.2. Existencia de planos proyectivos finitos 268
8.3. Cuadrados latinos ortogonales 274
8.4. Aplicaciones combinatorias 278
9. Probabilidad y demostraciones probabilísticas 281
9.1. Demostraciones por conteo 281
9.2. Espacios de probabilidad finitos 288
9.3. Variables aleatorias y su esperanza 299
9.4. Varias aplicaciones 306
10. Funciones generadoras 316
10.1. Aplicaciones combinatorias de polinomios 316
10.2. Cálculo con series de potencias 320
10.3. Números de Fibonacci y la razón áurea 332
10.4. Árboles binarios 340
10.5. Sobre tirar el dado 345
10.6. Paseo aleatorio 347
10.7. Particiones de enteros 350
11. Aplicaciones del álgebra lineal 358
11.1. Diseños de bloques 358
11.2. Desigualdad de Fisher 364
11.3. Recubrir con grafos completos bipartitos 367
11.4. Espacio de ciclos de un grafo 370
11.5. Circulaciones y cortes: espacio de ciclos 375
11.6. Verificación probabilística 380
Apéndice: Prerrequisitos de álgebra 391
Bibliografía 399
Indicaciones para los ejercicios seleccionados 405
Indice de términos 429
9788429151800
MATEMATICA DISCRETA
GRAFOS
ARBOLES
DOBLE CONTEO
PLANOS PROYECTIVOS FINITOS
PROBABILIDAD
FUNCIONES GENERADORAS
519.1 M428
Invitación a la matemática discreta / Jirí Matousek, Jaroslav Nesetril. - Barcelona: Reverté, 2008 - 442 p.
CONTENIDO
1. Introducción y conceptos básicos 1
1.1. Un surtido de problemas 2
1.2. Números y conjuntos: notación 8
1.3. Inducción matemática y otras demostraciones 17
1.4. Funciones 27
1.5. Relaciones 35
1.6. Equivalencias 40
1.7. Conjuntos ordenados 43
2. Enumeración combinatoria 51
2.1. Aplicaciones y subconjuntos 51
2.2. Permutaciones y factoriales 57
2.3. Coeficientes binomiales 60
2.4. Estimación: una introducción 71
2.5. Estimación: la función factorial 80
2.6. Estimaciones: coeficientes binomiales 88
2.7. Principio de inclusión-exclusión 93
2.8. La dama del guardarropa 99
3. Grafos: una introducción 105
3.1. La noción de grafo; isomorfismo 105
3.2. Subgrafos, componentes, adyacencias 114
3.3. Secuencia de grados de un grafo 121
3.4. Grafos eulerianos 127
3.5. Un algoritmo para un recorrido euleriano 133
3.6. Grafos dirigidos eulerianos 137
3.7. 2-conectividad 142
4. Arboles 150
4.1. Definición y caracterizaciones de los árboles 150
4.2. Isomorfismo de árboles 157
4.3. Árboles generadores de un grafo 164
4.4. El problema del árbol generador minimal 169
4.5. Los algoritmos de Jarník y de Boruvka 175
5. Dibujar grafos en el plano 181
5.1. Dibujar en el plano y en otras superficies 181
5.2. Ciclos en grafos planares 189
5.3. La fórmula de Euler 196
5.4. Coloración de mapas: el problema de los cuatro colores 206
6. Doble conteo 218
6.1. Argumentos de paridad 218
6.2. Teorema de Sperner para anticadenas 228
6.3. Un resultado de la teoría extremal de grafos 235
7. Número de árboles generadores 240
7.1. El resultado 240
7.2. Una demostración vía secuencia de grados 241
7.3. Una demostración con vertebrados 244
7.4. Una demostración usando el código de Prufer 246
7.5. Una demostración con determinantes 249
8. Planos proyectivos finitos 258
8.1. Definición y propiedades básicas 258
8.2. Existencia de planos proyectivos finitos 268
8.3. Cuadrados latinos ortogonales 274
8.4. Aplicaciones combinatorias 278
9. Probabilidad y demostraciones probabilísticas 281
9.1. Demostraciones por conteo 281
9.2. Espacios de probabilidad finitos 288
9.3. Variables aleatorias y su esperanza 299
9.4. Varias aplicaciones 306
10. Funciones generadoras 316
10.1. Aplicaciones combinatorias de polinomios 316
10.2. Cálculo con series de potencias 320
10.3. Números de Fibonacci y la razón áurea 332
10.4. Árboles binarios 340
10.5. Sobre tirar el dado 345
10.6. Paseo aleatorio 347
10.7. Particiones de enteros 350
11. Aplicaciones del álgebra lineal 358
11.1. Diseños de bloques 358
11.2. Desigualdad de Fisher 364
11.3. Recubrir con grafos completos bipartitos 367
11.4. Espacio de ciclos de un grafo 370
11.5. Circulaciones y cortes: espacio de ciclos 375
11.6. Verificación probabilística 380
Apéndice: Prerrequisitos de álgebra 391
Bibliografía 399
Indicaciones para los ejercicios seleccionados 405
Indice de términos 429
9788429151800
MATEMATICA DISCRETA
GRAFOS
ARBOLES
DOBLE CONTEO
PLANOS PROYECTIVOS FINITOS
PROBABILIDAD
FUNCIONES GENERADORAS
519.1 M428