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

1. 1. 1. Definir álgebra de Boole y dar un ejemplo con más de cinco elementos.
      2. Definir átomo en un álgebra de Boole y mostrar cuáles lo son en el ejemplo dado en la parte a).
      3. Probar que un álgebra de Boole tiene exactamente átomos si y sólo si posee .

1. 1. 1. Definir relación de equivalencia en un conjunto.
      2. Definir relación de orden en un conjunto.
      3. Probar que es una relación de equivalencia y de orden en un conjunto si y sólo si .

1. 1. 1. Definir árbol generador de un grafo y probar que un grafo posee un árbol generador si y sólo si es conexo.
      2. Sea un grafo conexo y tal que ningún ciclo o circuito de tiene todas sus aristas pertenecientes a . Probar que existe un árbol generador de que posee todas las aristas de .

1. 1. 1. Dar la definición de árbol y demostrar una propiedad equivalente a ella.
      2. Probar que si un árbol posee un vértice de grado entonces posee por lo menos vértices de grado .

1. 1. 1. Definir red de transporte y dar un ejemplo con por lo menos vértices.
      2. Definir flujo y su valor. Dar un ejemplo en la red dada en a).
      3. Definir corte y su capacidad. Dar un ejemplo de la red dada en a).
      4. Probar que si es un flujo y es un corte en la misma red, entonces
         

Justifique todos los pasos realizados.