Download Silabus Matematica Discreta Archivo - Virtual Udabol
Document related concepts
Transcript
FACULTAD DE INGENIERIA RED NACIONAL UNIVERSITARIA SYLLABUS Facultad de Ingeniería Ingeniería de Sistemas TERCER SEMESTRE Gestión Académica I/2017 1 FACULTAD DE INGENIERIA UDABOL UNIVERSIDAD DE AQUINO BOLIVIA Acreditada como PLENA mediante R. M. 288/01 VISION DE LA UNIVERSIDAD Ser la Universidad líder en calidad educativa. MISION DE LA UNIVERSIDAD Desarrollar la Educación Superior Universitaria con calidad y competitividad al servicio de la sociedad. 2 FACULTAD DE INGENIERIA SYLLABUS GENÉRICO Asignatura: Código: Requisito: Carga Horaria: Créditos: MATEMATICA DISCRETA MAT 201 A MAT 111 A 60 6 I. OBJETIVOS GENERALES DE LA ASIGNATURA. Desarrollar los conceptos fundamentales de la matemática discreta, estableciendo su importancia en las ciencias de la computación, a través de ejemplos de aplicación practica. La enseñanza de los contenidos fundamentales de la Matemática Discreta y el uso de su terminología son imprescindibles en todos los cursos de nivel universitario, ya que van asociadas al progreso de las ciencias y la unidad conceptual, desde el punto de vista instructivo la asignatura introduce la terminología y conocimientos que trata con diferentes tipos de objetos, los cuales pueden a su vez, combinarse de maneras diferentes. II. PROGRAMA ANALÍTICO DE LA ASIGNATURA. TEMA 1. TEORIA DE CONJUTOS Conjuntos Conjunto universal Conjunto vacio Subconjuintos Operaciones con conjuntos Complemento de conjuntos Intersección de conjuntos Unión de conjuntos Leyes de Morgan Diferencia de conjuntos TEMA 2. RECUENTO Conjunto producto Variaciones - Combinaciones R - eto Ordenado R - eto No Ordenado Métodos secuencial de Recuento de os r- etos Ordenados que Poseen Una propiedad Dada Número de r - etos Ordenados Con Repetición (Variaciones Con Repetición) Número de r - etos Ordenados Sin Repetición (Variaciones Sin Repetición) Número de r - etos No Ordenados Con Repetición (Combinaciones Con Repetición) Número de r - etos No Ordenados Sin Repetición (Combinaciones Sin Repetición) Extensión de los Métodos de Recuento Fórmula de inclusión y de Exclusión Representación de la Fórmulas que Poseen Propiedades Caso de Subconjuntos No Específicos Método General de Cribado en la Teoría de los números Enteros 3 FACULTAD DE INGENIERIA Función de Euler Función de Moebius Criba de Erastostenes TEMA 3. TEORIA DE GRAFOS Introducción Definición de Grafo. Tipos de Representación de Grafo Notación de Berge Definición de Grafo 2. Orden de un Grafo Vértice. Arco. Extremidades. Bucles Arcos Adyacentes. Vertices Adyacentes Arco Incidente a un Subconjunto de Vértices Semi-grado de un Subconjunto Grafo parcial de un Grafo. Subgrafo de un Grafo Grafo Simétrico. Grafo Antisimétrico. Grafo Completo. Grafo Lleno. Grafo Lleno Asociado Grafo Complementario de un Grafo. Noción de Camino. Camino Simple. Camino Elemental Circuito. Circuito Elemental. Circuito Simple Longitud de un Camino Camino Hamiltoniano. Circuito Hamiltoniano Grafo Fertemente Conexo Cierre Transitivo Descomposisción de un Grafo en Subgrafos Fuertemente Conexos Másimos Método Para Descomponer un Grafo en Subgrafos Fuertemente Conexos Máximos Existencia y Recuento de Caminos Función Ordinal de un Grafo sin Circuito. Función de Grundy Estabilidad interna. Nucleo de un Grafo Conceptos No Orientados Número Cromatica Tribu. Tribu Máxima Grafo p-Coloreado. Grafo p-Aplicado Multigarafo no Orientado o p-Grafo no Orientado. p-Grafos Planos TEMA 4. ARBOLES Arborescencia Arbol. Arboles Generados Mínimos Algoritmos de Búsqueda en grafo Retículo Finito TEMA 5. ENUMERACION Introducción Método de la Composición Latina Enumeración de lo Caminos Enumeración de los Caminos Elementales Enumeración de los Circuitos Elementales Enumeración de las Secuencias Con Repetición Enumeración de los Factores de un Grafo 4 FACULTAD DE INGENIERIA III. BIBLIOGRAFIA RALPH GRIMALDI, "Matemática discreta y Combinatoria", Iberoamericana. 576p., 1992 Segunda Edición, México, Addison-Wesley KOLMAN-BUSBY-ROSS, "Estructuras de matemática discreta para la computación” KENNETH A. ROSS – Charles R.B. Wright, “ Matemáticas Discretas ” Segunda Edición, Impreso en México, Prentice All, Inc. 672p., 1990 WINFRIED K. GRASSMANN JEAN-PAUL TREMBLAY, “Matemática Discreta y Lógica.” SEYMOUR LIPSCHTZ, PH. D., “ Matemáticas finitas”, Primera Edición Español, Impreso en Colombia, Mc GRAW – HILL BOOK COMPANY, INC., USA , 344p. ( Serie de Compendios Schaum), 1977 COLMAN – BUSBY – ROSS, "Estructuras de matemática discreta para la computación”, tercera edición, México, 1995. GRIMALDI R, “Combinatoria y Matemática Discreta”, Editorial Addison Wesley. ROSS, “Estructuras de Matemáticas Discretas”, Editorial Prentice Hall 5 FACULTAD DE INGENIERIA IV. CONTROL DE EVALUACIONES 1° evaluación parcial Fecha Nota 2° evaluación parcial Fecha Nota Examen final Fecha Nota APUNTES 6 FACULTAD DE INGENIERIA WORK PAPER # 1 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Métodos Combinatorios DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 7 FACULTAD DE INGENIERIA MÉTODOS COMBINATORIOS Técnicas básicas Sea S un conjunto finito no vacío. Se designar por | S | al cardinal de S, es decir, el número de elementos de S. En particular | CV | = 0 (CV es el conjunto vacío). Principio de Adición Sean A1, A2, ... , An conjuntos finitos tales que Ai INT Aj = CV (INT es la intersección) para cada i # j, donde i, j pertenecen a {1, 2, ... , n}, entonces: | A1 U A2 U ... U An | = | A1 | + | A2 | + ... + | An | En el lanzamiento de dos dados ¿De cuántas formas se pueden obtener un siete o un ocho? Obtener un siete = A = { (1, 6) , (2, 5) , (3, 4) , (4, 3) , (5, 2) , (6, 1) } Obtener un ocho = B = { (2, 6) , (3, 5) , (4, 4) , (5, 3) , (6, 2) } | A U B | = | A | + | B | = 6 + 5 = 11 El experimento de lanzar una moneda al aire tres veces ¿De cuántas formas se puede obtener una, dos o tres caras? Una cara = A = { (C, +, +) , (+, C, +) , (+, +, C) } Dos caras = B = { (+, C, C) , (C, +, C) , (C, C, +) } Tres caras = C = { (C, C, C) } |AUBUC|=|A|+|B|+|C|=3+3+1=7 Principio de Multiplicación Sea A1, A2, ... , An una colección de conjuntos finitos no vacíos, entonces: | A1 x A2 x ... x An | = | A1 | · | A2 | · ... · | An | Formación de placas de matrícula ¿Cuántas placas de matrícula pueden formarse con cuatro letras (en un alfabeto de 26 letras) seguidas de tres números? Cuatro letras = A = B = C = D = 26 Tres dígitos = E = F = G = 10 | A x B x C x D x E x F x G | = | A |·| B |·| C |·| D |·| E |·| F |·| G | = 26·26·26·26·10·10·10 = 456976000 Se dispone de una baraja de 40 cartas 8 FACULTAD DE INGENIERIA Se extraen 4 cartas por dos procedimientos: a) sin devolución de la carta extraída b) con devolución en cada extracción. 1ª carta = A , 2ª carta = B , 3ª carta = C , 4ª carta = D a) | A x B x C x D | = | A |·| B |·| C |·| D | = 40 · 39 · 38 · 37 = 2193360 b) | A x B x C x D | = | A |·| B |·| C |·| D | = 40 · 40 · 40 · 40 = 2560000 Formación de números ¿Cuántos números naturales distintos existen entre 5000 y 10000 y tienen todas sus cifras diferentes? 1º dígito (5...9) = A , 2º dígito (0...9) = B , 3º dígito (0...9) = C , 4º dígito (0...9) = D | A x B x C x D | = | A |·| B |·| C |·| D | = 5 · 9 · 8 · 7 = 2520 Principio de Distribución Sean m, n y p números naturales. Si se distribuyen np + m objetos en n cajas entonces alguna caja deberá contener al menos p + 1 objetos. 9 FACULTAD DE INGENIERIA WORK PAPER # 2 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Elementos Combinatorios DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 10 FACULTAD DE INGENIERIA ELEMENTOS COMBINATORIOS Permutaciones Cualquier arreglo de un conjunto de n objetos en un orden dado se llama permutación de los objetos (tomados todos al mismo tiempo). Se designa por: P( n ) = n! = n · (n - 1) · (n - 2) · ... · 2 · 1 Formaciones con personas ¿De cuántas maneras puede organizarse un grupo de 7 personas: a) en una fila de 7 asientos? b) alrededor de una mesa redonda? a) P( 7 ) = 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 b) P( 7 - 1 ) = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720 Permutaciones con repetición Con frecuencia deseamos encontrar el número de permutaciones de objetos, algunos de los cuales son iguales. La fórmula general es (r es el número de elementos repetidos): PR( n ) = n! / n1! · n2! · ... · nr! Permutaciones con letras ¿Cuántas permutaciones pueden formarse con las letras de la palabra "radar"? Repeticiones: r = 2 , a = 2 PR( 5 ) = 5! / 2! · 2! = 5 · 4 · 3 · 2 · 1 / 2 · 1 · 2 · 1 = 120 / 4 = 30 Permutaciones con banderas ¿Cuántas señales de 6 banderas pueden formarse con 4 banderas rojas y 2 azules? Repeticiones: rojas = 4 , azules = 2 PR( 6 ) = 6! / 4! · 2! = 6·5·4·3·2·1 / 4·3·2·1·2·1 = 720 / 48 = 15 Variaciones Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una variación de orden r es una lista ordenada de n elementos distintos tomados de r en r. Su fórmula es: V( n, r ) = n! / (n - r)! Variaciones con bolas Una urna contiene 8 bolas. Encontrar el número de muestras ordenadas de magnitud 3. 11 FACULTAD DE INGENIERIA V( 8, 3 ) = 8! / (8 - 3)! = 8! / 5! = 8·7·6·5·4·3·2·1 / 5·4·3·2·1 = 40320 / 120 = 496 Variaciones con números ¿Cuántos números de 3 dígitos pueden formarse con las cifras 2, 3, 5, 6, 7 y 9? V( 6, 3 ) = 6! / (6 - 3)! = 6! / 3! = 6·5·4·3·2·1 / 3·2·1 = 720 / 6 = 120 Variaciones con repetición Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una variación con repeticiones de orden r es una lista ordenada de n elementos tomados de r en r. Su fórmula es: VR( n, r ) = n^r Los catorce en las quinielas En el juego de las quinielas, ¿cuál es el número mínimo de columnas que han de rellenarse para acertar con seguridad los catorce signos? VR( 3, 14 ) = 3^14 = 4728969 Formaciones de palabras En un alfabeto formado por las letras (a, b, c, d), ¿cuántas palabras distintas de diez letras pueden formarse? VR( 4, 10) = 4^10 = 1048576 Combinaciones Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una combinación de orden r es una lista de elementos distintos, donde el orden no se tiene en cuenta. Se formula: C( n, r ) = n! / r! . (n - r)! El juego del póker ¿Cuántas manos de póker distintas (5 cartas) pueden formarse con una baraja de 52 cartas? C( 52, 5 ) = 52! / 5!·47! = 52·51·50·49·48 / 5·4·3·2·1 = 311875200 / 120 = 2598960 Comité de personas ¿De cuántas maneras puede formarse un comité que consta de 3 hombres y 2 mujeres, a partir de 7 hombres y 5 mujeres? A = Hombres = C( 7, 3 ) = 7! / 4! · 3! = 210 / 6 = 35 B = Mujeres = C( 5, 2 ) = 5! / 3! · 2! = 20 / 2 = 10 | A x B | = | A | ú | B | = 35 · 10 = 350 Combinaciones con repetición 12 FACULTAD DE INGENIERIA Sea un conjunto finito con n elementos (n > 0) y r un número natural. Una combinación con repetición de orden r es una lista ordenada de n elementos en donde los elementos pueden ser iguales. Su fórmula es: CR( n, r ) = C( n + r - 1, r ) Distribución de objetos ¿De cuántas formas se pueden distribuir 10 canicas azules en 5 bolsas distintas? CR( 5, 10 ) = C( 5 + 10 - 1, 10 ) = C( 14, 10 ) = 87178291000 / 87091200 = 1001 Suma de dígitos ¿Cuántos números hay en el conjunto {1, 2, ..., 1000 } que tengan la propiedad de que la suma de sus dígitos sea 5? CR( 3, 5 ) = C( 3 + 5 - 1, 5 ) = C( 7, 5 ) = 5040 / 240 = 21 Resumen del empleo de elementos combinatorios Se eligen r objetos de un Número de selecciones Número de selecciones conjunto de n ordenadas no ordenadas ========================================================= No están permitidas las repeticiones V(n,r) = n!/(n-r)! C(n,r) = n!/(n-r)!·r! Están permitidas las repeticiones VR(n,r) = n^r CR(n,r) = C(n+r-1,r) 13 FACULTAD DE INGENIERIA WORK PAPER #3 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Teorema del binomio DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 14 FACULTAD DE INGENIERIA TEOREMA DEL BINOMIO Se considera la expresión (x + y)^n . Su desarrollo puede obtenerse mediante la fórmula: (x + y)^n = Sumatorio de r ( 0 ... n ) en C( n, r ) · x^n-r · y^r Desarrollo de un binomio Calcúlese el coeficiente de x^6 en el desarrollo de (x - 3)^11. C( 11, 6 ) · x^6 · (-3)^5 = 462 · x^6 · (-243) = -112266x^6 Fórmula de Pascal Si n y r son enteros tales que 1 <= r <= n - 1, entonces: C( n, r ) = C( n - 1, r ) + C( n - 1, r - 1 ) La fórmula de Pascal da un método para el cálculo de los coeficientes binómicos, dado el valor inicial C( n, 0 ) = C( n, n ) = 1, para todo n >= 0. Los coeficientes de sucesivas potencias (x + y)^n se pueden distribuir en una figura que se conoce como triángulo de Pascal, en el cual se tiene: El primer y el último elemento de cada fila es 1. Cualquier otro número del tri ngulo se puede obtener sumando los dos números que aparecen encima de él. Fórmula de Leibnitz Se aplica a los coeficientes del tipo multinómicos: (x1 + x2 + ... + xk)^n = n! / n1! · n2! · ... · nk! Cálculo de un coeficiente Calcúlese el coeficiente del término a^3b^2c^4 del desarrollo de (a + b + c + d)^9. 9! / 3!·2!·4!·0! = 9·8·7·6·5 / 3·2·1·2·1·1 = 15120 / 12 = 1260 15 FACULTAD DE INGENIERIA WORK PAPER # 4 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Conteo DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 16 FACULTAD DE INGENIERIA CONTEO 1. Cuántos números de cinco cifras se pueden formar utilizando los dígitos 123567 y 9 con la condición de que: Todas las cifras sean distintas Todas las cifras sean iguales El número obtenido sea múltiplo de 4 El número obtenido sea capicúa El número obtenido sea par y capicúa 2. De una caja que contiene 122 bolillos numerados de 1 a 122, se extraen 5. Cuántos posibles resultados hay si: Los bolillos se extraen uno a la vez. Los bolillos se extraen todos juntos 3. De cuántas maneras se pueden ubicar 22 bolitas indistinguibles en 59 cajas numeradas con la condición de que cada caja debe contener a lo sumo una bolita. 4. Suponga que existen 10 caminos desde oz, hasta la tierra del centro, y 5 caminos desde la tierra del centro a la isla de la fantasía. a) De cuantas maneras diferentes se puede ir de oz a la isla de la fantasía pasando por la tierra del centro. b) Cuántas rutas del tipo oz del centro isla de la fantasía, tierra del centro, oz hay?, si se exige que no se repita el camino de oz a la isla de la fantasía en el viaje de regreso 5. Se tiene número enteros del 5 al 200 ambos inclusive a) b) c) d) cuántos números hay Cuántos números impares hay Cuántos son mayores que 72 Cuántos contienen el dígito 7 17 FACULTAD DE INGENIERIA WORK PAPER # 5 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Grafos DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 18 FACULTAD DE INGENIERIA GRAFOS Definición Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas). Otros conceptos básicos son: Dos vértices son adyacentes si comparten la misma arista. Los extremos de una arista son los vértices que comparte dicha arista. Un grafo se dice que es finito si su número de vértices es finito. Representación gráfica de un grafo Dado un grafo G = (V, E) donde V = {a, b, c, d, e} y E = {ab, bc, be, cd, de, ad}, constrúyase una representación gráfica de G. a /\ / \ b /-------\--------/ e \ \ / \ \/ \------c d Debido a lo dificultoso de realizar dibujos mediante el lenguaje HTML, he propuesto este ejemplo para que en los ejemplos sucesivos, se haga una representación gráfica de un grafo uniendo los vértices con las aristas dadas, tal y como se ha hecho en el dibujo. Clases de grafos Un multigrafo es un grafo con varias aristas entre dos v‚rtices. Un pseudografo es un grafo en el que hay aristas (lazos) que tienen el mismo extremo. Un digrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha. Los multidigrafos o pseudomultidigrafos son combinaciones de los anteriores. Identificación de grafos a) V = {a, b, c, d} y E = {aa, ab, bc, cd, dd} Representa un pseudografo b) V = {a, b, c, d, e, f} y E = {b->a, b->c, c->d, d->e, e->f} Representa un digrafo c) V = {a, b, c, d} y E = {ab, 2*bc, cd, 2*da} Representa un multigrafo d) V = {a, b, c, d, e, f} y E = {ab, bc, cd, de, ef, fa, b->f, f->d} No representa un grafo Teoremas Dos grafos son isomorfos si tienen el mismo número de vértices y aristas y, éstas se corresponden con los mismos extremos. El grado del vértice de un grafo (gr) es el número de aristas que tienen por extremo dicho vértice. Si dos grafos son isomorfos, los vértices que se corresponden tienen el mismo grado. Primer Teorema de la Teoría de Grafos: todo grafo contiene un número par o cero de vértices de grado impar. Un subgrafo es un grafo que está contenido dentro de otro grafo y que se obtiene elimando algunas aristas y vértices del grafo principal. 19 FACULTAD DE INGENIERIA Un grafo es regular si todos sus vértices tienen el mismo grado k (k-regular). Un grafo es completo si cada par de vértices son los extremos de una arista. Dos grafos completos con el mismo número de vértices son isomorfos. Subgrafos de un grafo Hallar todos los subgrafos del grafo: a / \ / \ / \ ---------b c Se realiza la lista de subgrafos del grafo de la figura por orden creciente al número de aristas (CV es el conjunto vacío): 1. Subgrafos con cero aristas: 1.1. Con un vértice: grafo 1.1.1.: ({a}, CV) grafo 1.1.2.: ({b}, CV) grafo 1.1.3.: ({c}, CV) 1.2. Con dos vértices: grafo 1.2.1.: ({a, b}, CV) grafo 1.2.2.: ({b, c}, CV) grafo 1.2.3.: ({a, c}, CV) 1.3. Con tres vértices: grafo 1.3.1.: ({a, b, c}, CV) 2. Subgrafos con una arista: 2.1. Con dos vértices: grafo 2.1.1.: ({a, b}, {ab}) grafo 2.1.2.: ({b, c}, {bc}) grafo 2.1.3.: ({a, c}, {ac}) 2.2. Con tres vértices: grafo 2.2.1.: ({a, b, c}, {ab}) grafo 2.2.2.: ({a, b, c}, {bc}) grafo 2.2.3.: ({a, b, c}, {ac}) 3. Subgrafos con dos aristas: 3.1. Con tres vértices: grafo 3.1.1.: ({a, b, c}, {ab, bc}) grafo 3.1.2.: ({a, b, c}, {ab, ac}) grafo 3.1.3.: ({a, b, c}, {ac, bc}) 20 FACULTAD DE INGENIERIA 4. Subgrafos con tres aristas: 4.1. Con tres vértices: grafo 4.1.1.: ({a, b, c}, {ab, bc, ac}) 21 FACULTAD DE INGENIERIA CAMINOS Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo. Otras definiciones básicas son: Los extremos son los vértices inicial y final del camino. La longitud de un camino es el número de aristas que contiene. Un camino es cerrado si sus extremos coinciden. Un camino es simple si en la sucesión de vértices no hay ninguno repetido. Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el último. Un circuito es un camino cerrado que no repite aristas. Si en un grafo existe un camino que conecta dos vértices distintos, entonces existe un camino simple con extremos en dichos vétices. Un grafo es conexo si para cada par de vértices, existe un camino con extremos en dichos vértices. Caminos en un grafo Sea un grafo con V = {a, b, c, d, e, f, g} y E = {ab, bc, cd, da, ca, ce, ef, fg, ge, ga}. a b g d c f e Encontrar dentro del grafo (basta enumerar los vértices): Un camino que conecta b y f: (b, a, g, f) Un camino simple de longitud 5 entre b y f: (b, a, d, c, e, f) Un camino de longitud 6 entre b y f: (b, a, d, c, e, g, f) Un camino cerrado con origen en f de longitud 6: (f, g, a, b, c, e, f) Un ciclo de longitud 3, otro de longitud 4 y otro de longitud 6: (b, a, c, b) - (a, c, e, g, a) - (f, g, a, b, c, e, f) Un circuito de longitud 9: (a, b, c, d, a, g, f, e, c, a) Tipos de caminos Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar. Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano. 22 FACULTAD DE INGENIERIA Caminos eulerianos Dibujar un camino euleriano para el siguiente grafo: a b e f c d (c, b, f, c, d, f, e, b, a, e, d) EXPLORACION Los grafos son utilizados con frecuencia para representar vías y redes de comunicación. Aquí se ofrece una forma matricial de representar un grafo. Se denomina matriz de adyacencia a una matriz cuyas entradas son unos y ceros siguiendo una ley: a cada emtrada mij le corresponde la arista dada por vivj. Según sea grafo o digrafo será: GRAFO DIGRAFO =================================================================== mij = 1 si vivj forma arista mij = 1 si vivj forma arista y orientación = vi -> vj mij = 0 si vivj no forma arista mij = 0 si vivj no forma arista y orientación = vj -> vi Teoremas Dos grafos con la misma matriz de adyacencia son isomorfos. Un árbol es un grafo conexo sin ciclos. Un grafo es un árbol si y sólo si cada dos vértices distintos se conectan por un único camino simple. Un grafo es etiquetado si sus aristas tienen asignado un número. Se llama distancia de un grafo etiquetado a la longitud mínima del camino entre dos vértices dados. Matriz de adyacencia de un grafo Con los siguientes vértices: 1 5 3 4 2 Hallar la matriz de adyacencia del grafo {12, 23, 34, 45, 51, 13, 35} |0 |1 |1 |0 |1 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0| 0| 1| 1| 0| 23 FACULTAD DE INGENIERIA Hallar la matriz de adyacencia del digrafo {1->2, 2->3, 3->4, 4->5,5->1, 1->3, 5->3} |0 |0 |0 |0 |1 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0| 0| 0| 1| 0| Algoritmo de Dijkstra Es un algoritmo que sirve para hallar la distancia más corta entre dos vértices de un digrafo. Sus reglas básicas son: Se toma el vértice inicial y se comprueba todas las direcciones posibles de salida. Se elige entre todos los vértices el de la distancia mínima y se accede a él. Desde el siguiente vértice se efectúa el mismo paso hasta llegar al vértice final. El algoritmo recorre todos los caminos posibles hasta tener la distancia mínima entre ambos vértices. Hallar el camino más corto Calcular la distancia desde el vértice s hasta el vértice t aplicando el Algoritmo de Dijkstra en el siguiente grafo etiquetado: a b s t c d Distancias: (sa=18, sc=15, ac=6, ab=9, cd=7, cb=14, bd=10, bt=28, dt=36) El camino más corto será (s, a, b, t) donde d(s, t) = 55 MAPAS Definiciones Un grafo se dice que es plano si admite una representación gráfica en el plano de modo que cada arista corta únicamente a otra arista en un vértice que sea extremo de ambas. Una representación de un grafo con estas condiciones se dice que es un mapa. Un mapa es conexo si el grafo que representa es conexo. Las regiones son las divisiones en varias partes de un plano. El grado de una región es la longitud del camino que la bordea. La suma de los grados de las regiones de un mapa es igual al doble del número de aristas del grafo que representa. Fórmula de Euler Sea M un mapa conexo con #R (número de regiones) que representa al grafo G con #V (número de vértices) y con #E (número de aristas), entonces: #V - #E + #R = 2 24 FACULTAD DE INGENIERIA Teoremas Si un grafo es plano conexo con #V > 2, entonces #E <= 3#V - 6. Si en un grafo plano conexo con #V > 2, no existe ningún subgrafo isomorfo k3-regular, entonces #E <= 2#V - 4. Dos regiones son adyacentes si los caminos que las bordean tienen alguna arista en común. Una coloración es una aplicación de tal manera que dos vértices contiguos no puedan tener el mismo color. Todo grafo plano admite una coloración con cuatro colores. Un grafo es bipartito si existe una coloración con sólo dos colores, o si y sólo si no tiene ciclos con longitud impar. 25 FACULTAD DE INGENIERIA WORK PAPER # 6 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Estructuras algebraicas DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 26 FACULTAD DE INGENIERIA ESTRUCTURAS ALGEBRAICAS Una Estructura Algebraica es un objeto matemático consistente en un conjunto no vacío y una relación ó ley de composición interna definida en él. En algunos casos más complicados puede definirse más de una ley de composición interna y también leyes de composición externa. Empecemos por recordar algunas definiciones: Operación binaria ó Ley de composición interna definida en un conjunto no vacío A Es una aplicación o función del producto cartesiano de A x A en A En símbolos: es una ley interna en A : A x A A Es decir (a1, a2 ) a1 a2 Ejemplo 1 La suma ó la multiplicación en N , en Z , en Q , en R ó en C. Ejemplo 2 Las siguientes tablas definen leyes de composición interna en el conjunto A = {a , b , c } i) ii) Ley de composición externa Una ley de composición externa definida en A con operadores de B es toda función ó aplicación de B x A en A. En símbolos es ley externa en A con operadores en B B x A A es decir, si b B y a A la imagen del par (b ; a) = b a A Según las propiedades que deban satisfacer estas leyes de composición, se tienen los distintos tipos de estructuras ó sistemas axiomáticos. Monoide El par (A , ) donde A es un conjunto no vacío dotado de una operación ó ley de composición interna se denomina monoide. Ejemplos de monoides ( N , + ) , ( Z , + ) , ( Q , + ) , son monoides. ( N , - ) no es un monoide porque la sustracción no es ley de 27 FACULTAD DE INGENIERIA composición interna en N. ( N , ) donde está definido como a b = máx.{a , b} es un monoide. Semigrupo Un monoide asociativo se denomina semigrupo. Si la ley de composición interna también es conmutativa se llama semigrupo conmutativo. Si existe el elemento neutro se dice que es un semigrupo con unidad ó semigrupo con identidad. El elemento neutro de llama identidad. Ejemplos de semigrupos ( N , + ) es un semigrupo conmutativo sin elemento neutro. ( N0 , + ) es un semigrupo conmutativo con elemento neutro, el 0. ( N , ) es un semigrupo conmutativo con elemento neutro ó identidad igual a 1. Grupo Sea el par (A , ) , donde A es un conjunto no vacío dotado de una ley de composición interna binaria : (A , ) es un grupo ó se define sobre A una estructura de grupo sí: a) es asociativa. Es decir a , b , c : a, b, c A a b c a b c b) posee elemento neutro en A. Es decir e A / a , si a A a e e a a c) Todo elemento de A es invertible en A respecto de . Es decir a A , a´ A / a a´ a´ a e Grupo Abeliano ó Grupo conmutativo es cuando además de ser un grupo, d) es conmutativa. Es decir a , b : a, b A a b b a Si G = (A , ) es un grupo, se dice que es un grupo finito si el conjunto A es finito y su cardinal se llama orden del grupo. Ejemplos 1) El par ( Z , ) donde Z es el conjunto de los números enteros y es una operación definida como a b = a + b + 3 forma un grupo abeliano. Comprobación: es una ley de composición interna en Z pues si a y b Z , a + b + 3 Z es asociativa pues a b c = (a + b +3) c = a + b +3 + c +3 = a + b + c + 6 y a b c = a (b + c + 3) = a + b + c + 3 + 3 = a + b + c + 6 28 FACULTAD DE INGENIERIA tiene elemento neutro e = –3 , pues a A , a e = a entonces a + e +3 = a e = –3 y e a = a entonces e + a + 3 = a e = –3 / a a e , en nuestro caso a a = –3 a a 3 = –3 luego a´ = – a – 6 es inverso a derecha a a 3 a a 3 = –3 luego a´ = – a – 6 es inverso a izquierda tiene inverso a , a es conmutativa pues a b = a + b + 3 = b + a + 3 = b a Otros ejemplos: 1) (Z,+) ; (Q,+) ; (R,+) y (C,+) Son grupos abelianos . También se llaman grupos aditivos debido a la operación aditiva. 2 ) ( N , + ) No es grupo. No tiene neutro ni inverso de cada elemento. 3 ) ( N0 , + ) No es grupo. Tiene neutro, el 0 , pero no tiene inverso aditivo. 4 ) ( Q , ) No es grupo, el 0 no tiene inverso multiplicativo. 5 ) ( R , ) No es grupo, el 0 no tiene inverso multiplicativo. 6 ) ( Q – { 0 } , ) y ( R – { 0 } , ) Son grupos. Subgrupo Un subconjunto no vacío B, del conjunto A es un subgrupo de ( A , ) si y solo sí ( B , ) es un grupo. Por ejemplo, ( Z , + ) es un subgrupo de ( Q , + ). Si en estas estructuras se introduce una nueva ley de composición interna con ciertas restricciones, se obtienen ternas ordenadas del tipo (A , , ) que también son estructuras algebraicas. Estas nuevas estructuras son: Anillo Dados, un conjunto no vacío A y dos leyes de composición interna y , la terna ordenada (A , , ) tiene estructura de Anillo si y solo si a) es asociativa. Es decir a , b , c : a, b, c A a b c a b c 29 FACULTAD DE INGENIERIA b) posee elemento neutro en A. Es decir e A / a , si a A a e e a a c) Todo elemento de A es invertible en A respecto de . Es decir a A , a´ A / a a´ a´ a e d) es conmutativa. Es decir a , b : a, b A a b b a Estas 4 propiedades muestran que ( A , ) es un grupo abeliano. e) es asociativa. Es decir a , b , c : a, b, c A (a b) c = a ( b c) Esta propiedad muestra que ( A , ) es un semigrupo. f) distribuye doblemente sobre . Es decir, a , b , c : a, b, c A a (b c ) = ( a b ) (a c ) y (b c ) a = (b a ) ( c a ) Resumiendo podemos decir que: (A , , ) es un Anillo sii (A , ) es un grupo abeliano ; ( A , ) es un semigrupo y la segunda operación distribuye sobre la primera. Una aclaración oportuna Como la operación es aditiva y la operación es multiplicativa, es común representarlas con los conocidos signos de la suma y el producto, pero en todos los casos deberá respetarse la definición que corresponde a cada operación. Con esta aclaración debe quedar claro que ( A , + , ) representa una estructura algebraica, talvez un anillo, pero que la operación + y la operación no representan la suma y el producto conocido, salvo ello esté expresamente indicado. Con igual margen de tolerancia en la interpretación de este tema, debemos decir que el elemento neutro de la operación aditiva se representa con 0 (cero) y el neutro de la operación multiplicativa con 1 (uno) sin que ellos sean necesariamente el 0 y 1 conocidos. Si además g) conmutativa. Es decir a , b : a, b A a b = b a entonces tenemos un Anillo conmutativo. h) posee elemento neutro en A. Es decir e A / a , si a A a e e a a entonces tenemos un Anillo con identidad ó Anillo con unidad. i) Todo elemento de A distinto de cero es invertible en A respecto de . Es decir a A , a 0 , a´ A / a a´ = a´ a = e entonces se llama Anillo de división. Ejemplos 1.- ( N , + , ) con las operaciones conocidas no es un anillo, pues en N no existe neutro para la adición. 30 FACULTAD DE INGENIERIA 2.- ( N0 , + , ) con las operaciones conocidas no es anillo, pues N0 carece de inversos aditivos. 3.- ( Z , + , ) con las operaciones conocidas, es un anillo conmutativo con unidad. Anillos sin divisores de cero Un anillo (A , , ) se dice sin divisores de cero si y solo sí elementos no nulos de A dan producto no nulo. En símbolos: (A , , ) carece de divisores de cero si y solo sí a , b : a, b A si a 0 y b 0 entonces a b 0 Anillo de integridad (A , , ) es un Anillo de integridad si y solo sí (A , , ) es un anillo y 0 es su único divisor de cero Dominio de integridad La terna (A , , ) se llama Dominio de integridad si y solo sí (A , , ) es un Anillo conmutativo con unidad y sin divisores de cero. Dicho de otra manera, un Dominio de integridad es un Anillo conmutativo con identidad y de integridad. Ejemplos 1.- ( Z , + , ) con las operaciones conocidas es un dominio de integridad. 2.- ( Q , + , ) ; ( R , + , ) y ( C , + , ) con las operaciones conocidas son dominio de integridad. 3.- Los polinomios en una indeterminada ( o más ) con coeficientes en Q , R ó C forman dominio de integridad con las operaciones conocidas. Cuerpo La terna ordenada ( A , + , ) es un cuerpo, o tiene estructura de cuerpo si y solo si ( A , + , ) es un anillo de división conmutativo. Esto es: ( A , + , ) es un cuerpo si y solo si ( A , + , ) es un anillo conmutativo, con unidad cuyos elementos no nulos admiten inverso multiplicativo. Un cuerpo queda caracterizado por las siguientes estructuras: ( A , + , ) es un cuerpo si y solo si a) ( A , + ) es un grupo abeliano. b) ( A – {0} , ) es un grupo abeliano. c) distribuye respecto de + 31 FACULTAD DE INGENIERIA Ejemplos 1.- ( Z , + , ) con las operaciones conocidas, no es cuerpo, pues Z carece de inversos multiplicativos. 2.- ( Q , + , ) ; ( R , + , ) y ( C , + , ) con las operaciones conocidas son cuerpos. 3.- Todo cuerpo es un dominio de integridad. Para proveer de un ejemplo de estructura algebraica no tan conocida, definiremos el conjunto Zn llamado conjunto de los enteros modulo n. Enteros módulo n (Zn) Si n es un número entero tal que n 2 , se denomina Zn al conjunto Zn = { 0 , 1 , 2 , 3 ,..., n-1} Este conjunto, provisto de las operaciones de suma y producto definidas así: + suma : si h y k pertenecen a Zn , entonces h + k es igual al resto de la división de h + k por n. Ejemplo: si n = 8 ; h = 5 y k = 7 , entonces h + k = 4 producto : si h y k pertenecen a Zn , entonces h k es igual al resto de la división de h k por n. Ejemplo: si n = 8 ; h = 5 y k = 7 , entonces h k = 3 La terna (Zn , + , ) es un anillo conmutativo con unidad. Se llama Anillo de los enteros módulo n. ( Zn , + , ) es un dominio de integridad si y solo sí n es primo. Esto puede verse en las siguiente tablas de operaciones en el conjunto Zn Para n = 3 Zn = { 0 , 1 , 2 } las tablas de operaciones son: Para la suma + 0 1 2 Para el producto 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 El producto No posee divisores de cero Para n = 4 Zn = { 0 , 1 , 2 , 3 } las tablas de operaciones son: Para la suma Para el producto 32 FACULTAD DE INGENIERIA + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 El producto posee divisores de cero Espacio Vectorial Un espacio vectorial sobre un cuerpo K es un conjunto V , cuyos elementos se denominan vectores, provisto de dos operaciones, una interna que se denomina suma y otra externa que se denomina producto y que cumplen ciertas propiedades. La operación externa , multiplica un elemento del conjunto K por un elemento del conjunto V. Notación Esta estructura suele representarse de las siguientes maneras: Como la cuaterna ordenada ( V , + , K , ) ; como la terna ordenada ( K , V ,+ ) y también es muy usual la expresión sintetizada VK , todas ellas se leen Espacio Vectorial V sobre el cuerpo K . o simplemente K – espacio vectorial. Las operaciones enunciadas deben cumplir las siguiente propiedades: 1. ( V , + ) es un Grupo conmutativo a) + Es asociativa b) + Es conmutativa c) + Tiene neutro d) + Tiene inverso 2. La operación externa asocia de la siguiente manera: a , b : a, b K y x A , a ( b x ) = ( a b ) x 3. La operación externa distribuye sobre la interna de la siguiente manera: a : a K y x , y A , a ( x + y ) = a x + a y 4. La operación externa tiene elemento neutro. Ejemplos 1.- ( Rn, + , R , ) es un Espacio Vectorial con las suma y el producto conocidos. Siendo Rn , con n 1 el conjunto de las n – uplas de números reales. 2.- ( K x , + , K , ) es un Espacio Vectorial con la suma y el producto conocidos, siendo K un cuerpo y K x el conjunto de los polinomios en una indeterminada con coeficientes en K. 33 FACULTAD DE INGENIERIA 3.- ( Rm x n, + , R , ) en el Espacio Vectorial de la matrices de orden m x n en el cuerpo de los reales, con la suma y el producto conocidos. Morfismo u Homomorfismo Una aplicación de conjuntos f: A B se dirá que es un morfismo de la estructura (A , ) en la estructura (B , ) o simplemente un morfismo de A en B si se cumple que: x , y A ; f(x y) = f(x) f(y) Ejemplo: Sean las estructuras ( R , + ) y ( R + , ) con las operaciones + y usuales. La aplicación f : R R + definida por f(x) = 2 x es un morfismo de estas estructuras ya que cumple que: f (x + y) = 2 x + y = 2 x 2 y = f (x) f (y) Endomorfismo Se llama así a todo morfismo de A en A. Monomorfismo Se llama así a todo morfismo inyectivo. Epimorfismo Se llama así a todo morfismo sobreyectivo. Isomorfismo Se llama así a todo morfismo biyectivo. Automorfismo Se llama así a todo endomorfismo biyectivo. Ejemplos 1. Sean las estructuras ( R3 , + ) y ( R2 x 2 , + ) y la aplicación x1 0 x2 x3 f ( x1 , x2 , x3 ) = 34 FACULTAD DE INGENIERIA Las operaciones consideradas son las de suma de ternas ordenadas de números reales y la de suma de matrices. Entonces, como : f x1, x2 , x3 y1, y2 , y3 = f x1 y1 ,x2 y2 ,x3 y3 = 0 x1 y1 x1 0 y1 0 x y x y = x x + y y = 2 3 3 3 3 2 2 2 = f x1, x2, x3 + f y1, y2, y3 f es un morfismo. Además es inyectivo, es decir un monomorfismo. puesto que x y al dominio, resulta: 0 x f x1, x2, x3 = 1 f y1, y2, y3 = x2 x3 y1 0 y y 3 2 1 2 no es imagen de nadie. 3 4 Para probar que no es sobreyectivo, basta ver que, por ejemplo 2. f : R R tal que f (x) = – 3x es un automorfismo respecto a la suma. Es morfismo pues f (x + y ) = – 3 (x + y ) = – 3x – 3y = f (x ) + f (y ) f es biyectiva porque: es inyectiva: x y ; f (x ) f (y ) ya que – 3x – 3y y es suryectiva: y R x R tal que f (x ) = y ; – 3x = y entonces x = – y 3 3. f : R R tal que f(x) = x + 1 no es homomorfismo respecto a la adición. Efectivamente no cumple la definición de morfismo f (x + y) f (x) + f (y) ya que x + y + 1 x +1 + y + 1 = x + y + 2 35 FACULTAD DE INGENIERIA Es interesante saber que la Topología es la parte de la matemática que se ocupa de estudiar los conjuntos estructurados mediante relaciones que nos permiten decir cuando un elemento del conjunto es “contiguo” o próximo a una parte del mismo. Topología deriva del griego que significa: Topos: Lugar , extensión ó posición. Logos: Ciencia ó saber. Luego la topología puede definirse como la “ Ciencia de la extensión ó del lugar”. 36 FACULTAD DE INGENIERIA WORK PAPER # 7 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Teoría de Conjuntos DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 37 FACULTAD DE INGENIERIA TEORÍA DE CONJUNTOS Conjuntos numéricos Recuerde las formas de definir un conjunto: por extensión y por comprensión Números naturales Los puntos sucesivos significan: "y así sucesivamente" Son los que se utilizan para contar objetos existentes En algunos casos este conjunto incluye el cero. En ese caso se anota N a veces se lo denomina: enteros positivos ( ) * ¿ Tiene este conjunto primer elemento ? * ¿ Tiene este conjunto último elemento ? * Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede? * Dado un elemento cualquiera, ¿se puede decir que elemento le sigue? Podemos graficar mediante un diagrama de Venn de la siguiente manera: También podemos verlos como una serie de puntos alineados y equidistantes Operemos con estos números 3 +1 4 -3 = = 4 1 38 FACULTAD DE INGENIERIA 3 -4 = ? Como llegamos a una operación que no podemos resolver. Es necesario extender este conjunto. Números enteros Son los naturales más sus simétricos y el cero. * ¿ Tiene este conjunto primer elemento ? * ¿ Tiene este conjunto último elemento ? * Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede? * Dado un elemento cualquiera, ¿se puede decir que elemento le sigue? Podemos graficar mediante un diagrama de Venn de la siguiente manera: También podemos verlos de la siguiente manera Operemos con estos números: 3-4 2* 3 6: 2 3: 2 = = = = -1 6 3 ? Como llegamos a una operación que no podemos resolver. Es necesario extender este conjunto. Números Racionales Q = {a sobre b, tal que a y b pertenecen a Z y b es distinto de cero} De aquí en adelante no aclararemos más que los denominadores deben ser distintos de cero. También llamados fracciones 39 FACULTAD DE INGENIERIA * ¿ Tiene este conjunto primer elemento ? * ¿ Tiene este conjunto último elemento ? * Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede? * Dado un elemento cualquiera, ¿se puede decir que elemento le sigue? Podemos graficar mediante un diagrama de Venn de la siguiente manera: También los podemos ver de la siguiente manera Operemos con estos números Reflexione sobre esta imposibilidad hasta comprender realmente. Rehaga los ejemplos dados en clase. Obviamente necesitamos crear un conjunto que agrupe este tipo de números. Números irracionales Son los que no se pueden expresar como racionales * ¿ Tiene este conjunto primer elemento ? * ¿ Tiene este conjunto último elemento ? * Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede? * Dado un elemento cualquiera, ¿se puede decir que elemento le sigue? 40 FACULTAD DE INGENIERIA Podemos graficar mediante un diagrama de Venn de la siguiente manera: Podemos graficar de la siguiente manera Números reales: Con lo cual obtenemos la denominada recta real. (Piense en las dos rectas cribadas sobrepuestas) Recuerde: una recta es una sucesión infinita de puntos alineados. Entre dos puntos siempre existe otro punto, o bien entre dos puntos existen infinitos puntos (reflexione sobre estas dos cuestiones) A cada número real le corresponde un punto y a cada punto le corresponde un número real. De aquí en más siempre que hablemos de número nos referiremos a un número real, en caso contrario se hará expresa mención. A cada número le corresponde un punto y a cada punto le corresponde un número. * ¿ Tiene este conjunto primer elemento ? * ¿ Tiene este conjunto último elemento ? * Dado un elemento cualquiera, ¿ se puede decir que elemento lo precede? * Dado un elemento cualquiera, ¿se puede decir que elemento le sigue? Lamentablemente aquí no terminan los problemas. 41 FACULTAD DE INGENIERIA Por ejemplo si queremos resolver: nos veremos nuevamente en problemas. Pero para nosotros está bien por ahora. Mencionaremos este problema más adelante cuando hablemos de parábolas. (Leibnitz agradecido,¿?) División de un segmento en una razón dada. Trate de comprobar que el valor 2/3 aparece, independientemente del ángulo elegido y el largo del segmento seleccionado, en la misma posición en la recta real, recordando la explicación dada durante la clase. Hallará la respuesta a continuación, pero trate de resolver por si mismo. A continuación obtenemos un segmento de longitud 4/3 de dos formas distintas. Explique claramente cuál fue el criterio utilizado en cada caso. 42 FACULTAD DE INGENIERIA * Defina por extensión el conjunto de todos los nombres de varón, en Español, que no contengan ninguna de las letras del nombre "Carlos". * Defina por extensión el conjunto que contenga todos los números naturales en cuyo nombre, en Español, tengan la misma cantidad de letras que representan. * Defina por extensión el conjunto que contenga todos los números naturales en cuyo nombre, en Inglés, tengan la misma cantidad de letras que representan. * Defina por extensión el conjunto que contenga todos los números naturales en cuyo nombre, en Italiano, tengan la misma cantidad de letras que representan. * (en Alemán)? * Recuerde la explicación sobre como hallar el punto que representa a sobre la recta real. Sobre la recta real halle: * * * En la tabla que sigue, siempre que sea posible ( pregunte en clase sobre las imposibilidades ): * Marque a que conjunto/s pertenecen los números de la primera columna. * Escriba el número como racional, de tres maneras distintas. * Convierta cada número en notación decimal expresándolos con uno, dos, tres y cinco decimales. (Piense que, en algunos casos, no es exactamente el mismo número) 43 FACULTAD DE INGENIERIA * Ordene todos los números en forma creciente. * Marque, de ser posible, su ubicación en la recta real. (recuerde la explicación sobre "división de un segmento en una razón dada") * -5 8.3 Signo Natural Entero Irracional Racional -10.3 8 0 - Determine sobre una misma recta real los puntos que representan a: 0, 1, Recién después de resolver vea la solución e las páginas siguientes. 44 FACULTAD DE INGENIERIA 45 FACULTAD DE INGENIERIA Se muestran a continuación las reglas prácticas para convertir un número racional en notación decimal a notación racional. Aproximación 1. Un número con parte entera igual a cero y la parte decimal periódica pura. El numerador será igual a la parte periódica y el denominador tantos nueves como dígitos contenga el período: Aproximación 2. Un número con parte entera distinta a cero y la parte decimal periódica pura. Será igual a la parte entera más un racional que tendrá como numerador la parte periódica y como denominador tantos nueves como dígitos contenga el período: Observe que este caso contiene al anterior. Compruebe con algunos ejemplos. Aproximación 3. Un número con parte entera distinta a cero y la parte decimal periódica impura. Será igual la parte entera más un racional que tendrá como numerador a la parte no periódica seguida de la parte periódica menos la parte no periódica, y como denominador tantos nueves como dígitos contenga el período y tantos ceros como dígitos contenga la parte no periódica: 46 FACULTAD DE INGENIERIA Observe que este caso contiene al anterior. Compruebe con algunos ejemplos. Por lo tanto podremos tomar este último caso como regla general. Obtenga los racionales correspondientes 47 FACULTAD DE INGENIERIA WORK PAPER # 8 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Conjuntos, relaciones y funciones DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 48 FACULTAD DE INGENIERIA CONJUNTOS , RELACIONES Y FUNCIONES Conjuntos Definición de Conjuntos 1) Enumerando A = { 1,3,5,7 } 2) Por Propiedades A = { x | x es impar } = { x | (x mod 2)=1 } 3) Intervalos A = [ 1,5 ] = { 1,2,3,4,5 } A = ( 1,5 ) = { 2,3,4 } Conjuntos especiales Conjunto Vacío Conjunto Universal Ø U Conjunto Números Enteros Positivos 1,2,3,... Conjunto Números Naturales 0,1,2,3,... Conjunto Números Enteros ...,-3,-2,-1,0,1,2,3,... Conjunto Números Racionales (Razones de enteros, i.e. quebrados) y Conjunto Números Irracionales -1, ¾, ... 49 FACULTAD DE INGENIERIA Cardinalidad Operador de Cardinalidad long(A): Numero de elementos del conjunto A A=[1,5], long(A)=5 Finito Número de elementos es finito A=[1,5] Infinito Número indefinido de elementos A = { x | x es par } Contable Sus elementos son enumerables (puede ser infinito). No Contable Dado cualquier pareja de elementos siempre existirá un elemento intermedio entre ambos. Operaciones para Conjuntos x | x x Unión x | x Intersección x A-B=A\B={x Equivalencia: B - | x x Diferencia (Complemento Relativo) c Complemento Ac = ~A = ¬A = { (x x x =U-A={x | x Diferencia Simétrica - A) = x x x x x Subconjunto x( x x 50 FACULTAD DE INGENIERIA i ={i x i } Unión / Intersección Múltiple i Conjunto Potencia (A) = El conjunto de todos los subconjuntos de A Si A tiene n elementos, entonces (A) tiene 2n subconjuntos. Ej: A={0,1}, luego (A)={Ø, {0},{1},{0,1}}. Nota: (Ø)={Ø} Formalmente: long( (A)) = 2long(A) Producto Cartesiano donde: <a,b> denota un par ordenado, i.e. tupla-2. Relaciones entre Conjuntos Conjunto Propio Conjunto Impropio Conjuntos Disjuntos Relaciones 51 FACULTAD DE INGENIERIA Sean A y B conjuntos. Una relación de A a B es cualquier subconjunto R del producto cartesiano A×B. A se conoce como dominio y B como rango de R. Ejemplo: Sean P={x I={x |x |x x<12 } = { 1, 3, 5, 7, 11 } x<10 } = { 1, 3, 5, 7, 9 } Por lo tanto: P × I = { <1,1>, <1,3>, <1,5>, ... , <11,9>, } Sea: R = { <1,1>, <3,3>, <5,5>, <7,7>, <11,9> } Gráficamente: I Matriz: 1 3 5 7 9 <1,1> <1,3> <1,5> <1,7> <1,9> 1 3 P 5 7 11 <3,1> <3,3> <3,5> <3,7> <3,9> <5,1> <5,3> <5,5> <5,7> <5,9> <7,1> <7,3> <7,5> <7,7> <7,9> 52 FACULTAD DE INGENIERIA <11,1> <11,3> <11,5> <11,7> <11,9> Grafo: Relaciones Especiales Relación de Equivalencia { < x,x E R-1 Relación Inversa Propiedades para Relaciones Reflexiva Para toda x Irreflexiva Para toda x xRx xRx Simétrica Para toda xRy, existe yRx Asimétrica Para cada xRy, no existe yRx 53 FACULTAD DE INGENIERIA Antisimétrica Para cada xRy, no existe yRx, pero si xRx Transitiva Siempre que exista xRy, y yRz, existe xRz La relación de equivalencia E es reflexiva, simétrica y transitiva. Funciones Sean X, Y conjuntos. Una función f de X a Y es una relación R de X a Y tal que para cada f(x) existe un solo elemento y Finalmente: "La función f es una relación de X a Y". < x,y f f(x) = y "f mapea de X a Y". f: "f transforma X en Y", donde: X es el dominio y Y es la imagen. Existe una correspondencia uno-a-uno en f(x)=y, cuando para toda x tienen el mismo número de elementos, i.e. cardinalidad. existe una y , y viceversa. Por lo que X y Y Función Inversa: Toda función con correspondencia uno-a-uno posee una función inversa, f-1(y) = x si y solo si f(x) = y 54 FACULTAD DE INGENIERIA WORK PAPER # 9 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Teoría de Grafos DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 55 FACULTAD DE INGENIERIA TEORÍA DE GRAFOS Definición: Un grafo (o bien, un grafo o dirigido) G consiste en un conjunto de V de vértices (o nodos) y un conjunto E de lados (o ramas) tales que cada lado e Є E está asociado a un par no ordenado de vértices. Si un lado e está asociado a un único par de vértices v y w, se escribe e=(v,w) o bien e=(w,v). En este contexto, (v,w) denota un lado de un grafo no dirigido y no un par ordenado de números. Un grafo dirigido (o dígrafo) consiste en un conjunto V de vértices (o nodos) y un conjunto de E de lados (o ramas) tales que cada lado e Є E está asociado a un par ordenado de vértices. Si un lado e está asociado a n par ordenado único de vértices v y w, se escribe e=(v,w). T S e2 e1 e3 e9 e10 W e11 Z U e7 e6 e4 e8 V X e5 Y En esta figura se muestra un grafo no dirigido donde {S,T,U,V,W,Y,Z} son los vértices y {e1,e2,e3,…..e11) son los lados. La siguiente figura muestra un grafo dirigido: V1 e1 e3 V2 V3 e4 e2 V5 e5 V4 V6 e6 Representaciones de grafos: Existen dos métodos para la representación de un grafo: 56 FACULTAD DE INGENIERIA Matriz de Adyacencia: Se selecciona un orden arbitrario para los vértices. a b c d a b c d e a 0 1 0 0 1 b c 1 0 0 1 1 1 0 0 1 1 d 0 0 0 0 1 e 1 1 1 1 0 e Matriz de Incidencia: Se le asignan a las filas las marcas correspondientes a los vértices, y a las columnas las correspondientes los lados. b x1 x2 x5 a c x6 x3 x7 e x8 x4 a b c d e x1 1 1 0 0 0 x2 x3 x4 x5 x6 x7 x8 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 d 57 FACULTAD DE INGENIERIA WORK PAPER # 10 PROGRAMA DE CONTROL DE CALIDAD No. DE PROCEDIMIENTO: No. DE HOJAS 4 ELABORÓ: CÓDIGO: TÍTULO DEL WORK PAPER: : Arboles, Teoría de los cuatro colores DPTO.: Facultad de Ingeniería DESTINADO A: DOCENTES ALUMNOS X ADMINIST. OTROS OBSERVACIONES: FECHA DE DIFUSIÓN: FECHA DE ENTREGA: 58 FACULTAD DE INGENIERIA ÁRBOLES TEORÍA DE LOS CUATRO COLORES Cuatro colores son siempre suficientes para colorear un mapa.(Véase también:Colorear un mapa con 4 colores) El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método. La forma precisa de cada país no importa; lo único relevante es saber cual país toca cual otro. Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos. Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. prueba de ello es que se ha tenido que emplear los ordenadores para 59 FACULTAD DE INGENIERIA acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos , lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador. Un juego muy conocido es el siguiente: Se dibuja tres casas y tres pozos. Los vecinos de las casas tienen todos el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿ Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces ? Cualquier disposición de las casas, los posos y los caminos implica la presencia de al menos un cruce. Se nota Kn el grafo completo con n vértices, es decir en el cual cada par de vértices están conectadas por una arista. Kn,p es el grafo compuesto de un grupo de nvértices y otro de p, tal que cada vértice del primer grupo está conectado con cada del segundo, y no hay más aristas. El juego anterior equivale a descubrir si el grafo K3,3 es planario (se dice también plano), es decir si se puede dibujar en un plano sin que haya cruces. Y la respuesta es no. Establecer qué grafos son planarios no es obvio, y tiene que ver con la topología. 60 FACULTAD DE INGENIERIA PROGRAMA DE CALIDAD UDABOL DIF – 001 TEORIA DE GRAFOS En cierta competencia todos los alumnos gustan de Aritmética, algunos de Física y otros de química. aritmética y Física y 470 de química o aritmética, cuántos no gustan de física? Si 350 gustan de Supongo que Alvaro toma huevos o tocino para su desayuno cada mañana durante el mes de enero. Si come tocino 26 mañanas y huevos 17 mañanas. ¿Cuántas mañanas come huevos y tocico?. Un grupo de 70 personas ejecutan trabajos manuales utilizando tres materiales: barro madera y cartulina. Se sabe que todos utilizan barro, 29 utilizan madera, 40 cartulina y 11 emplean los tres materiales. Cuántos utilizan únicamente barro? Un ingeniero que dirige la construcción de un edificio de tres plantas, distribuye el personal de la siguiente manera: 43 trabajan en la primera planta, 58 en la tercera planta, 16 en la primera y segunda planta, 22 en la primera y tercera planta, 7 trabajan en las tres plantas. Si 52 trabajan en una sola planta y 37 dos plantas a la vez pero no en las tres. Cuántos trabajan: a) En la primera y segunda, pero no en la tercera b) En la segunda o tercera pero no en la primera c) Únicamente en la primera d) Cuántos en total. 61 FACULTAD DE INGENIERIA PROGRAMA DE CALIDAD UDABOL DIF – 002 CAMINOS Y CIRCUITOS Caminos y circuitos: Veremos las definiciones formales de caminos y circuitos, y se estudian estos conceptos en detalle. Sea G un grafo y sean v y w vértices en G. Un Camino, de longitud n de v a w es una sucesión de lados que va de v a w y la cual tiene n lados distintos entre sí. Un camino simple, de longitud n de v a w es uno de la forma (v0, v1,………vn), en donde V0=v y vn=w, y vo, v1, v2, ….vn, son distintos entre sí. Un circuito es un camino de v a v. Un circuito simple, es un circuito de la forma (v0, v1,………vn), en donde v0=vn y v0, v1, v2, ….. Vn-1 son distintos entre sí. Ejemplo c d b g a e f 62 FACULTAD DE INGENIERIA Sucesión de lados Camino? Camino simple? Circuito? (a,b,d,c,b,a) no no no (f,e,b,d,c,b,a) si no no (f,e,b,d) si si no (b.f.e.b,d,c,b) si no si (e,f,b,e) si no si Circuito simple? no no no no si 63