| Autor |
Mensaje |
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
Hola gente,
estoy terminando de estudiar la parte de grafos para el final y me quedaron sin resolver algunos ejercicios.
Si alguien me puede tirar alguna idea para encarar algún ejercicio se lo agradecería.
1)Determinar el número de aristas de G para que G y ~G (G complemento) sean isomorfos.
2)Probar que si un grafo no es de Euler agregando un vértice y arista se puede hacer de Euler.
3)Probar que si G es un grafo => G o ~G (G complemento) son conexos
4)Si un grafo tiene exactamente 2 vértices de grado impar, hay una trayectoria que une a esos dos vértices.
Gracias !!
Saludos.
Gonzalo
|
|
|
|
|
|
   |
    |
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
No tengo tiempo, te tiro un centro manana tranqui los resuelvo.
1) Plantea que |ag| + |agc| = |Akn|, luego para ser isomorfos tienen los mismos vertices y por isomorfismos los gr v se deben distribuir de identica forma en w (espacio de gc = g complemento), luego sum grv = sumgr w, luego AKn=n(n-1)/2, luego como las sum son iguales y la sum gr = 2|A| te queda que |Ag| = |Agc| = Akn/2 (con eso creo q estaria bien, probalo, lo hice recien sin nada de dem)
2) Si no es de Euler entonces no existe un camino que o circ q recorra todas sus aristas, esto puede ser por no ser conexo o por no existir un camino o circ que recorra todas sin repetir. Es falso por donde se mire, si repetia y no era de euler al agregar algo sigue repitiendo las anteriores y si era no conexo nada te asegura que agregando UNA arista y UN vertice deje de serlo. Algo le falta a este enunciado.
3) verdadero (falta decir que G es simple), si G es conexo verdadero, si G es no conexo demostra que es Gc lo es, para eso: Gc tiene los mismos vertices y las aristas salen de |Akn| - |Ag|, pone la condicion de que como G es no conexo y simple entonces Ag <= |v| - 2, de ahi demostras... tenes que poner que G complemento va a tocar a los aislados, etc etc
4) Esta demostracion sale viendo q es conexo, es sencilla pensala dibujando un grafo con dos vert de grado impar y algo en el medio vas a llegar que si esta cortado en el medio viola la hipotesis y si no esta cortado existe un camino entre los dos vertices de gr 1, ademas si esta cortado en el medio el vertice que corta tiene grado 1 y el subgrafo subyacente desde el inicio a ese punto de corte cumple tu hipotesis, es mas hasta lo podes reducir a que te quede dos vertices de gr 1.
Si manana no te salieron los vemos! Abrazo
|
|
|
|
_________________
arielik
[CAMPAÑA] Colaboremos entre todos por un foro más ordenado (click aquí)
[CAMPAÑA] Hacer un tópico por cada curso y con información ¡útil! (click aquí)
|
|
  |
  |
|
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
| Ídolo !! Voy a ver si logro armar alguna demostración con tu ayuda !!
|
|
|
|
|
|
| |
|
|
mart
Nivel 4
Edad: 39
Registrado: 11 Sep 2007
Mensajes: 86
Ubicación: SL
Carrera: Informática
|
|
Agrego un par que no logro resolver para ver si alguien me puede ayudar:
+ Probar que si ![[tex]T[/tex]](images/latex/d2e04dadb5f6870434e79813f5ee568b1864df29_0.png "[tex]T[/tex]") es una relación de orden en ![[tex]A[/tex]](images/latex/734ef645c78704dbe5a136258a49d8425298f623_0.png "[tex]A[/tex]") y ![[tex]B\subseteq A[/tex]](images/latex/307466aa6f4c1ab524b82f12a323476b6a9d9ae3_0.png "[tex]B\subseteq A[/tex]") entonces, si existe el supremo de ![[tex]B[/tex]](images/latex/133465fc3d126a47593d2ffc76426cb2e5e9437d_0.png "[tex]B[/tex]") es único.
+ Probar que en un álgebra de Boole con el orden definido: ![[tex]xRy \leftrightarrow x+y=y[/tex]](images/latex/ca2a61c5607d7441913e010177fc6256b7663db7_0.png "[tex]xRy \leftrightarrow x+y=y[/tex]") se cumple ![[tex]x\prec \overline y \wedge x \overline z \prec y \rightarrow y = 0 [/tex]](images/latex/40c581cd0f028d554029c426b34ac61ff1467837_0.png "[tex]x\prec \overline y \wedge x \overline z \prec y \rightarrow y = 0 [/tex]") . ( Yo llegué a: ![[tex]xy = 0 [/tex]](images/latex/5489500bf5ef0a3cf766aa87761ee6f3aefe71f0_0.png "[tex]xy = 0 [/tex]") y ![[tex]x\overline z = 0 [/tex]](images/latex/6b3e5886c4282374c54c83403718ad98c6beb1be_0.png "[tex]x\overline z = 0 [/tex]") pero de ahí no salgo).
Saludos.-
|
|
|
|
_________________
She will kiss you till your lips bleed.-
|
|
  |
 |
|
arielik
Nivel 9
Edad: 36
Registrado: 11 Sep 2007
Mensajes: 1234
Ubicación: Para mi siempre será San Telmo...
Carrera: Electrónica, Informática y Sistemas
|
|
| |
|
|
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
Hola, dejo la solución para el ejericio 1) .
Nota: supongo que se pueden reordenar los vértices de ![[tex]\overline{G}[/tex]](images/latex/a464a4e484408bc8832becb388e55872060e824c_0.png "[tex]\overline{G}[/tex]") porque sino es imposible que ![[tex]G[/tex]](images/latex/fee7794312210ac6c4e9723de4f524e55c712709_0.png "[tex]G[/tex]") y sean isomorfos para ![[tex]\left |V_G \right| \neq 1 [/tex]](images/latex/9d952f5d7551ca1f6a3a559c7e6a07ed15829f1c_0.png "[tex]\left |V_G \right| \neq 1 [/tex]") ya que y no conservan adyacencia entre vértices (condición necesaria para que dos grafos sean isomorfos)
Sabemos que ![[tex]\left |A_G \right | = \left |A_K \right | - \left |A_{\overline{G}} \right |[/tex]](images/latex/e3002b45a7ba016fa3fa7e859d560bf751fc96a8_0.png "[tex]\left |A_G \right | = \left |A_K \right | - \left |A_{\overline{G}} \right |[/tex]")
Pero para que y sean isomorfos necesitamos que tengan la misma cantidad de aristas, es decir ![[tex]\left |A_G \right | = \left |A_{\overline{G}} \right |[/tex]](images/latex/a674fd531a87b1f2c1d2908e5affefb43e79170f_0.png "[tex]\left |A_G \right | = \left |A_{\overline{G}} \right |[/tex]") . Reemplazando:
![[tex]\Rightarrow \left |A_G \right | = \left |A_K \right | - \left |A_G \right | \Rightarrow 2 \left |A_G \right | = \left |A_K \right | [/tex]](images/latex/b2a81196bc546f4a16ef5e448a3b3cfc182724c9_0.png "[tex]\Rightarrow \left |A_G \right | = \left |A_K \right | - \left |A_G \right | \Rightarrow 2 \left |A_G \right | = \left |A_K \right | [/tex]")
Además sabemos que ![[tex]\left |A_K \right | = \frac {n(n - 1)}{2}[/tex]](images/latex/c79c335699b41be1b02bdd368a72c6e4a93dff4e_0.png "[tex]\left |A_K \right | = \frac {n(n - 1)}{2}[/tex]") . Reemplazando:
![[tex]\Rightarrow 2 \left |A_G \right | = \frac {n(n - 1)}{2}[/tex]](images/latex/676d5b229e290da4c078b7f80457b37d244729a5_0.png "[tex]\Rightarrow 2 \left |A_G \right | = \frac {n(n - 1)}{2}[/tex]")
Por lo tanto, ![[tex] \left |A_G \right | = \frac {n(n - 1)}{4}[/tex]](images/latex/b8e424c23bf45adaf7960c709a0199335f328941_0.png "[tex] \left |A_G \right | = \frac {n(n - 1)}{4}[/tex]") con ![[tex]\left |A_G \right | \in{Z}[/tex]](images/latex/4ac75a8dde49cd627f00ed51c87753ba733a1aa4_0.png "[tex]\left |A_G \right | \in{Z}[/tex]")
|
|
|
|
|
|
| |
|
|
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
Respuesta al punto 2).
Si G no es de Euler entonces G es alguno de los siguientes grafos:
1) G conexo con n vértices de grado impar, n != 0, n != 2, n par (Nota: recordar que la cantidad de vértices de grado impar de un grafo siempre es un número par).
2) G no conexo
Analicemos que sucede si se agrega un vértice y una arista en ambas opciones.
1) Puedo conectar el nuevo vértice con un vértice de grado impar, entonces sigo teniendo n vértices de grado impar.
La otra opción es conectar el nuevo vértice con un vértice de grado par, entonces me quedan n + 2 vértices de grado impar.
2) Puedo agregar el nuevo vértice y arista en cualquiera componente conexa que me va a seguir quedando el grafo no conexo.
Por lo tanto la preposición es falsa.
|
|
|
|
|
|
| |
|
|
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
Ejercicio 3)
1) Si G es conexo, entonces se cumple la preposición.
2) Si G es no conexo, entonces se cumple para todo par de vértices lo siguiente:
a) dos vértices que están en distintos componentes conexas están conectadas en el grafo complementario(por definición de grafo complementario).
b) dos vértices que están en el mismo componente conexo se pueden unir a través de un vértice que este en otra componente conexa(por lo enunciado en a)).
Por lo tanto G complemento es conexo.
Ejercicio 4)
1) Si G es conexo, entonces existe un camino entre todo par de vértices, en particular para los dos vertices de grado impar.
2) Si G es no conexo, entonces cada componente conexa tiene una cantidad par de vértices de grado impar (propiedad de grados de un vértice). Entonces, la única forma de tener exactamente dos vértices de grado impar es que ambos vértices estén en una componente conexa y los demás componentes tengan ningún vértice de grado impar. Por lo tanto, como la componente que tienen los dos vértices de grado impar es conexa, existe un camino entre ambos vértices.
|
|
|
|
|
|
| |
|
|
|
|
|
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.
|
![[tex]a \in A[/tex]](images/latex/11a44a09f6533cebeca72f3ca50b4a534c6f723d_0.png "[tex]a \in A[/tex]")
supremo de B en A luego a es cota superior de B en A y si ![[tex]\exists a_1[/tex]](images/latex/9f41986ef4e568eecb30185a23cac2bb94986c47_0.png "[tex]\exists a_1[/tex]")
\ ![[tex]a_1[/tex]](images/latex/1e547402296b9e2cd0374f1927f16b056ecb7df9_0.png "[tex]a_1[/tex]")
es otra cota superior, entonces ![[tex]a \preceq a_1[/tex]](images/latex/c4969fa7f779b6bd463472b3f3ffce57a10b031d_0.png "[tex]a \preceq a_1[/tex]")
![[tex]s_1[/tex]](images/latex/678f2e4bd94ae23a7e40899d4ac1f6eeaeed3d07_0.png "[tex]s_1[/tex]")
y ![[tex]s_2[/tex]](images/latex/be6f86cd8b9bf97733c1053f24de22920f5019c7_0.png "[tex]s_2[/tex]")
supremos de B en A, luego:
![[tex]s_2 \in A \Rightarrow s_1 \preceq s_2[/tex]](images/latex/b56ea061b645ad6941e24a2c48d0224be953954c_0.png "[tex]s_2 \in A \Rightarrow s_1 \preceq s_2[/tex]")
![[tex]s_1 \in A \Rightarrow s_2 \preceq s_1[/tex]](images/latex/0602cb50a5b1533d323e0bf3dd973a9bd7c03a0d_0.png "[tex]s_1 \in A \Rightarrow s_2 \preceq s_1[/tex]")
![[tex]s_1 = s_2[/tex]](images/latex/469891eba8de1910c2b6f8d093172859b5e7f36c_0.png "[tex]s_1 = s_2[/tex]")