====== Examen Final - 61.07. Matemática Discreta - 26 de Diciembre de 2007 ====== **Cátedra:** Cátedra 03 \\ **Fecha:** Oportunidad X - Verano 2007\\ **Día:** 26/12/2007 Esta página está incompleta; podés ayudar completando el material. ===== Enunciado ===== ==== Punto I ==== - - - Definir álgebra de Boole y dar un ejemplo con más de cinco elementos. - Definir átomo en un álgebra de Boole y mostrar cuáles lo son en el ejemplo dado en la parte a). - Probar que un álgebra de Boole tiene exactamente n\in\mathbf{N} átomos si y sólo si posee 2^n. ==== Punto II ==== - - - Definir relación de equivalencia en un conjunto. - Definir relación de orden en un conjunto. - Probar que R es una relación de equivalencia y de orden en un conjunto A si y sólo si R=\left\{(x,x):x\in A\right\}. ==== Punto III ==== - - - Definir árbol generador de un grafo y probar que un grafo posee un árbol generador si y sólo si es conexo. - Sea G=(V,A) un grafo conexo y H=\left\{ a_1,\ldots,a_k \right\} \subseteq A tal que ningún ciclo o circuito de G tiene todas sus aristas pertenecientes a H. Probar que existe un árbol generador de G que posee todas las aristas de H. ==== Punto IV ==== - - - Dar la definición de árbol y demostrar una propiedad equivalente a ella. - Probar que si un árbol posee un vértice de grado k\in\mathbf{N} entonces posee por lo menos k vértices de grado 1. ==== Punto V ==== - - - Definir red de transporte y dar un ejemplo con por lo menos 7 vértices. - Definir flujo y su valor. Dar un ejemplo en la red dada en a). - Definir corte y su capacidad. Dar un ejemplo de la red dada en a). - Probar que si F es un flujo y P es un corte en la misma red, entonces \mathrm{val}(F) \leq \mathrm{cap}(P)\\ **Justifique todos los pasos realizados.** ===== Resolución ===== ===== Discusión ===== Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá.