Examen Final - 61.07. Matemática Discreta - 29 de Febrero de 2012

Fecha: Oportunidad 5 - Verano 2012
Día: 29/02/2012

1. 1. Definir árbol generador minimal. Dar una condición necesaria y suficiente para su existencia, y justificar.
   2. Explicar paso a paso un algoritmo para la obtención de un árbol generador minimal, y justificar que se obtiene lo buscado.

1. 1. Definir árbol generador.
   2. Demostrar que si todos los árboles generadores de contienen la arista , el grafo que se obtiene al quitar la arista de , no es conexo.
   3. Demostrar que si un grafo tiene un único árbol generador, es árbol.

1. Para un conjunto
   1. Definir relación de orden.
   2. Definir todos los elementos particulares de una relación de orden.
   3. Demostrar que si tiene un , éste es único.
   4. Dar un ejemplo de un orden con 3 elementos maximales y 2 elementos minimales, todos diferentes.

1. 1. Definir red de transporte, flujo, valor de flujo, corte, y capacidad de corte.
   2. Definir flujo maximal y corte minimal
   3. Probar que para cualquier corte en una red de transporte con un flujo .
   4. ¿Qué significa que se de la igualdad del item anterior?

1. Sean dos álgebras de Boole y , y un isomorfismo entre las dos algebras (definir concepto de isomorfismo)
   1. Demostrar que
   2. Sea un algebra de Boole formada por los divisores enteros positivos de 105 y con . Se define:\\
      1. Definir y
      2. Dar los atomos de