10 Abril, 2020, 16:23 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Grafos Isomorfos  (Leído 2719 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Carolina Herschel
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Femenino
Venezuela Venezuela

Mensajes: 383



Ver Perfil
« : 12 Julio, 2010, 20:40 »

Hola qué tal.

Tengo la definición siguiente:

Dos grafos G1 y G2 son isomorfos cuando existe una biyección f entre los conjuntos de sus vértices y f conserva la adyacencia . Es decir, G1 es isomorfo a G2 si y sólo si existe [texx]f:V_1\rightarrow{V_2}[/texx] tal que:

  • f es biyectiva
  • [texx]\forall{u,v\in{V_1}}, uv\in{A_1}\Leftrightarrow{f(u)f(v)\in{A_2}}[/texx]

No entiendo muy bien esta definición, especialmente cómo aplicarla, porque según veo la cantidad de vértices y de aristas en ambos grafos deben ser iguales, además que si debe conservar la adyacencia entonces ún grafo isomorfo a uno dado sería una especie de "reordenación"  Me refiero a tomar el mismo conjunto de aristas y de vértices pero cambiar los vértices de posición. No se si estaré completamente equivocada..

Por ejemplo tengo estos dos problemas:

1) ¿Se puede hallar un grafo isomorfo al de la figura? ¿Por qué? Si su respuesta es afirmativa, encuentre uno.



2) Probar que G1 y G2, G2 y G3 no son isomorfos.



Muchas gracias  :sonrisa:

* grafoz2.jpg (3.77 KB - descargado 645 veces.)
* grafoz.jpg (7.31 KB - descargado 701 veces.)
En línea

"Math is like love -- a simple idea but it can get complicated."
deped32
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 17


Ver Perfil
« Respuesta #1 : 14 Julio, 2010, 02:14 »

A veces las definiciones por mantener la formalidad confunden mas.

"Informalmente, un grafo G1 es isomorfo a un grafo G2 si son el mismo grafo pero estan dibujados de distinta manera."

Seria como agarrar un grafo, con sus conexiones hechas, y redistribuir los vertices y las aristas en el plano, pero sin sacar, ni agregar, ni intercambiar aristas y sin sacar, ni agregar, ni intercambiar vertices (respetar que estaba conectado a que)

Ejemplo:
Si en tu grafo G1 tenes un vertice (a) que esta conectado SOLAMENTE: por medio de 1 arista al vertice (b), por medio de 2 aristas al vertice (c) y por medio de 2 aristas a si mismo;
en el grafo G2 deberías reconocer un vertice (a') que este conectado TAMBIEN SOLAMENTE: por medio de 1 arista al vertice (b') y por medio de 2 aristas al vertice (c'), y por medio de 2 aristas a si mismo. (y nada más)
Este proceso de biyección lo deberías poder hacer para todos lo vertices del grafo. Ya con que para uno falle, dejan de ser isomorfos.


De la definicion se deducen condiciones necesarias (pero no suficientes) de isomorfismo:
a) G1 y G2 tienen la misma cantidad de nodos
b) G1 y G2 tienen la misma cantidad de aristas

Por ultimo, basta decir que un grafo G1 es isomorfo a si mismo.

Espero que no te confunda más todavía, pero es más sencillo de lo que parece.

¿Estás estudiando matemática discreta o algo así? Porque ayer discutimos algo sobre complejidad de algoritmos
En línea
Carolina Herschel
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Femenino
Venezuela Venezuela

Mensajes: 383



Ver Perfil
« Respuesta #2 : 14 Julio, 2010, 19:48 »

Hola!

Sí, yo estudio Matemática y estoy en un curso de Matemáticas Discretas  :cara_de_queso:

Muchas gracias por tu explicación, lo entendí perfectamente  :sonrisa_amplia:

Gracias!!

Saludos.
En línea

"Math is like love -- a simple idea but it can get complicated."
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #3 : 15 Julio, 2010, 04:31 »

Hola
 
 Carolina como se indica en las reglas no debes de poner imágenes alojadas en servidores ajenos al foro.

 El procedimiento correcto para incluir una imagen está explicado aquí:

http://www.rinconmatematico.com.ar/foros/index.php?topic=3659.msg14457#msg14457

 De todas formas en este caso te lo he corregido yo.

Saludos.
En línea
Carolina Herschel
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Femenino
Venezuela Venezuela

Mensajes: 383



Ver Perfil
« Respuesta #4 : 15 Julio, 2010, 20:07 »

Ah ok el_manco, discúlpame  :avergonzado: No se repetirá otra vez.

Saludos!
En línea

"Math is like love -- a simple idea but it can get complicated."
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

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