**12/12/12**
**MATEMÁTICA DISCRETA**\\
**Coloquio**
-
- Definir isomorfismo para un par de álgebras de Boole.
- Demostrar que para todo x,y en B_1, si x precede a y, entonces f(x) precede a f(y) en B_2.
- Sean B_1 el álgebra de los divisores positivos de 154 y el álgebra de partes de {1;2;3}. Y el isomorfismo definido por: f(2) = {3}, f(7) = {2},
f(11) = {1}
- Calcular f(1) y f(77).
- Dar los átomos de B2.
-
-Definir árbol.
-Demostrar que en un árbol |A| = |V| - 1.
-Probar que si G = (A, V) es árbol, el grafo G^*, que se construye a partir de G, quitando un vértice de grado 1 de G y la correspondiente arista, entonces G^* es árbol.
-
- Demostrar que si, en un grafo conexo simple, existen dos caminos de longitud máxima, entonces comparten al menos 1 vértice.
- ¿Vale la propiedad para grafos no conexos?
- Demostrar que un grafo es conexo si y sólo si existe su árbol generador mínimo.
-
- Demostrar que, siendo M la matriz de adyacencia, el elemento i,j de la matriz M^n es igual a la cantidad de caminos de longitud n entre V_i, V_j.
- Demostrar que para un grafo simple de n vértices, entonces al menos dos de ellos deben tener el mismo grado.
-
- Definir red de transporte, flujo en una red de transporte y su valore de corte en una red de transporte y su capacidad.
- Definir flujo maximal y corte minimal en una red de transporte.
- Probar que dados un flujo F y un corte C en una red de transporte, entonces: \text{valor}(F) \le \text{capacidad}(C)
- ¿Qué puede decirse sobre F y C si en el punto anterior se cumple la igualdad?