| Autor |
Mensaje |
JinnKaY
Nivel 9
Edad: 32
Registrado: 16 Jul 2010
Mensajes: 1445
Carrera: Electrónica y Mecánica
|
|
Final 05/08/2009:
1)b) Pide definir flujo maximal y corte minimal, en mis apuntes tengo simplemente que cuando en el teorema que piden probar en c) se cumple la igualdad ... tengo flujo maximal y corte minimal sin especificar QUE es.Incluso en el d) dice "y si se cumple la igualdad del teorema de c)?"
4)b)ii) Si B tiene exactamente n átomos ¿Cuántas clases de equivalencia hay en el conjunto cociente correspondiente a la relación R?
Cada elemento de un conjunto donde se aplique la relación esta formado por los átomos según entendi ... es decir, cada elemento que tome tiene relación directa con los mismos ... no estarian todos en la misma clase de equivalencia?!! Es decir ...1 sola?
Final xx/xx/xxxx (Sin fecha)
1)b)2) Sea en N la relación definida por ![[tex]aRb\Longleftrightarrow{a|b \vee b|a}[/tex]](images/latex/0a30231694102686a5d085806ee361206360d153_0.png "[tex]aRb\Longleftrightarrow{a|b \vee b|a}[/tex]")
Probar que es de equivalencia (YA LO HICE).Y agrega :
Restringir la relacion al conjunto ![[tex]b=\{2,3,4,5,6\}[/tex]](images/latex/368453a158a6da1073a7839324741d4ad97a2fc3_0.png "[tex]b=\{2,3,4,5,6\}[/tex]") y calcular ![[tex]cl[2][/tex]](images/latex/4f61c91950e084716da48bb87aed12d8d21e39e1_0.png "[tex]cl[2][/tex]") y![[tex]cl[3][/tex]](images/latex/02ff888ee960cfcfd1bb67e36003992de8a09cb4_0.png "[tex]cl[3][/tex]") , hallar el conjunto cociente y dibujar la particion.
Pero al momento de calcular las clases de equivalencia :
![[tex]cl[2]=\{x\in{R}:xR2\}=\{x|2 \vee 2|x\}=\{2,4,6\}[/tex]](images/latex/d7a11906d3dfa12fc3bc718450fc3051065b6d59_0.png "[tex]cl[2]=\{x\in{R}:xR2\}=\{x|2 \vee 2|x\}=\{2,4,6\}[/tex]")
![[tex]cl[3]=\{x\in{R}:xR3\}=\{x|3 \vee 3|x\}=\{3,6\}[/tex]](images/latex/26736f84be61a8f97ff49ee282a9f004e0be9dc0_0.png "[tex]cl[3]=\{x\in{R}:xR3\}=\{x|3 \vee 3|x\}=\{3,6\}[/tex]")
el 6 esta en ambos?! Creo que ESO no deberia pasar, incluso si sigo
![[tex]cl[4]=\{x\in{R}:xR4\}=\{x|4 \vee 4|x\}=\{2,4\}[/tex]](images/latex/7ee7ca477be828eb052f348b26c1764e4026616c_0.png "[tex]cl[4]=\{x\in{R}:xR4\}=\{x|4 \vee 4|x\}=\{2,4\}[/tex]")
![[tex]cl[5]=\{x\in{R}:xR5\}=\{x|5 \vee 5|x\}=\{5\}[/tex]](images/latex/77a74a606ede153788b0505d0abc15a289647fa8_0.png "[tex]cl[5]=\{x\in{R}:xR5\}=\{x|5 \vee 5|x\}=\{5\}[/tex]")
![[tex]cl[6]=\{x\in{R}:xR6\}=\{x|6 \vee 6|x\}=\{2,3,6\}[/tex]](images/latex/6b8ce0c4fa59601ca88623ee52e6a06510b1c0ec_0.png "[tex]cl[6]=\{x\in{R}:xR6\}=\{x|6 \vee 6|x\}=\{2,3,6\}[/tex]")
No deberian ser conjuntos cuya interseccion sea nula? T.T
b) Definir arbol m-ario, hoja, vertice interno y probar que siendo arbol m-ario completo tiene n vertices entonces: n=m*i+1 y h=(m-1)*i+1
arbol m-ario : Posee vertices con grado de 0 a m (si fuera completo seria 0 o m)
hoja : Posee vertices de grado- nulo (no tiene hijos)
Vertice interno : Posee vertices de grado- distinto de 0 (tiene hijos)
Ahora la parte de probar esas formulas no :P osea ... me las acuerdo pero no se como probarlas xD
Final 12/08/2009
4) a) Determinar el número de vértices de G para que G y su complemento sean árboles.
b) Lo mismo pero para ser isomorfos
a) Para que G sea arbol se debe cumplir que ![[tex]\|A_g\|=\|V_g\|-1[/tex]](images/latex/fd5627762c5527ec037da29b6f59d9ca4999d973_0.png "[tex]\|A_g\|=\|V_g\|-1[/tex]") y Llamo H al grafo complemento de G, y debe cumplir que ![[tex]\|A_h\|=\|V_h\|-1[/tex]](images/latex/8bbeae9c1c6d1284897a67ad0485125f920ac9ad_0.png "[tex]\|A_h\|=\|V_h\|-1[/tex]") . Ademas ambos deben ser conexos sin ciclos .... no se como seguir XD
b) Aca tienen que tener la misma cantidad de vertices SI o SI :P
Final 14/07/2010
2) Dada la preposición }\rightarrow{\exists{x \in{R}}:(x \in{Z}\wedge x^3-2x=0})[/tex]](images/latex/a87a13debb67d610e126dfd28eafdf45ea3c3a88_0.png "[tex](\forall{x \in{R}:x^2>0)}\rightarrow{\exists{x \in{R}}:(x \in{Z}\wedge x^3-2x=0})[/tex]")
a) Analizar el valor de verdad de la misma
b) Negar la proposicion
c) Escribir la expresion contraria,reciproca y contra reciproca, analizando su valor de verdad.
a) ![[tex]P \rightarrow{(Q \vee S)} \Rightarrow{\sim P\vee (Q\wedge S)} [/tex]](images/latex/e57052e5b2caed923b5045030e3ec39ff8f2a07c_0.png "[tex]P \rightarrow{(Q \vee S)} \Rightarrow{\sim P\vee (Q\wedge S)} [/tex]")
Entonces siempre que P sea falsa (![[tex]x^2\leq 0[/tex]](images/latex/2887acd6e2a7925ffc0c7655dc96213edd7c35b6_0.png "[tex]x^2\leq 0[/tex]") ,especificamente ![[tex]x=0[/tex]](images/latex/78e432e755209ec9b76d88d2343a181739cb28db_0.png "[tex]x=0[/tex]") ) la proposicion resulta cierta. En caso de que P sea verdadera, S resulta Falsa y por lo tanto toda la proposicion.
b) Negar la proposicion
![[tex]\sim(P \rightarrow{(Q \vee S)}) \Rightarrow{\sim(\sim P\vee (Q\wedge S)}) \Rightarrow{(P\wedge \sim(Q\wedge S)}) \Rightarrow{(P\wedge (\sim Q \vee \sim S)}) [/tex]](images/latex/d5b3c22389a2a1033de778ffa2a702bdb4063cbf_0.png "[tex]\sim(P \rightarrow{(Q \vee S)}) \Rightarrow{\sim(\sim P\vee (Q\wedge S)}) \Rightarrow{(P\wedge \sim(Q\wedge S)}) \Rightarrow{(P\wedge (\sim Q \vee \sim S)}) [/tex]")
c) Contraria : ![[tex]\sim P \rightarrow{\sim (Q \vee S)}[/tex]](images/latex/fbcb3f525ca71b26cf189839cf78e820c32e6a63_0.png "[tex]\sim P \rightarrow{\sim (Q \vee S)}[/tex]")
Si P es verdadera la proposicion es verdadera. Si P es falsa entonces S es falsa y no se cumple la proposicion.
Reciproca : ![[tex] (Q \vee S) \rightarrow{P}[/tex]](images/latex/8c9a09f1c004c4e703f128c99abd03e20304c156_0.png "[tex] (Q \vee S) \rightarrow{P}[/tex]")
Si Q es falsa o S es falsa la proposicion es verdera. Si ambos son verderos y P es falsa, la misma es falsa.
contrareciproca : ![[tex] \sim (Q \vee S) \rightarrow{\sim P}[/tex]](images/latex/0e42be922d6b45cceb27d4c6c7a9b93c1d93c8fe_0.png "[tex] \sim (Q \vee S) \rightarrow{\sim P}[/tex]")
Si Q o S son verdaderos, la proposicion es verdadera, si son falsos (algunos de los 2), y P es falsa, la proposicion tambien lo es.
3)
a)Probar que si ![[tex]G=(V;A)[/tex]](images/latex/a132243011b9710213932d2dfedc838b5e5ddef7_0.png "[tex]G=(V;A)[/tex]") es un grafo conexo y ![[tex]\|A\|=\|V\|-1[/tex]](images/latex/6294174f2f7f03e0df9bcd563d0dd6d7f502c4fa_0.png "[tex]\|A\|=\|V\|-1[/tex]") , entonces G es aciclico.
b) Analizar el valor de verdad de : es un grafo conexo y , entonces G es aciclico.
No es lo mismo en todo caso?:P Igualmente no tengo idea, me arriesgaria a decir "che, esto es un arbol" y de eso sacar lo aciclico, o suponer que tiene un ciclo, sacarle una arista y ver que deja de ser conexo.
5)
b) Verdadero o Falso.
I) Si un grafo es un ciclo de Euler entonces en el hay un ciclo de Hamilton
II) Es posible construir un arbol de 12 vertices y 70 aristas
III) Un grafo simple con 8 vertices y 13 aristas puede no ser conexo
IV) Si es bosque de 7 arboles y 40 aristas, entonces tiene 47 vertices.
I)Si es ciclo de Euler entonces pasa por todos los vertices y aristas sin repetir ... Hamilton pide pasar por todos los vertices sin repetir ... Verdadero? (OFF: Tengo que Euler tiene que pasar por aristas y vertices, y hamilton solo por vertices; pero en OTRO libro dice que Euler solo pide aristas)
II) Con ,|A|=70 y |V|=12 se ve que no cumple. FALSO?
III) Con mostrar 2 grafos es suficiente? arme uno donde es conexo y otro donde no lo es ^^. Formalmente como seria?
IV) ![[tex]\|A\|=\|V\|-k[/tex]](images/latex/64e4b8f8daabb0c6d34c7d5043fd42fdc41c1dfa_0.png "[tex]\|A\|=\|V\|-k[/tex]") , con |A|=40, |V|=47 y k=7 cumple.Verdadero?
Final : 20/07/2010
2) Demostrar :
I) Si un grafo G tiene exactamente dos vértices de grado impar hay una trayectoria entre ambos vértices.
II) El número máximo de aristas de un grafo no conexo simple con n vértices y k componentes es (n-k)(n-k+1)/2.
III) ¿Para que valores de n,un grafo completo de n vértices contiene camino de Euler pero no un circuito de Euler?
I) Supongo un grafo G que tiene u y v como vértices con grado impar, los demas de grado par. Supongo C una componente conexa que contiene a C. Como C es un grafo, debe contener un numero par de vertices de grado impar, por lo tanto contiene a V. Como C es conexa, por definicon, existe un camino de u a v y finaliza la demostracion ^^.
II) Para k=1 se cumple .... se encuentra por induccion? Para k=1 lo habia armado con la matriz de adyacencia, pero para k>1 no se me ocurre T.T
III) ¿WTF?! No me tenia que fijar en los grados de los vertices? :P
Por ahora son todas las dudas que encontre :P cualquier cosa subo mas, si algun alma caritativa me puede ayudar XD
|
|
|
|
_________________
 http://tinyurl.com/8y3ghjg
![[tex][|0|.................|25|.................|50|.................|75|.................|100|][/tex]](images/latex/effa113548b50017fcbda7adaa849d5f5c6e5965_0.png "[tex][|0|.................|25|.................|50|.................|75|.................|100|][/tex]")
![[tex][|||||||||||||||||||||||||||||||||||..............................................................][/tex]](images/latex/f4593c6130a660e6bb7c8bc60c41f8a6a69c572e_0.png "[tex][|||||||||||||||||||||||||||||||||||..............................................................][/tex]")
|
|
   |
    |
|
csebas
Nivel 9
Edad: 71
Registrado: 16 Feb 2009
Mensajes: 1634
Carrera: No especificada
|
|
Bajate el grimaldi ahi tenes varias de las definiciones....
ahora vamos por partes...
Puede que haya cosas que te diga que esten mal (lo desconosco), pero yo las creo bien, por eso te las escribo.
| Cita:
|
|
4)b)ii) Si B tiene exactamente n átomos ¿Cuántas clases de equivalencia hay en el conjunto cociente correspondiente a la relación R?
|
Para mi al tener n atomos, hay n cosas que no se relacionan entre si (el resto de los elementos son sumas de estos n) por lo tanto habria n clases. (yo lo veo asi)
| Cita:
|
|
No deberian ser conjuntos cuya interseccion sea nula? T.T
|
Estas confundiendo la definicion de particion, con clase. En las diferentes clases puede haber elementos en comun, es mas, hay clases que tiene todos sus elementos en comun.
Es en el conjunto cociente donde se evita poner las clases que contienen todos sus elementos iguales.
| Cita:
|
|
b) Definir arbol m-ario, hoja, vertice interno y probar que siendo arbol m-ario completo tiene n vertices entonces: n=m*i+1 y h=(m-1)*i+1, siendo i el numero de vertices internos
|
Te falto lo subrayado, sino es imposible.
n=m*i+1 :
El arbol tiene i vertices internos que tienen m hijos cada uno, de ahi viene el m*i, y el +1 es porque le sumas la raiz.
h=(m-1)*i+1
Vertices totales - vertices internos = (m*i +1) - i = (m-1)*i +1 (de donde saque la magica solucion de Vt - Vi....de cuando la curse)
| Cita:
|
|
4) a) Determinar el número de vértices de G para que G y su complemento sean árboles.
|
Si en algun momento la sabes, bienvenida sea la respuesta.
| Cita:
|
a)Probar que si es un grafo conexo y , entonces G es aciclico.
b) Analizar el valor de verdad de : es un grafo conexo y , entonces G es aciclico.
|
Si mal recuerdo la saque del grimaldi, o de algun libro.
a) Supone que T tiene un ciclo. Como la eliminacion de una arista de un ciclo no desconecta el grafo, podemos elimilar las aristas, pero no los vertices, de ciclos de T hasta que el grafo resultatnte T* sea conexa y aciclica. Ahora, T* es un grafo conexo y aciclico con n vertices. Entonces T* tiene n-1 aristas (esto sale de las diferentes definiciones de arboles). Pero entonces T tiene mas de n-1 aristas.
Esto es un alto absurdo. Por lo tanto, T es aciclica.
| Cita:
|
|
I) Si un grafo es un ciclo de Euler entonces en el hay un ciclo de Hamilton
|
Falso. Siempre lo supe, y despues de mucho tiempo pude encontrar un ejemplo.
*------*
| \ \ |
| * * |
| \\ |
*-----*
(espero que se entienda porq sale medio feo, son 6 vertices, y 8 aristas.
Euler pero no hamilton, asique por contraejemplo, acordatelo, sale.
II Es asi
III con armar uno que no es listo.
IV supongo que si, si cumple la formula verdadero.
| Cita:
|
Final : 20/07/2010
2) Demostrar :
I) Si un grafo G tiene exactamente dos vértices de grado impar hay una trayectoria entre ambos vértices.
II) El número máximo de aristas de un grafo no conexo simple con n vértices y k componentes es (n-k)(n-k+1)/2.
III) ¿Para que valores de n,un grafo completo de n vértices contiene camino de Euler pero no un circuito de Euler?
|
I no entendi tu demostracion, creo porque a veces pones C y quisiste decir G, o porque directamente no tengo idea.
II Ni idea.
III - supongo que habra que ir probando jeje.
------------------------------------------------------------
Te dejo algunas que yo no se....
a-Probar que en un grafo conexo cualquier par de caminos simples de longitud maxima tiene un vertice en comun
b- Probar con un ejemplo que es falso que en un grafo conexo cualquier par de caminos simples de longitud maxima tienen una arista en comun.
c- Probar que si G es un grafo aciclico entonces #A = #V -k con k la cantidad de componentes conexas de G (es la formula que usaste antes para probar que era verdadero con k=7)
|
|
|
|
Última edición por csebas el Mie Dic 21, 2011 6:41 pm, editado 1 vez
|
|
  |
 |
|
juaniii
Nivel 3
Edad: 35
Registrado: 10 Ago 2008
Mensajes: 34
Carrera: Informática
|
|
Al igual que csebas no estoy seguro que todo esté bien pero capaz te sirve mi punto de vista.
| JinnKaY escribió:
|
Final 05/08/2009:
1)b) Pide definir flujo maximal y corte minimal, en mis apuntes tengo simplemente que cuando en el teorema que piden probar en c) se cumple la igualdad ... tengo flujo maximal y corte minimal sin especificar QUE es.Incluso en el d) dice "y si se cumple la igualdad del teorema de c)?"
|
Acá tenes la teoría de Redes de transporte. Definen Flujo y Corte pero no definen el Flujo maximal ni el Corte minimal. También están los teoremas y demostraciones.
Yo creo que lo que pide es que expliques con tus palabras ya que las definiciones las das en en a)
| JinnKaY escribió:
|
4)b)ii) Si B tiene exactamente n átomos ¿Cuántas clases de equivalencia hay en el conjunto cociente correspondiente a la relación R?
|
Cabe aclarar que falta la mitad del enunciado jaja:
4. Sea B un álgebra de Boole.
b) Se define en B la relación:
![[tex]. \qquad a R b \Longleftrightarrow (a = b \vee a = \overline{b} )[/tex]](images/latex/4add2f0db58b86ba10e5a3f80717b5a6ffe69ac9_0.png "[tex]. \qquad a R b \Longleftrightarrow (a = b \vee a = \overline{b} )[/tex]")
ii) Si B tiene exactamente n átomos ¿Cuántas clases de equivalencia hay en el conjunto cociente correspondiente a la relación R?
Vemos las clases de cualquier elemento de B [/tex]](images/latex/4e7fe4325d07cb67060b5a86b9d2f53cdc8a03fa_0.png "[tex]( a \in B )[/tex]")
![[tex]a R x \quad \Longleftrightarrow \quad (a = x \vee a = \overline{x} ) [/tex]](images/latex/d6583f13ccfb655a662e9df3ee65f94700be417f_0.png "[tex]a R x \quad \Longleftrightarrow \quad (a = x \vee a = \overline{x} ) [/tex]")
Si ![[tex]a = 0 \quad \rightarrow \quad 0 = x \vee 0 = \overline{x} \quad \rightarrow \quad x = 1 \vee x = 0 [/tex]](images/latex/46ac395ea59b8442e7857313f0b3147c4c76a3f4_0.png "[tex]a = 0 \quad \rightarrow \quad 0 = x \vee 0 = \overline{x} \quad \rightarrow \quad x = 1 \vee x = 0 [/tex]")
por lo tanto [/tex]](images/latex/284e6b177de278dc3f85432c972fee5bcec11643_0.png "[tex]( 0 , 1 \in cl[0] )[/tex]") y como demostramos en a) que es una relación de equivalencia se tiene que
[/tex]](images/latex/d6f279f6e7a5895215dd530d4b240efeaf9703e5_0.png "[tex]( cl[0] = cl[1] = \{ 0 , 1 \} )[/tex]")
Ahora si ![[tex]a \not= 0 \wedge a \not= 1 [/tex]](images/latex/0dbd71c439e8ee3664979eb5a8cccd35ea81388f_0.png "[tex]a \not= 0 \wedge a \not= 1 [/tex]") lo que nos queda son los átomos:
si por ejemplo tenemos 4 átomos ![[tex]\{ x_{0}, x_{1}, x_{2}, x_{3} \} [/tex]](images/latex/cddb448f3e02c3b00d7816365f58bae337f0894b_0.png "[tex]\{ x_{0}, x_{1}, x_{2}, x_{3} \} [/tex]") se da que:
![[tex] a = x_{1} \rightarrow \overline{a} = x_{0} + x_{2} + x_{3}[/tex]](images/latex/932193b518d2553dcf97d1acbb216052df7b9c3d_0.png "[tex] a = x_{1} \rightarrow \overline{a} = x_{0} + x_{2} + x_{3}[/tex]")
es decir, la negación de ![[tex] x_{1} [/tex]](images/latex/1425f645a29e89aee1ca5fad58dc1737648fab52_0.png "[tex] x_{1} [/tex]") es la suma de los átomos restantes
Entonces, si ![[tex]a = x_{1} \quad \rightarrow \quad x_{1} R x \quad \rightarrow \quad x_{1} = x \vee x_{1} = \overline{x} \quad \rightarrow \quad x = x_{1} \vee x = x_{0} + x_{2} + x_{3} [/tex]](images/latex/4a433da5af2e3d7b85e9108e48f7aeafa8eff67d_0.png "[tex]a = x_{1} \quad \rightarrow \quad x_{1} R x \quad \rightarrow \quad x_{1} = x \vee x_{1} = \overline{x} \quad \rightarrow \quad x = x_{1} \vee x = x_{0} + x_{2} + x_{3} [/tex]")
Por lo tanto la clase de equivalencia de es:
![[tex] cl[x_{1}] = cl[x_{0} + x_{2} + x_{3}] = \{ x_{1} ,\ x_{0} + x_{2} + x_{3} \} [/tex]](images/latex/f44da52c6f4cb4b9cb9c0f370738a0fcfd66fff9_0.png "[tex] cl[x_{1}] = cl[x_{0} + x_{2} + x_{3}] = \{ x_{1} ,\ x_{0} + x_{2} + x_{3} \} [/tex]")
En conclusión, cada clase de equivalencia tiene un elemento de B y su negación por lo tanto la cantidad de clases será la cantidad de elementos dividido 2:
![[tex] \# B = 2^n \rightarrow \mbox{ Cantidad de clases } = \frac{\# B}{2} = \frac{2^n}{2} = 2^{n-1} [/tex]](images/latex/cb957bdd208cf03d412751909d3b7e424b61ba39_0.png "[tex] \# B = 2^n \rightarrow \mbox{ Cantidad de clases } = \frac{\# B}{2} = \frac{2^n}{2} = 2^{n-1} [/tex]")
| JinnKaY escribió:
|
Final xx/xx/xxxx (Sin fecha):
1)b)2) Sea en N la relación definida por...
|
El problema está en que ![[tex]R[/tex]](images/latex/06bb2956f6ba6274346e5b9e386e2e81f25a8632_0.png "[tex]R[/tex]") no es transitiva ![[tex]\rightarrow[/tex]](images/latex/0c89e795172728eb53d5b86aac2d8c0d59994eda_0.png "[tex]\rightarrow[/tex]") no es de equivalencia
![[tex]R\ es\ transitiva \Longleftrightarrow \forall a,b,c \in A : a R b \wedge b R c \Rightarrow a R c [/tex]](images/latex/954dbffab3eba318a9bdaab91a92b901f0bf5984_0.png "[tex]R\ es\ transitiva \Longleftrightarrow \forall a,b,c \in A : a R b \wedge b R c \Rightarrow a R c [/tex]")
Hipótesis: ![[tex] ( a=kb \quad \vee \quad b=k'a ) \wedge ( b=k''c \quad \vee \quad c=k'''b ) [/tex]](images/latex/e7a44395c6b669ca665f505eafd3ae5a63908075_0.png "[tex] ( a=kb \quad \vee \quad b=k'a ) \wedge ( b=k''c \quad \vee \quad c=k'''b ) [/tex]")
si desarrollamos...
![[tex] ( a=kb \wedge b=k''c )\quad \vee \quad ( a=kb \wedge c=k'''b ) \quad\vee\quad (b=k'a \wedge b=k''c )\quad \vee \quad (b=k'a \wedge c=k'''b )[/tex]](images/latex/ac82cdacf6c995a0b5675dc9fd022f19a72eb22d_0.png "[tex] ( a=kb \wedge b=k''c )\quad \vee \quad ( a=kb \wedge c=k'''b ) \quad\vee\quad (b=k'a \wedge b=k''c )\quad \vee \quad (b=k'a \wedge c=k'''b )[/tex]")
Se pueden dar estos 4 casos, hay que demostrar para cada uno. Fijate que en N no se cumple en todos los casos.
Por ejemplo :  \rightarrow c=\frac{k'''a}{k}[/tex]](images/latex/eef02c6d3711bc04a35c8dc8e0b6df3a8458e559_0.png "[tex]( a=kb \wedge c=k'''b ) \rightarrow c=\frac{k'''a}{k}[/tex]")
A mi también se me escapó y llegué a lo mismo que vos.
| JinnKaY escribió:
|
Final 12/08/2009 :
4) a) Determinar el número de vértices de G para que G y su complemento sean árboles.
|
Para que ![[tex]G[/tex]](images/latex/fee7794312210ac6c4e9723de4f524e55c712709_0.png "[tex]G[/tex]") y ![[tex]\overline{G}[/tex]](images/latex/a464a4e484408bc8832becb388e55872060e824c_0.png "[tex]\overline{G}[/tex]") sean árboles para empezar:
1. los 2 tienen la misma cantidad de vértices (por la definición de complemento)
2. los 2 tienen la mínima cantidad de aristas ( ![[tex]|A| = |V| - 1[/tex]](images/latex/c4c7af57d8d662618156484ea6296561f519e8bd_0.png "[tex]|A| = |V| - 1[/tex]") )
3. sabemos que la suma de las aristas da la cantidad aristas de un Completo n ![[tex]|A| + \overline{|A|} = |A_{Kn}|[/tex]](images/latex/1b316af60f8db5f744e56a9d4419c3c08697bfd8_0.png "[tex]|A| + \overline{|A|} = |A_{Kn}|[/tex]") por la definición de complemento
de 1. y 2. sacamos que ![[tex]|A| = \overline{|A|} [/tex]](images/latex/0960031969133b5a297d7500677197ded3e47073_0.png "[tex]|A| = \overline{|A|} [/tex]")
entonces de 3. ![[tex]|A| + |A| = 2|A| = |A_{Kn}|[/tex]](images/latex/7ad4b5976550740de282eab1100c9e90ba3d9363_0.png "[tex]|A| + |A| = 2|A| = |A_{Kn}|[/tex]")
Luego ![[tex] |A| = \frac{|A_{Kn}|}{2}[/tex]](images/latex/5c7ea51f531c917bb86f720f0247c6d7e132b377_0.png "[tex] |A| = \frac{|A_{Kn}|}{2}[/tex]")
reemplazando ![[tex]|A_{Kn}| = \frac{n(n-1)}{2}[/tex]](images/latex/265eac592db589027c73b81a1be220b5d9986a98_0.png "[tex]|A_{Kn}| = \frac{n(n-1)}{2}[/tex]") y por ser árbol ![[tex]|A|=n-1[/tex]](images/latex/489279e8f07604dca6f4c6fcdaf8c411547cf01b_0.png "[tex]|A|=n-1[/tex]")
![[tex]n - 1 = \frac{\frac{n(n-1)}{2}}{2} [/tex]](images/latex/66f8de6d355b8a784a50ad94e64302d0527acefa_0.png "[tex]n - 1 = \frac{\frac{n(n-1)}{2}}{2} [/tex]")
queda una cuadrática igualada a 0: ![[tex]n^2 - 5n + 4 = 0[/tex]](images/latex/fbf70f5de7ee4793e9e32df630744a38ab6ab9e3_0.png "[tex]n^2 - 5n + 4 = 0[/tex]") los resultados son ![[tex]n_{1} = 1 [/tex]](images/latex/388d8033b6369bd7431e3cb3af7bef73df45d579_0.png "[tex]n_{1} = 1 [/tex]") y ![[tex] n_{2} = 4[/tex]](images/latex/9f195e103e6ce36b62e35e1f1e4b233f0454adac_0.png "[tex] n_{2} = 4[/tex]")
Para que sean isomorfos:
1. Los 2 tienen la misma cantidad de vértices
2. Los 2 tienen que tener la misma cantidad de aristas (sino no son isomorfos)
Bueno haciendo un análisis parecido al anterior llegué a esto:
![[tex] \frac{\frac{n(n-1)}{2}}{2} = |A| [/tex]](images/latex/b766a4eb873b9dc56835630faa44426b94d1d935_0.png "[tex] \frac{\frac{n(n-1)}{2}}{2} = |A| [/tex]")
bueno sabiendo que n y |A| son Naturales + 0 ![[tex] \rightarrow n = \{ 0, 1, 4, 5, 8,9, ...\} [/tex]](images/latex/3a06765e037f6244da71afad398fcad7d8cc5075_0.png "[tex] \rightarrow n = \{ 0, 1, 4, 5, 8,9, ...\} [/tex]")
| JinnKaY escribió:
|
Final 14/07/2010:
2) Dada la preposición...
|
2)a) ![[tex] \forall x\ \in\ R :\ x^2\ >\ 0 [/tex]](images/latex/477091b1f6c9331e66de7758bf294c62e8d7d874_0.png "[tex] \forall x\ \in\ R :\ x^2\ >\ 0 [/tex]") : Falso. pe: ![[tex] x = 0 [/tex]](images/latex/5b57e6869288771ca517b89883413c8677c4b5d6_0.png "[tex] x = 0 [/tex]")
![[tex] \exists x\ \in\ R : ( x\ \in\ Z\ \wedge \ x^3 - 2x = 0 ) [/tex]](images/latex/91499181f41629886996d31143e11c229579dbf2_0.png "[tex] \exists x\ \in\ R : ( x\ \in\ Z\ \wedge \ x^3 - 2x = 0 ) [/tex]") : Verdadero. Pe
![[tex] Falso\ \rightarrow\ Verdadero = Verdadero [/tex]](images/latex/bd987caf6f7c05141db9f30b35bd678f4e0586b5_0.png "[tex] Falso\ \rightarrow\ Verdadero = Verdadero [/tex]")
b) Negar un ![[tex]P \rightarrow Q [/tex]](images/latex/bb21f26471fea7d64539480d7727a1f26d9b0aa4_0.png "[tex]P \rightarrow Q [/tex]") si no me equivoco es ![[tex]P \wedge ¬Q [/tex]](images/latex/a0abd588cd5c9c412c47a71e1ce1e87ed8e6acc4_0.png "[tex]P \wedge ¬Q [/tex]")
Entonces: ![[tex] (\forall x\ \in\ R :\ x^2\ >\ 0 ) \ \wedge\ [/tex]](images/latex/265b3ccd92cf43dfcc3b8fea261b606af136c42d_0.png "[tex] (\forall x\ \in\ R :\ x^2\ >\ 0 ) \ \wedge\ [/tex]") ![[tex] \forall x\ \in\ R : ( x\ \notin\ Z\ \vee \ x^3 - 2x \not= 0 ) [/tex]](images/latex/cc545578d045267f0f1a7beb0e443d1314e3df8c_0.png "[tex] \forall x\ \in\ R : ( x\ \notin\ Z\ \vee \ x^3 - 2x \not= 0 ) [/tex]")
c) Contraria:
Reciproca: ![[tex]Q \rightarrow P[/tex]](images/latex/62eece26c632daa55e5f1b34e0f4ce4516320e63_0.png "[tex]Q \rightarrow P[/tex]")
Contrareciproca: ![[tex]¬Q \rightarrow ¬P[/tex]](images/latex/66ff7a2924893720040499d8cd127ba0705bc751_0.png "[tex]¬Q \rightarrow ¬P[/tex]")
3) a) La cantidad mínima de aristas para un grafo conexo es
Si este grafo tuviera un ciclo significa que existen 2 caminos que conectan a 2 vértices. Por lo tanto podríamos desconectar uno sin que deje de ser conexo ya que quedaría el otro camino. Entonces sacando esta arista queda ![[tex]|A| = |V| - 2[/tex]](images/latex/e0e3ec13cc31d5681243384d8c3de4fdf35e4efc_0.png "[tex]|A| = |V| - 2[/tex]") lo cual es un absurdo ya que la cantidad mínima de aristas para un grafo conexo es
b) Me parece que es NO conexo
5)
b) Verdadero o Falso.
I) Si un grafo es un ciclo de Euler entonces en el hay un ciclo de Hamilton
Como no se dibujar te paso la matriz de adyacencia
![[tex]M_{A} = \left( \begin{array}{ccccc} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0\end{array} \right)[/tex]](images/latex/5965cdb1681fe0f5c6a2e7943764ab713b953803_0.png "[tex]M_{A} = \left( \begin{array}{ccccc} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0\end{array} \right)[/tex]")
Tiene un ciclo de Euler pero no un ciclo de Hamilton (ya que para que se forme el cliclo tiene que pasar 2 veces por el vértice C)
II) coincido con vos
III) Calculo que con solo un ejemplo de que se puede dar ya está
IV) también coincido
| JinnKaY escribió:
|
Final : 20/07/2010
2) Demostrar :
I) Si un grafo G tiene exactamente dos vértices de grado impar hay una trayectoria entre ambos vértices.
II) El número máximo de aristas de un grafo no conexo simple con n vértices y k componentes es (n-k)(n-k+1)/2.
III) ¿Para que valores de n,un grafo completo de n vértices contiene camino de Euler pero no un circuito de Euler?
|
I) En realidad creo que es más fácil: Sabiendo que hay exactamente 2 vértices de grado impar entonces se cumple el teorema de Euler y por lo tanto existe un camino que une esos dos vértices de grado impar.
II) Este es la muerte! No lo copio porque es larguísimo adentro metí una ecuación de recurrencia, un análisis de función con derivada, el desarrollo de una sumatoria (lo único que me faltaba meter era una transformada de laplace jaja)
Bueno lo pensé calculando para algún n (vértices) cual es la cantidad de vértices que me conviene "separar" del grafo de forma tal que la cantidad de aristas que pierda sea la mínima. Ahí metí la ecuación de recurrencia y el análisis jaja. El resultado es que hay q separa solo 1 vértice. Entonces si querés 3 componentes conexas x ejemplo te conviene un grafo completo de n - 2 y 2 vértices aislados.
saludos!
|
|
|
|
|
|
 |
 |
|
csebas
Nivel 9
Edad: 71
Registrado: 16 Feb 2009
Mensajes: 1634
Carrera: No especificada
|
|
| juaniii de lo que puse yo al final de mi post sabes alguno?
|
|
|
|
|
|
| |
|
|
juaniii
Nivel 3
Edad: 35
Registrado: 10 Ago 2008
Mensajes: 34
Carrera: Informática
|
|
| csebas escribió:
|
Te dejo algunas que yo no se....
a-Probar que en un grafo conexo cualquier par de caminos simples de longitud maxima tiene un vertice en comun
b- Probar con un ejemplo que es falso que en un grafo conexo cualquier par de caminos simples de longitud maxima tienen una arista en comun.
c- Probar que si G es un grafo aciclico entonces #A = #V -k con k la cantidad de componentes conexas de G (es la formula que usaste antes para probar que era verdadero con k=7)
|
a. A ver, pasamos la proposición a lenguaje lógico
Grafo conexo ![[tex]\Rightarrow\ \forall[/tex]](images/latex/76276a44ccf0e05ccdf27ed5a82b4b47f88d7ab5_0.png "[tex]\Rightarrow\ \forall[/tex]") par de caminos simples de longitud máxima tienen un vértice en común
Probar ![[tex]P \Rightarrow Q [/tex]](images/latex/595c5d1b0f264704298071beba71e664915464a6_0.png "[tex]P \Rightarrow Q [/tex]") es equivalente a probar ![[tex]¬Q \Rightarrow ¬P [/tex]](images/latex/65928162097a99345049c65d1440a89bd161fcc7_0.png "[tex]¬Q \Rightarrow ¬P [/tex]") (la contra-reciproca)
Suponemos que ![[tex]\exists[/tex]](images/latex/0d2870a48f57168a8635684aaba790fe9df8a5b6_0.png "[tex]\exists[/tex]") dos caminos simples de longitud máxima y SIN vértices en común (![[tex]¬Q [/tex]](images/latex/cf93882e65f547daf315c129cab66a8be54e904b_0.png "[tex]¬Q [/tex]") ). Los llamamos ![[tex]C_{1}[/tex]](images/latex/99febe069c8d311a9ea981a3e6d5f6914f37d051_0.png "[tex]C_{1}[/tex]") y ![[tex]C_{2}[/tex]](images/latex/3c5b8c77fa4c2567d17ac5c0019917e83caac6ca_0.png "[tex]C_{2}[/tex]") . Si fuese un grafo conexo existiría otro camino ![[tex]C_{3}[/tex]](images/latex/a121bc2c2cc416aa313364824351f6f99bf354c4_0.png "[tex]C_{3}[/tex]") que conecte algún vértice ![[tex] v\ \in\ C_{1}[/tex]](images/latex/c0692c3c0ba47db472c8382f422eff51e22b1c7c_0.png "[tex] v\ \in\ C_{1}[/tex]") con algún otro ![[tex]w\ \in\ C_{2}[/tex]](images/latex/316d7b9e5a3c80597c0172d240c087b9c8e25ceb_0.png "[tex]w\ \in\ C_{2}[/tex]") . Concentrémosnos en la longitud de , si y se conectan por una sola arista (lo mínimo para que no compartan vértices pero estén conectados y sea conexo) entonces la mínima longitud de es ![[tex]|C_{3}|=\frac{|C_{1}|}{2} +\frac{|C_{2}|}{2} + 1[/tex]](images/latex/605cc027ec759519a18bc704d9ef4f56b120bf97_0.png "[tex]|C_{3}|=\frac{|C_{1}|}{2} +\frac{|C_{2}|}{2} + 1[/tex]") (notá que la longitud de es 1 más que la longitud de los caminos máximos) por lo tanto es un camino más largo que los máximos, lo cual contradice la hipótesis. Entonces el grafo no puede ser conexo (![[tex]¬P [/tex]](images/latex/89173fe6f7edbb08e16dd550a964a36a774cde07_0.png "[tex]¬P [/tex]") ).
b. Un árbol cuaternario completo con 5 vértices? quedaría como una cruz, 4 vértices conectados a uno en el medio. Bueno ahí hay 2 caminos de longitud 2 que no comparten ninguna arista.
c. Grafo Acíclico con ![[tex]k[/tex]](images/latex/de61dde472a066a5b90a2ff0be7a2f756110011b_0.png "[tex]k[/tex]") componentes conexas ![[tex]\Rightarrow\ |A| = |V| - k[/tex]](images/latex/c602b3fae29b9eb16eba599e3da0d8ed0542933a_0.png "[tex]\Rightarrow\ |A| = |V| - k[/tex]") .
Siendo ![[tex]G_{k}[/tex]](images/latex/feab44e90d902a554fcd431956293f7a6593dc33_0.png "[tex]G_{k}[/tex]") un grafo acíclico y con componentes conexas entonces se pueden agregar ![[tex]k-1[/tex]](images/latex/b3979b36c4a51ca1b373f9dea102aac526b6c547_0.png "[tex]k-1[/tex]") aristas de forma tal que conecte cada componente conexa y siga siendo acíclico (ya que por cada arista agregada, generamos un camino entre vértices que antes no tenían un camino).
Ahora, si es acíclico y conexo es un árbol por definición, por lo tanto se cumple que (la cantidad mínimas de aristas para un grafo conexo). Si yo agregué aristas ahora se las saco: ![[tex]|A_{k}|\ =\ |A|\ -\ (k-1) = |V| - 1 - (k - 1) = |V| - k[/tex]](images/latex/204f3a3c5de27b8380edc3d61f35e8e4de6b1cd9_0.png "[tex]|A_{k}|\ =\ |A|\ -\ (k-1) = |V| - 1 - (k - 1) = |V| - k[/tex]") y tarán!!!
|
|
|
|
|
|
| |
|
|
csebas
Nivel 9
Edad: 71
Registrado: 16 Feb 2009
Mensajes: 1634
Carrera: No especificada
|
|
Estuve dando muchas vueltas con este ejercicio, hasta que (supongo) me ilumine y llegue a la siguiente conclusion
| Cita:
|
Final : 20/07/2010
2) Demostrar :
III) ¿Para que valores de n,un grafo completo de n vértices contiene camino de Euler pero no un circuito de Euler?
|
Condicion para camino: tener exactamente 2 vertices de grado impar
Condicion para circuito: no tener ninguno impar (osea todos par)
En todo grafo Kn, tenemos que el grado de los vertices es n-1, por lo tanto
Si n=1, tiene 1 vertice de grado 0 y no tiene camino ni circuito.
Si n=2, tiene 2 vertices de grado 1-> tiene un circuito y no un camino (respuesta)
Y de ahora en mas no existen mas caminos de euler, solo circuitos
Explicacion....
Para n>2
Si n=3, tiene 3 vertices de grado 2, es un circuito.
Si n=4, tiene 4 vertices de grado 3, no es nada.
Si n=5, tiene 5 vertices de grado 4, es un circuito.
Si n=6, tiene 6 vertices de grado 5, no es nada.
y de aca sale una conclusion(a demostrar :p)
si n>2 y n es par no es nada
si n>2 y n es impar, es un circuito.
Que opinan?
|
|
|
|
|
|
| |
|
|
pinus
Nivel 4
Edad: 36
Registrado: 20 Ene 2009
Mensajes: 100
Carrera: Informática, Sistemas y
|
|
| juaniii escribió:
|
4)b)ii) Si B tiene exactamente n átomos ¿Cuántas clases de equivalencia hay en el conjunto cociente correspondiente a la relación R?
En conclusión, cada clase de equivalencia tiene un elemento de B y su negación por lo tanto la cantidad de clases será la cantidad de elementos dividido 2:
|
Juanii estoy de acuerdo con el resultado que pusiste para la cantidad de clases de equivalencia en el ejercicio 4-b, lo unico que no puedo ver tan claro es porque luego de estudiar la clase del 0 y el 1 se puede afirmar que si a no es el minimo ni el maximo lo unico que restan son los atomos.
Creo que con mostrar la clase del 0 y el 1 y mencionar el hecho de que el complemento es unico para cada elemento podría responderse la cantidad de clases y se usaria el dato de la cantidad de atomos para lo que lo usaste vos que es para sacar la cantidad de elementos.
|
|
|
|
|
|
  |
|
|
pinus
Nivel 4
Edad: 36
Registrado: 20 Ene 2009
Mensajes: 100
Carrera: Informática, Sistemas y
|
|
| csebas escribió:
|
Estuve dando muchas vueltas con este ejercicio, hasta que (supongo) me ilumine y llegue a la siguiente conclusion
| Cita:
|
Final : 20/07/2010
2) Demostrar :
III) ¿Para que valores de n,un grafo completo de n vértices contiene camino de Euler pero no un circuito de Euler?
|
Condicion para camino: tener exactamente 2 vertices de grado impar
Condicion para circuito: no tener ninguno impar (osea todos par)
En todo grafo Kn, tenemos que el grado de los vertices es n-1, por lo tanto
Si n=1, tiene 1 vertice de grado 0 y no tiene camino ni circuito.
Si n=2, tiene 2 vertices de grado 1-> tiene un circuito y no un camino (respuesta)
Y de ahora en mas no existen mas caminos de euler, solo circuitos
Explicacion....
Para n>2
Si n=3, tiene 3 vertices de grado 2, es un circuito.
Si n=4, tiene 4 vertices de grado 3, no es nada.
Si n=5, tiene 5 vertices de grado 4, es un circuito.
Si n=6, tiene 6 vertices de grado 5, no es nada.
y de aca sale una conclusion(a demostrar :p)
si n>2 y n es par no es nada
si n>2 y n es impar, es un circuito.
Que opinan?
|
Me parece que esta bien y no creo que sea necesario hacer la demostracion que mencionas al final ya que estas usando correctamente la definicion de grafo completo.
Es mas calculo que no te habrian hecho problema si no descartabas el caso especial de n=1 cuando estudiaste si había camino o no de euler. Aunque esta claro que un camino no puede existir sin involucrar al menos una arista.
Una ultima cosa, supongo que habra sido un typo ...
| Cita:
|
Si n=2, tiene 2 vertices de grado 1-> tiene un circuito y no un camino (respuesta)
|
Tiene camino y no un circuito.
Mañana a las 9am aprobamos todos 
|
|
|
|
|
|
| |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
