====== Examen Final - 61.07. Matemática Discreta - 29 de Febrero de 2012 ====== **Fecha:** Oportunidad 5 - Verano 2012\\ **Día:** 29/02/2012 ===== Enunciado ===== ==== Punto I ==== - - Definir árbol generador minimal. Dar una condición necesaria y suficiente para su existencia, y justificar. - Explicar paso a paso un algoritmo para la obtención de un árbol generador minimal, y justificar que se obtiene lo buscado. ==== Punto II ==== - - Definir árbol generador. - Demostrar que si todos los árboles generadores de G=(V,A) contienen la arista a_0, el grafo G* que se obtiene al quitar la arista a_0 de G, no es conexo. - Demostrar que si un grafo G=(V,A) tiene un único árbol generador, G es árbol. ==== Punto III ==== - Para un conjunto A - Definir relación de orden. - Definir todos los elementos particulares de una relación de orden. - Demostrar que si B \subset A tiene un sup(B), éste es único. - Dar un ejemplo de un orden con 3 elementos maximales y 2 elementos minimales, todos diferentes. ==== Punto IV ==== - - Definir red de transporte, flujo, valor de flujo, corte, y capacidad de corte. - Definir flujo maximal y corte minimal - Probar que para cualquier corte C en una red de transporte con un flujo F Valor(F) /leq Capacidad(C). - ¿Qué significa que se de la igualdad del item anterior? ==== Punto V ==== - Sean dos álgebras de Boole B1 y B2, y f:B1 \rightarrow B2 un isomorfismo entre las dos algebras (definir concepto de isomorfismo) - Demostrar que x \leq_1 y \rightarrow f(x) \leq_2 f(y) - Sea B1 un algebra de Boole formada por los divisores enteros positivos de 105 y B2=(P[A],\cap,\cup,\bar{ },\emptyset,A) con A={1,2,3}. Se define:\\f(3)={3} f(5)={1} f(7)={2} - Definir f(1) y f(35) - Dar los atomos de B2 Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá.