12/12/12

MATEMÁTICA DISCRETA
Coloquio

1. 1. Definir isomorfismo para un par de álgebras de Boole.
   2. Demostrar que para todo en , si precede a , entonces precede a en .
   3. Sean el álgebra de los divisores positivos de 154 y el álgebra de partes de . Y el isomorfismo definido por:
      1. Calcular y .
      2. Dar los átomos de .
2. 1. Definir árbol.
   2. Demostrar que en un árbol .
   3. Probar que si es árbol, el grafo , que se construye a partir de , quitando un vértice de grado 1 de y la correspondiente arista, entonces es árbol.
3. 1. Demostrar que si, en un grafo conexo simple, existen dos caminos de longitud máxima, entonces comparten al menos 1 vértice.
   2. ¿Vale la propiedad para grafos no conexos?
   3. Demostrar que un grafo es conexo si y sólo si existe su árbol generador mínimo.
4. 1. Demostrar que, siendo la matriz de adyacencia, el elemento de la matriz es igual a la cantidad de caminos de longitud entre .
   2. Demostrar que para un grafo simple de vértices, entonces al menos dos de ellos deben tener el mismo grado.
5. 1. Definir red de transporte, flujo en una red de transporte y su valore de corte en una red de transporte y su capacidad.
   2. Definir flujo maximal y corte minimal en una red de transporte.
   3. Probar que dados un flujo y un corte en una red de transporte, entonces:
   4. ¿Qué puede decirse sobre y si en el punto anterior se cumple la igualdad?