====== Examen Final - 61.07. Matemática Discreta - 10/07/2013 ====== **Cátedra:** Todas\\ **Fecha:** Segunda Oportunidad - Invierno 2013\\ **Día:** 10/07/2013 Esta página está incompleta; podés ayudar completando el material. ===== Enunciado ===== ==== Punto I ==== Dar el valor de verdad de las siguientes proposiciones. Justificar su respuesta. -Existe un grafo dirigido de 3 vértices, no euleriano tal que cada vértice tiene grado interior igual al grado exterior. -El grafo de la figura admite al menos 2 árboles generadores mínimos con todas sus aristas distintas. -Todo grafo conexo de 5 vértices y 6 aristas es un árbol. ==== Punto II ==== Probar que: -Si un grafo es conexo y tiene al menos dos vértices, tales que el grado de uno de ellos es igual a 1, y el de los demás es mayor (estricto) a 2, entonces el grafo tiene al menos un ciclo. -Si un Grafo conexo y acíclico, entonces |A| = |V|^{-1}. ==== Punto III ==== Dado un grafo G cuya matriz de adyacencia es: A= \begin{matrix} & V_1 & V_2 & V_3 & V_4 & V_5 & V_6 \\ V_1 & 0 & 1 & 1 & 0 & 1 & 1 \\ V_2 & 1 & 0 & 1 & 1 & 0 & 1 \\ V_3 & 1 & 1 & 0 & 1 & 1 & 0 \\ V_4 & 0 & 1 & 1 & 0 & 1 & 0 \\ V_5 & 1 & 0 & 1 & 1 & 0 & 1 \\ V_6 & 1 & 1 & 0 & 0 & 1 & 0 \\\end{matrix} -Analizar si es un grafo de Euler. Justificar la respuesta. Y en caso afirmativo hallar el camino o circuito. -Analizar si es un grafo de Hamilton. -Si se quita el vértice V2 y las aristas incidentes en él ¿El grafo resultante es isomorfo al del dibujo? ¿Y si se quita V3? Justifique. Acá había dibujado un grafo con 5 vértices: a,b,c,d,e con adyacencias: *a con: b,c,d,e *b con: a,c *c con: a,b,e *d con: a,e *e con: a,c,d ==== Punto IV ==== -Determinar el resultado de multiplicar la matriz A consigo misma n veces, siendo A = \left (\begin{matrix} 1 & -1\\ -1 & 1\end{matrix}\right ). Probar por inducción tal resultado. -Dar el valor de verdad de: "Si R y S son dos relaciones de orden, entonces R \cap S y R \cup S también son relaciones de orden". ==== Punto V ==== Se define en R^2 la siguiente relación: (x,y)R(w,z) \iff (x-y)^2 = (w-z)^2 -Demostrar que se trata de una relación de equivalencia. -Calcular cl(1,2), cl(-1,2), cl(2,2) y cl(0, \sqrt{2}), y graficarlas en el plano. -Escribir el conjunto cociente. ¿Cómo sería el conjunto cociente si en vez de estar trabajando en los pares ordenados de números reales, estuviéramos trabajando con los pares ordenados de números naturales? ===== Resolución ===== ====Punto I==== -VERDADERO: Un grafo con tres vértices aislados cumple. - -FALSO: Como contraejemplo, considerar un circuito de 5 vértices, y que dos de ellos estén conectados con una arista más ====Punto II==== ===(1)=== Si existe en el grafo algún lazo, existe entonces un ciclo.\\ Si existen aristas paralelas, entonces existe también un ciclo.\\ Supongamos entonces un grafo sin lazos y sin aristas paralelas, de dos vértices v_1 y v_2 unidos por una arista. Si se quiere que gr(v_2)>2 entonces se agregan dos vértices más, cada uno unido a v_2 por separado. Para cada uno de estos nuevos vértices de grado 1, se agregan dos vértices más, también unidos por separado. Siguiendo esta lógica se obtiene un árbol cuyas hojas, claramente, tienen un grado igual a 1. Pero por ser conexo, si se agrega una arista entre dos vértices existentes, se está agregando un segundo posible camino entre estos dos vértices, lo que lleva seguramente a un ciclo. ===(2)=== Dada la hipótesis, por cada vértice que se agrega al grafo, se agrega una y sólo una arista, ya que si se agregasen dos, por la hipótesis de conexividad, se formaría un segundo camino entre los dos vértices adyacentes, es decir un ciclo. La diferencia entre |A| y |V| se debe a que, cuando se agrega un vértice a un grafo vacío no se agrega una arista. ====Punto III==== ===(1)=== Es un grafo de Euler porque existen sólo dos vértices de grado impar (aquellos que tienen una cantidad impar de 1's en su fila o columna).\\ Un camino podría ser v_4 \rightarrow v_5 \rightarrow v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_1 \rightarrow v_6 \rightarrow v_2 \rightarrow v_4 \rightarrow v_3 \rightarrow v_5 \rightarrow v_6. ===(2)=== Es un grafo de Hamilton porque existe un camino y/o un ciclo hamiltoniano. Por ejemplo: v_4 \rightarrow v_5 \rightarrow v_6 \rightarrow v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4. ===(3)=== Sí es isomorfo porque, siendo V_{G'} el grafo sin el vértice 2 y V_D el dibujado, \exists f:V_{G'} \longrightarrow V_{D} biyectiva.\\ Por ejemplo:\\ f(v_1)=c\\ f(v_3)=e\\ f(v_4)=d\\ f(v_5)=a\\ f(v_6)=b\\ Y para cada \{v, w\} \in A_{G'} corresponde que \{f(v), f(w)\} \in A_{D}.\\ Lo mismo sucede reemplazando el vértice 3 por el vértice 2 (analizarlo). ====Punto IV==== ===(1)=== Elevando A al cuadrado y al cubo, se puede especular que, genéricamente,\\ A^n = \left( \begin{array}{cccc} 2^{n-1} & -2^{n-1} \\ -2^{n-1} & 2^{n-1} \end{array} \right) Probaremos entonces que\\ A^n = \left( \begin{array}{cccc} 2^{n-1} & -2^{n-1} \\ -2^{n-1} & 2^{n-1} \end{array} \right) \longrightarrow A^{n+1} = \left( \begin{array}{cccc} 2^{n} & -2^{n} \\ -2^{n} & 2^{n} \end{array} \right) Comenzamos analizando que\\ A^{n+1} = A^n \times A Y, usando la hipótesis y el valor conocido de A:\\ A^{n+1} = \left( \begin{array}{cccc} 2^{n}/2 & -2^{n}/2 \\ -2^{n}/2 & 2^{n}/2 \end{array} \right) \cdot \left( \begin{array}{cccc} 1 & -1 \\ -1 & 1 \end{array} \right) =\\ = \frac{1}{2} \left( \begin{array}{cccc} 2^{n} & -2^{n} \\ -2^{n} & 2^{n} \end{array} \right) \cdot \left( \begin{array}{cccc} 1 & -1 \\ -1 & 1 \end{array} \right) = \frac{1}{2} \left( \begin{array}{cccc} 2^n + 2^n & -2^n - 2^n \\ -2^n - 2^n & 2^n + 2^n \end{array} \right) =\\ = \frac{1}{2} \left( \begin{array}{cccc} 2\times2^n & -2\times2^n \\ -2\times2^n & 2\times2^n \end{array} \right) = \left( \begin{array}{cccc} 2^n & -2^n \\ -2^n & 2^n \end{array} \right) Ahora falta el primer caso, con n=1: A^1 = \left( \begin{array}{cccc} 2^0 & -2^0 \\ -2^0 & 2^0 \end{array} \right) = \left( \begin{array}{cccc} 1 & -1 \\ -1 & 1 \end{array} \right) Y confirmamos que la igualdad especulada al principio se confirma \forall n \geq 1. ===(2)=== La proposición dada resulta ser falsa. La idea es ir analizando por separado la reflexión, antisimetría y transitividad de las relaciones R \cap S y R \cup S. Cuando se analiza la antisimetría de R \cup S no se puede garantizar que x=y por lo que no es garantía de que R \cup S sea antisimetrica, es decir que no es de orden. Y como la tesis de la condición esta compuesta por una conjunción ('y'), la proposición resulta ser falsa.\\ Este punto es casi idéntico al Ejercicio 4 de la Práctica N° 4 de la guía (actualizada para el 1er cuatrimestre del 2007). ====Punto V==== ===(1)=== Se debe demostrar que la relación es reflexiva, antisimétrica y transitiva. ==Reflexividad== (x;y)R(x;y) \Leftrightarrow (x-y)^2 = (x-y)^2, y se cumple la reflexividad ==Antisimetría== (x;y)R(w;z) \Leftrightarrow (x-y)^2 = (w-z)^2,y por conmutatividad de la igualdad se cumple que (w;z)R(x:y) ==Transitividad== (a;b)R(c;d) \, \wedge \, (c;d)R(e;f) \, \Rightarrow \, (a-b)^2=(c-d)^2 \, \wedge \, (c-d)^2=(e-f)^2 \, \Rightarrow \\ \Rightarrow \, (a-b)^2=(e-f)^2 \, \Rightarrow \, (a;b)R(e;f) ===(2)=== cl[(1,2)] = \{ x \in R^2 / xR(1,2) \} = \{ x \in R^2 / (x_1 - x_2)^2 = (1-2)^2 = 1 \} \\ Dado este conjunto, se tiene que |x_1 - x_2| = 1. Entonces, \\ x_1 - x_2 = 1 \, \vee x_1 - x_2 = -1 \, \Rightarrow \\ \Rightarrow \, x_2 = x_1 - 1 \, \vee x_2 = x_1 + 1 \\ Y el gráfico de dicho conjunto es \\ set grid "on" set xlabel "x_1" set ylabel "x_2" set zeroaxis set samples 1000 plot [-4:4][-4:4] x-1, x+1 Para la siguiente clase pedida:\\ cl[(-1,2)]=\{ x \in R^2 / (x_1-x_2)^2=3^2=9 \} \, \Rightarrow \\ \Rightarrow \, |x_1 - x_2| = 3 \, \Rightarrow \\ \Rightarrow \, x_2 = x_1 - 3 \, \vee \, x_2 = x_1 + 3\\ Y el gráfico pedido es\\ set grid "on" set xlabel "x_1" set ylabel "x_2" set zeroaxis set samples 1000 plot [-4:4][-4:4] x-3, x+3 Para la clase cl[(2,2)]:\\ cl[(2,2)] = \{x \in R^2 / (x_1-x_2)^2=0 \} \, \Rightarrow \\ \Rightarrow \, x_1 = x_2 \\ Y el gráfico: \\ set grid "on" set xlabel "x_1" set ylabel "x_2" set zeroaxis set samples 1000 plot [-4:4][-4:4] x Y finalmente:\\ cl[(0,\sqrt{2})] = \{x \in R^2 / (x_1-x_2)^2 = \sqrt{2}^2 = 2 \} \, \Rightarrow \\ \Rightarrow \, x_2 = x_1 - \sqrt{2} \, \vee \, x_2=x_1+\sqrt{2} \\ Y el gráfico sería:\\ set grid "on" set xlabel "x_1" set ylabel "x_2" set zeroaxis set samples 1000 plot [-4:4][-4:4] x-sqrt(2), x+sqrt(2) ===(3)=== El conjunto cociente sería R^2|_R = \{ [(0,x)] / x \in R_{\geq 0} \} \\ (con [(0,x)] = \{a \in R^2 / (a_1-a_2)^2=x^2 \} ) \\ Considerar que para x=0 se tiene la recta x_1=x_2, y a medida que se aumenta x, una recta para para arriba y la otra para abajo, barriendo todo R^2.\\ Si se tratase con naturales, el conjunto cociente sería N^2|_R = \{[(0,x)] / x \in N_0 \} = \{ [(0,0)], [(0,1)], [(0,2)], ... \} ===== Discusión ===== Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá.