Matematicas discretas
Páginas: 23 (5746 palabras)
Publicado: 5 de agosto de 2010
Matemáticas Discretas Resúmenes de Teoría
Juan David González Cobas 7 de junio de 2004
II
Índice general
1. Combinatoria 1.1. Principios de la suma y el producto . . . . . . . 1.2. Muestras: permutaciones y combinaciones . . . 1.3. Teorema del binomio y coeficientes binomiales 1.4. Muestras con reemplazo . . . . . . . . . . . . 1.5. Permutaciones con elementos identificados . . 1.6.Generación ordenada de muestras . . . . . . . 1.6.1. Permutaciones en orden lexicográfico . 1.6.2. Combinaciones en orden lexicográfico . 1.7. El principio de inclusión-exclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1 1 2 5 8 12 13 14 15 15 19 19 19 20 20 22 23 23 24 25 26 27 28 30 32 32 33 34 34 34 36 38 40 41 41 42 47
2. Grafos 2.1. Conjuntos y relaciones . . . . . . . . . . . . . . 2.1.1. Producto cartesiano . . . . . . . . . . . . 2.1.2. Relaciones . . . . . . . . . . . . . . . . 2.1.3. Propiedades de las relaciones . . . . . . . 2.1.4. Clausura transitiva . . . . . . . . . . . . 2.2. Grafos . . . .. . . . . . . . . . . . . . . . . . . 2.2.1. Grafo dirigido y no dirigido . . . . . . . 2.2.2. Incidencia y grado . . . . . . . . . . . . 2.2.3. Representación como estructuras de datos 2.2.4. Caminos y ciclos . . . . . . . . . . . . . 2.3. Relaciones y grafos . . . . . . . . . . . . . . . . 2.4. Accesibilidad y conexión . . . . . . . . . . . . . 2.4.1. Matrices de accesibilidad . . . . . . . . .2.5. Algunos grafos especiales . . . . . . . . . . . . . 2.5.1. Grafos completos . . . . . . . . . . . . . 2.5.2. Torneos . . . . . . . . . . . . . . . . . . 2.5.3. Grafos bipartitos . . . . . . . . . . . . . 2.5.4. Caminos y ciclos . . . . . . . . . . . . . 2.5.5. Grafos cúbicos Q n . . . . . . . . . . . . 2.6. Arboles . . . . . . . . . . . . . . . . . . . . . . 2.6.1. Arboles enraizados . . . .. . . . . . . . 2.6.2. Arboles binarios . . . . . . . . . . . . . 2.7. Recorridos de grafos . . . . . . . . . . . . . . . 2.7.1. Recorridos de árboles binarios . . . . . . 2.7.2. Recorridos eulerianos . . . . . . . . . . . 2.7.3. Caminos hamiltonianos . . . . . . . . . . III
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.7.4. Recorridos en anchura y profundidad . . . . . . . . . . . . . 2.7.5. Caminos mínimos, MST y demás . . . . . . . . . . . . . . . 2.8. Planaridad y coloreado . . . . . . . . . . . . . . . . . . . . . . . . . 3. Recurrencias y notación asintótica 3.1. Objetivo . . . . . . . . . . . . . . 3.2. Recurrenciaslineales homogéneas 3.3. Notación asintótica . . . . . . . . 3.4. Recurrencias divide y vencerás . .
49 52 53 57 57 58 60 62
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
IV
Capítulo 1
Combinatoria
El objetivo de laCombinatoria, tal y como nosotros vamos a entenderla, consiste en calcular el número de elementos de ciertos conjuntos finitos. Es decir, nos ejercitaremos en el uso de determinadas técnicas de recuento.
1.1. Principios de la suma y el producto
Aunque en este capítulo emplearemos una gama muy variada de técnicas con el fin de calcular de cuántas formas pueden disponerse conjuntos de objetos, todas ellas...
Juan David González Cobas 7 de junio de 2004
II
Índice general
1. Combinatoria 1.1. Principios de la suma y el producto . . . . . . . 1.2. Muestras: permutaciones y combinaciones . . . 1.3. Teorema del binomio y coeficientes binomiales 1.4. Muestras con reemplazo . . . . . . . . . . . . 1.5. Permutaciones con elementos identificados . . 1.6.Generación ordenada de muestras . . . . . . . 1.6.1. Permutaciones en orden lexicográfico . 1.6.2. Combinaciones en orden lexicográfico . 1.7. El principio de inclusión-exclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1 1 2 5 8 12 13 14 15 15 19 19 19 20 20 22 23 23 24 25 26 27 28 30 32 32 33 34 34 34 36 38 40 41 41 42 47
2. Grafos 2.1. Conjuntos y relaciones . . . . . . . . . . . . . . 2.1.1. Producto cartesiano . . . . . . . . . . . . 2.1.2. Relaciones . . . . . . . . . . . . . . . . 2.1.3. Propiedades de las relaciones . . . . . . . 2.1.4. Clausura transitiva . . . . . . . . . . . . 2.2. Grafos . . . .. . . . . . . . . . . . . . . . . . . 2.2.1. Grafo dirigido y no dirigido . . . . . . . 2.2.2. Incidencia y grado . . . . . . . . . . . . 2.2.3. Representación como estructuras de datos 2.2.4. Caminos y ciclos . . . . . . . . . . . . . 2.3. Relaciones y grafos . . . . . . . . . . . . . . . . 2.4. Accesibilidad y conexión . . . . . . . . . . . . . 2.4.1. Matrices de accesibilidad . . . . . . . . .2.5. Algunos grafos especiales . . . . . . . . . . . . . 2.5.1. Grafos completos . . . . . . . . . . . . . 2.5.2. Torneos . . . . . . . . . . . . . . . . . . 2.5.3. Grafos bipartitos . . . . . . . . . . . . . 2.5.4. Caminos y ciclos . . . . . . . . . . . . . 2.5.5. Grafos cúbicos Q n . . . . . . . . . . . . 2.6. Arboles . . . . . . . . . . . . . . . . . . . . . . 2.6.1. Arboles enraizados . . . .. . . . . . . . 2.6.2. Arboles binarios . . . . . . . . . . . . . 2.7. Recorridos de grafos . . . . . . . . . . . . . . . 2.7.1. Recorridos de árboles binarios . . . . . . 2.7.2. Recorridos eulerianos . . . . . . . . . . . 2.7.3. Caminos hamiltonianos . . . . . . . . . . III
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.7.4. Recorridos en anchura y profundidad . . . . . . . . . . . . . 2.7.5. Caminos mínimos, MST y demás . . . . . . . . . . . . . . . 2.8. Planaridad y coloreado . . . . . . . . . . . . . . . . . . . . . . . . . 3. Recurrencias y notación asintótica 3.1. Objetivo . . . . . . . . . . . . . . 3.2. Recurrenciaslineales homogéneas 3.3. Notación asintótica . . . . . . . . 3.4. Recurrencias divide y vencerás . .
49 52 53 57 57 58 60 62
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
IV
Capítulo 1
Combinatoria
El objetivo de laCombinatoria, tal y como nosotros vamos a entenderla, consiste en calcular el número de elementos de ciertos conjuntos finitos. Es decir, nos ejercitaremos en el uso de determinadas técnicas de recuento.
1.1. Principios de la suma y el producto
Aunque en este capítulo emplearemos una gama muy variada de técnicas con el fin de calcular de cuántas formas pueden disponerse conjuntos de objetos, todas ellas...
Leer documento completo
Regístrate para leer el documento completo.