Foros de matemática
23/10/2014, 11:26:32 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Ejercicio de grafos y árboles, variados.  (Leído 6810 veces)
0 Usuarios y 1 Visitante están viendo este tema.
cristianll
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 236


Ver Perfil
« : 22/06/2008, 11:18:43 pm »

Hola, como están, estoy haciendo unos ejercicio que me piden que lleve realizados y quería saber si los hice bien.

1)Escriba siempre que sea posible:

a) La definición de trayectoria entre vértices y de una gráfica:
R:Sean y los vértices en una gráfica.Una trayectoria de a de longitud 1 es una sucesión alternante de vértices y arista que comienza en el vértice y termina en , simbólicamente sería

b) El conjunto de vértices y aristas de un grafo no conexo con dos componentes conexas,4 vértices y 13 aristas
R: no sé si se puede realizar por que son demasiadas aristas para 4 vértices, no logro realizarlo

c) El requisito que debe cumplir una gráfica para ser simple
R:No tener lazos ni aristas paralelas.

2)Pruebe o refute las siguientes proposiciones:

a)El grafo dado por y es conexo y bipartito
R:Falso? o existe una trayectoria entre el vértice y el vacío?
b)Si es un árbol entonces no es una gráfica bipartita
R:Falso?
c) Ningún árbol es una gráfica completa
R=Falso, contraejemplo
d)Toda subgráfica de una gráfica bipartita es bipartita
R:Falso? tomamos 2 vértices con 1 arista, es bipartita, luego una subgráfica los 2 vértices sin la arista no es bipartita?
e)Las subgráficas de una gráfica conexa, son conexas
R:Falso
f)Toda gráfica bipartita sin vértices aislados admite sólo una partición en el conjunto de vértices
R:Falso?

3)Escriba siempre que sea posible:

a) Un ejemplo de gráfica para la que , siendo y
R:No se puede hacer, la sumatoria de los grados siempre es par?
b) Una gráfica con un número par de vértices de grado par
R:No se puede hacer ya que si hay número par de vértices el grado es impar

4)Pruebe o refute

a) Si tiene 2 componentes conexas entonce admite circuito de Euler
R:Falso, la gráfica debe ser conexa y acá no es conexa porque tiene más de 1 componente conexo
b) Sea una gráfica conexa, tiene un circuito de Euler si y sólo si todo vértice de tiene grado par
R:Verdadera. Sea el vértice donde comienza el circuito de Euler. Para cualquier otro vértice de , cada vez que el ciclo llegue allí, partirá de ese vértice. Así, el circuito ha pasado por 2 aristas nuevas con él o por un lazo de él. En cada caso se añade 2 al grado de ese vértice. Como ese vértice no es un punto inicial, se añade 2 cada vez que el ciclo pasa por de modo que el grado de es par.
En el vértice (inicial), la primera arista del cico debe ser distinta de la última,y de cualquier otra que pase por , por tanto, se tiene que el grado de también es par.
Pero ahora no sé cómo hacer el recíproco.

5)Escriba cuando sea posible:

a) Dé la definición de isomorfismo de gráficas y la definición de gráficas isomorfas.
b) Tres condiciones necesarias para que 2 gráficas sean isomorfas.
c) Los dibujos de todas las gráficas no isomorfas, sin ciclos y conexas que tengan 5 vértices.

Acá no encuentro qué poner, porque no encuentro la definición de isomorfismo de gráficas(la de gráficas isomorfas si la tengo, sólo no encuentro isomorfismo de gráficas).

6)Lea la siguiente definición:

Sean y árboles, con raíces y respectivamente. Los árboles y son isomorfos si existe una función uno a uno y sobre el conjunto de vértices de al conjunto de vértices de que satisfaga lo siguiente:
i) Los vértices y son adyacente en si y sólo si los vértices y son adyacentes en
ii)

a) Dé un ejemplo de 2 árboles de jerarquía distintos que sean isomorfos (Acá que se refiere con árbol de jerarquía, árboles con funciones de algún lugar?)
b) ¿Puede asegurar que 2 árboles isomorfos son 2 gráficas isomorfas? Justifique exhaustivamente su respuesta

7)Pruebe o refute:

a) Si 2 gráficas tienen la misma cantidad de vértices con el mismo grado, entonces son isomorfas
b) Si las gráficas tiene la misma cantidad de vértices y aristas y admiten ciclos de Euler entonces son isomorfas
c) Si 2 gráficas son isomorfas y una admite ciclo hamiltoniano, entonces la otra también
d) Un árbol sólo puede ser isomorfo a otro árbol


Si me pueden dar unas ideas para estos muchas gracias
Muchas gracias.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 29.515


Ver Perfil
« Respuesta #1 : 23/06/2008, 06:08:45 am »

Hola

 1) a) ¿Por qué defines trayectoria de longitud y no de otras longtiudes?.

     b) Suponiendo que no admitimos una arista de un vértices sobre si mismo ni aristas "repetidas", el número máximo de aristas de un grafo de vértices es . Por tanto efectivamente tu grafo no existe.

     c) Está bien. Teniendo en cuenta esto, si en (b) supones que tus lazos pueden NO ser simples si que existiría un grafo en las condiciones dadas. ¿Lo ves?.

 2) a) Puede considerarse grafo bipartito con  la partición , . Lo único que hay que exigirle es que no haya aristas uniendo vértices dentro de cada partición y eso lo cumple.

 b) Por ejemplo toma dos vértices unidos por una arista.

 c) OK.

 d) Verdadero. Fíjate que en una gráfica bipartita (al menos con la definición que yo conozco) sólo necesitas dividir el grafo en dos conjunto de vértices, de manera que dentro de cada uno de ellos no haya aristas. Pero no necesitas que todos los vértices de un trozo estén unidos con todos los del otro (eso sería un grafo bipartito COMPLETO).

 e) Si, pero pon un ejemplo.

 f) FALSO. Piensa es cuatro vértices unidos dos a dos.

Saludos.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 29.515


Ver Perfil
« Respuesta #2 : 23/06/2008, 06:27:49 am »

Hola

 3) a) OK.

     b) Un cuadrado.

 4) a) OK.
     b) http://lambda.fciencias.unam.mx/~elisa/NotasDeCursos/Discretas/Graficas-2x1.pdf
     (página 163)

 5) a) ¿Cuál es la qué tienes de gráficas isomorfas?.
     b) Si son isomorfas conservan las mismas propiedades como grafos: componentes conexas, número de vértices, de aristas, existencia o no de ciclos,.... TODO.
     c) No tienen porqué tener ciclos. Por ejemplo:



Saludos.

* grafo5.JPG (1.83 KB - descargado 2308 veces.)
En línea
cristianll
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 236


Ver Perfil
« Respuesta #3 : 23/06/2008, 12:15:49 pm »

Hola, muchas gracias el_manco me aclaraste muchas dudas,por otro lado la definición que tengo de que dos gráficas son isomorfas es la siguiente:
Las gráficas y son isomorfas si existe una función uno a uno y sobre de los vértices de a los vértices de y una función uno a uno y sobre de las aristas de a las aristas de .
Y la de isomorfismo de gráficas puede ser : Una arista es incidente en y en si y sólo si la arista es incidente en y en . El par de funciones f y g reciben el nombre de isomorfismo de en :¿eh?:?
El 5b) serían tres condiciones:
.)Tener la misma cantidad de vértices
.)Tener la misma cantidad de aristas
.)Tener el mismo ciclo o circuito

Y el 5c) sólo va a tener una gráfica, la que vos dejaste, porque estoy haciendo otras pero son iguales?

Muchas gracias
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 29.515


Ver Perfil
« Respuesta #4 : 23/06/2008, 12:28:10 pm »

Hola

 Efectivamente dos gráficas son isomorfas si existe un isomorfismo entre ellas. Un isomorfismo es una aplicación biyectiva entres sus vértices y que además verifica que en el grafo inicial dos vértices están unidos por una arista si y sólo si lo están en el final.

 En cuanto al 5b) quizá tener "el mismo ciclo o circuito" es una condición poco clara. ¿A qué te refieres?. Puedes decir por ejemplo que tiene el mismo grado, o el mismo número de componentes conexas. Por supueso hay cientos de propiedades que podrías citar, es decir no pienses que sólo pueden darse tres condiciones necesarias concretas.

 Finalmente otro ejemplo de gráfo con cinco vértices, conexo y sin ciclos:



 Pero hay más...

Saludos.

* grafo51.JPG (1.58 KB - descargado 2175 veces.)
En línea
cristianll
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 236


Ver Perfil
« Respuesta #5 : 23/06/2008, 12:36:28 pm »

Muchas gracias nuevamente, ya comprendí, sé que tengo dudas pero es que estoy por rendir y necesito presentar estas preguntas, y el ejercicio referido en este post, no sé si sabés como hacerlo, yo lo hice pero no sé si está bien a lo que llegué. http://www.rinconmatematico.com/foros/index.php?topic=13169.0

Muchas gracias.

PD:Usas un programa para realizar los grafos?
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 29.515


Ver Perfil
« Respuesta #6 : 23/06/2008, 12:41:40 pm »

Hola

Cita
PD:Usas un programa para realizar los grafos?

 El GeoGebra.

Saludos.
En línea
cristianll
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 236


Ver Perfil
« Respuesta #7 : 23/06/2008, 09:04:27 pm »

Hola, para el 6) está bien decir que el árbol con raíz vértices y con aristas es isomorfo al árbol con raíz vértices y aristas , con
.Y si es correcto para demostrar que son gráficas isomorfas tengo que demostrarlo diciendo en lo que son equivalente(es decir,vértices,aristas,ciclos,...) o mediante algún teorema o propiedad por ejemplo el que los vértices adyacentes en deben ser adyacentes en tomando con el conjunto de aristas?
Y luego para asegurar que dos árboles isomorfos son 2 gráficas isomorfas, y me pide que justifique exhaustivamente, no comprendo muy bien que demostración hacer.

Luego para el 7) en el a) sería falsa con el contraejemplo de la gráfica con y y luego la gráfica con y aristas no son isomorfas porque tienen diferentes aristas???, para el b) no logro llegar bien a la conclusión, para mí es falso, pero no sé bien como demostrarlo, para el c) es verdadero porque si dos gráficas son isomorfas tienen las mismas propiedades,caractéristicas, si una tiene un cliclo, la otra tiene el mismo cliclo y para el d) es falsa pero como la demuestro?

Muchas gracias.
En línea
cristianll
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 236


Ver Perfil
« Respuesta #8 : 23/06/2008, 11:10:13 pm »

Este ejemplo


Es un árbol con raíz en forma vertical?

Muchas gracias.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 29.515


Ver Perfil
« Respuesta #9 : 24/06/2008, 06:15:53 am »

Hola

 En general hay algo que me desconcierta en tus preguntas, porque versan sobre conceptos que parece no te han definido previamente. Entonces es imposible contestar.

 En concreto no estoy seguro de cual es la definición que se maneja de árbol jerarquizado.

 En cuanto a tu ejemplo, efectivamente y son árboles isomorfos; se prueba de manera rigurosa viendo que efectivamente tu función lleva raíz en raíz, vértices en vértices y de manera que los vértices imagen son adyacentes si y sólo si lo son los iniciales.

 Para comprobar de manera rigurosa que dos árboles isomorfos son gráficas isomorfas simplemente compara la definición de una y otra cosa: es decir comprueba que si un árbolo cumple la definición de isomorfo entonces también cumple la definición de gráfica isomorfa.

 7) (a) tu ejemplo no vale porque con una función que reordene los vértices tendrías el mismo grafo. Pero compara tu con el grafo de igual vértices y aristas : DIBUJALOS!!!!

 (b) Si crees que es falso busca un contraejemplo.

Spoiler (click para mostrar u ocultar)

 (d) ¿Por qué dices que es falso? Recuerda que dos grafos isomorfos tienen exactamente las mismas propiedades.

Saludos.

* grafonoiso.JPG (6.74 KB - descargado 2372 veces.)
En línea
cristianll
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 236


Ver Perfil
« Respuesta #10 : 24/06/2008, 10:59:01 am »

Hola, muchas gracias, pero en el ejemplo que me das que compare para el 7a) que es [/tex] con hay vértices que no tienen el mismo grado, por ejemplo en el hay vértice con grado 3, y en el el grado máximo es de los vértices es 2, y me pide que los grados en las dos gráficas sean iguales.Entonces no sirve ese ejemplo?

Muchas gracias.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 29.515


Ver Perfil
« Respuesta #11 : 24/06/2008, 01:20:39 pm »

Hola

 Ah, perdona estaba entendiendo que lo que era igual era el grado del grafo, es decir, la suma de los grados de todos los vértices.

 En cualquier caso tampoco es cierto:



Saludos.

* contraejemgraf.JPG (4.1 KB - descargado 2212 veces.)
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!