[Nub]

Hola, tengo unas preguntas sobre el isomorfismo de grafos

1) Según la definición, hay que encontrar una función inyectiva y sobreyectiva con el conjunto de vertices de ambos grafos, supongamos que encuentro la funcion que es inyectiva y sobreyectiva, pero no cumple con la condición de las aristas. Por ejemplo

Entonces definimos la función G asi:
\( g(m)=r, g(n)=s, g(p)=t, g(q)=u \)
sabemos que la función es sobreyectiva y inyectiva por lo tanto cumple esta parte de la definición pero la otra parte de la arista no la cumple ya que, la arista \( \left\{{m,q}\right\} \) del grafo C su correspondiente en el grafo D \( \left\{{r,u}\right\} \) no existe en el grafo D. Entonces no se podría decir que la función cumple un isomorfismo, pero, si hacemos otra función por ejemplo la función h tal que
\( h(m)=s,h(n)=r,h(p)=u,h(q)=t \) y en este caso funciona.

Ahora la pregunta, en la practica, ¿tengo que probar todas las posibles funciones y que justo cumpla la condición de la arista?

2) Según el libro que estaba leyendo había una especie de técnica para encontrar mas facil el grafo isomorfo, era encontrar un ciclo en el primer grafo A y que el mismo ciclo se mantenga en el grafo B.

La pregunta es, ¿El ciclo en el grafo B debe estar formado con los vértices correspondientes   del grafo A? ¿O simplemente funciona si el ciclo es de longitud igual que el del en grafo A? ¿Esto se aplica también para circuitos, caminos simples,recorridos,etc?

Muchas gracias.

[manooooh]

Hola

Ahora la pregunta, en la practica, ¿tengo que probar todas las posibles funciones y que justo cumpla la condición de la arista?

Una condición suficiente para que dos grafos sean isomorfos es que exista un ordenamiento de los vértices tal que las matrices de adyacencia sean iguales.

La pregunta es, ¿El ciclo en el grafo B debe estar formado con los vértices correspondientes   del grafo A? ¿O simplemente funciona si el ciclo es de longitud igual que el del en grafo A? ¿Esto se aplica también para circuitos, caminos simples,recorridos,etc?

Si los grafos son isomorfos, deben compartir las mismas propiedades estructurales. Como consecuencia de eso, deben tener la misma cantidad de ciclos, pero por supuesto las "etiquetas" de los vértices que los componen pueden ser distintas, como exhibes en tu ejemplo. Pero siempre tomando todos los vértices y aristas de un grafo o de otro, no se pueden "cruzar" aristas y vértices entre grafos, si eso era lo que preguntabas.

Saludos

P.D. Creo que aquí:

La condición (b) solo es cierta si no hay aristas paralelas. Si las hubiera, creo que ya no sería cierto.

[Nub]

Una condición suficiente para que dos grafos sean isomorfos es que exista un ordenamiento de los vértices tal que las matrices de adyacencia sean iguales.

No era esa mi pregunta, pero puede ser una manera rápida de verificar si son isomorfos ¡Gracias!

Si los grafos son isomorfos, deben compartir las mismas propiedades estructurales. Como consecuencia de eso, deben tener la misma cantidad de ciclos, pero por supuesto las "etiquetas" de los vértices que los componen pueden ser distintas, como exhibes en tu ejemplo. Pero siempre tomando todos los vértices y aristas de un grafo o de otro, no se pueden "cruzar" aristas y vértices entre grafos, si eso era lo que preguntabas.

No exactamente era lo que preguntaba y el ejemplo que di era solo para la pregunta 1, Supongamos que tengo un ciclo en un grafo A cualquiera, supongamos que el ciclo sea a-b-c-d-a entonces yo tengo que buscar un ciclo en el grafo B que sea e-f-g-h-e siendo f(a)=e,f(b)=f,f(c)=g,f(d)=h ? o basta con encontrar un ciclo de largo 4 cualquiera aunque los vértices no sean los correspondientes

[manooooh]

Hola

No exactamente era lo que preguntaba y el ejemplo que di era solo para la pregunta 1, Supongamos que tengo un ciclo en un grafo A cualquiera, supongamos que el ciclo sea a-b-c-d-a entonces yo tengo que buscar un ciclo en el grafo B que sea e-f-g-h-e siendo f(a)=e,f(b)=f,f(c)=g,f(d)=h ? o basta con encontrar un ciclo de largo 4 cualquiera aunque los vértices no sean los correspondientes

Antes que nada recordemos que tener la misma cantidad de ciclos es una condición necesaria, no suficiente. Entonces por más que se cumpla lo que dices (encontrar un ciclo de longitud \( n \) cualquiera), no garantiza el isomorfismo entre grafos.

De todas maneras, para ir "tanteando", supongo que es suficiente con que el extremo inicial del primer grafo sea el mismo que el segundo (y el extremo final también). Al final un "ciclo" es un camino cerrado, da igual el "recorrido" siempre que se llegue y parta del mismo sitio (que sean correspondientes).

Saludos

[Nub]

Hola

No exactamente era lo que preguntaba y el ejemplo que di era solo para la pregunta 1, Supongamos que tengo un ciclo en un grafo A cualquiera, supongamos que el ciclo sea a-b-c-d-a entonces yo tengo que buscar un ciclo en el grafo B que sea e-f-g-h-e siendo f(a)=e,f(b)=f,f(c)=g,f(d)=h ? o basta con encontrar un ciclo de largo 4 cualquiera aunque los vértices no sean los correspondientes

Antes que nada recordemos que tener la misma cantidad de ciclos es una condición necesaria, no suficiente. Entonces por más que se cumpla lo que dices (encontrar un ciclo de longitud \( n \) cualquiera), no garantiza el isomorfismo entre grafos.

De todas maneras, para ir "tanteando", supongo que es suficiente con que el extremo inicial del primer grafo sea el mismo que el segundo (y el extremo final también). Al final un "ciclo" es un camino cerrado, da igual el "recorrido" siempre que se llegue y parta del mismo sitio (que sean correspondientes).

Saludos

Entiendo, era eso básicamente que dices al final, que sean correspondientes era mi duda.

Una condición suficiente para que dos grafos sean isomorfos es que exista un ordenamiento de los vértices tal que las matrices de adyacencia sean iguales.

Ahora que estaba viendo esto, a un ordenamiento de vértices te podrías referir a que básicamente es hacer las matrices de adyacencia de cada grafo y ordenar los vertices de forma que las matrices queden iguales? porque he echo las matrices de estos dos grafos

y quedan diferentes, osea cada entrada no es igual pero si se ordena podría serlo
G1:
\begin{pmatrix}{0}&{1}&{0}&{0}&{1}\\{1}&{0}&{1}&{0}&{0}\\{0}&{1}&{0}&{1}&{0}\\{0}&{0}&{1}&{0}&{1}\\{1}&{0}&{0}&{1}&{0}\end{pmatrix}
G2:
\begin{pmatrix}{0}&{0}&{1}&{1}&{0}\\{0}&{0}&{0}&{1}&{1}\\{1}&{0}&{0}&{0}&{1}\\{1}&{1}&{0}&{0}&{0}\\{0}&{1}&{1}&{0}&{0}\end{pmatrix}

[manooooh]

Hola

Ahora que estaba viendo esto, a un ordenamiento de vértices te podrías referir a que básicamente es hacer las matrices de adyacencia de cada grafo y ordenar los vertices de forma que las matrices queden iguales? porque he echo las matrices de estos dos grafos

y quedan diferentes, osea cada entrada no es igual pero si se ordena podría serlo
G1:
\begin{pmatrix}{0}&{1}&{0}&{0}&{1}\\{1}&{0}&{1}&{0}&{0}\\{0}&{1}&{0}&{1}&{0}\\{0}&{0}&{1}&{0}&{1}\\{1}&{0}&{0}&{1}&{0}\end{pmatrix}
G2:
\begin{pmatrix}{0}&{0}&{1}&{1}&{0}\\{0}&{0}&{0}&{1}&{1}\\{1}&{0}&{0}&{0}&{1}\\{1}&{1}&{0}&{0}&{0}\\{0}&{1}&{1}&{0}&{0}\end{pmatrix}

Claro. Si son iguales, seguro son isomorfos. Ahora si no lo son, pueden o no ser isomorfos. La contra de esto es que hay que ir probando configuración por configuración hasta dar con el ordenamiento, pero si no es tan fácil encontrarlo, se tarda mucho.

En ese ejemplo creo que con la función \( f\colon f(0)=a,\;f(1)=c,\;f(2)=e,\;f(3)=b,\;f(4)=d \) hace que las matrices de adyacencia resulten iguales, y por lo tanto \( G_1 \) y \( G_2 \) son isomorfos.

Saludos

[Nub]

Hola

Ahora que estaba viendo esto, a un ordenamiento de vértices te podrías referir a que básicamente es hacer las matrices de adyacencia de cada grafo y ordenar los vertices de forma que las matrices queden iguales? porque he echo las matrices de estos dos grafos

y quedan diferentes, osea cada entrada no es igual pero si se ordena podría serlo
G1:
\begin{pmatrix}{0}&{1}&{0}&{0}&{1}\\{1}&{0}&{1}&{0}&{0}\\{0}&{1}&{0}&{1}&{0}\\{0}&{0}&{1}&{0}&{1}\\{1}&{0}&{0}&{1}&{0}\end{pmatrix}
G2:
\begin{pmatrix}{0}&{0}&{1}&{1}&{0}\\{0}&{0}&{0}&{1}&{1}\\{1}&{0}&{0}&{0}&{1}\\{1}&{1}&{0}&{0}&{0}\\{0}&{1}&{1}&{0}&{0}\end{pmatrix}

Claro. Si son iguales, seguro son isomorfos. Ahora si no lo son, pueden o no ser isomorfos. La contra de esto es que hay que ir probando configuración por configuración hasta dar con el ordenamiento, pero si no es tan fácil encontrarlo, se tarda mucho.

En ese ejemplo creo que con la función \( f\colon f(0)=a,\;f(1)=c,\;f(2)=e,\;f(3)=b,\;f(4)=d \) hace que las matrices de adyacencia resulten iguales, y por lo tanto \( G_1 \) y \( G_2 \) son isomorfos.

Saludos

Bueno, pero aca no seguimos en lo mismo  ? es decir, no me da ninguna información las matrices para encontrar la funcion que si sirva, osea en este caso fue medio innecesario hacer las matrices. Y a que te refieres configuracion por configuracion?

[Luis Fuentes]

Hola

Bueno, pero aca no seguimos en lo mismo  ? es decir, no me da ninguna información las matrices para encontrar la funcion que si sirva, osea en este caso fue medio innecesario hacer las matrices. Y a que te refieres configuracion por configuracion?

Es que el problema de determinar si dos grafos son isomorfos y encontrar el isomorfismo no es sencillo. Puedes leer por aquí al respecto:

https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

P.D. Creo que aquí:

La condición (b) solo es cierta si no hay aristas paralelas. Si las hubiera, creo que ya no sería cierto.

No entendí esto; yo creo que la definición está bien. ¿Qué problema ves?.

Saludos.

[Nub]

Hola

Bueno, pero aca no seguimos en lo mismo  ? es decir, no me da ninguna información las matrices para encontrar la funcion que si sirva, osea en este caso fue medio innecesario hacer las matrices. Y a que te refieres configuracion por configuracion?

Es que el problema de determinar si dos grafos son isomorfos y encontrar el isomorfismo no es sencillo. Puedes leer por aquí al respecto:

https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

P.D. Creo que aquí:

La condición (b) solo es cierta si no hay aristas paralelas. Si las hubiera, creo que ya no sería cierto.

No entendí esto; yo creo que la definición está bien. ¿Qué problema ves?.

Saludos.

Ahhh ahora entiendo, pensé que era un método infalible el de las matrices Y con la definición, era solo para ilustrar la idea de "la segunda parte de la def" que era básicamente lo de las aristas, pero nada, ¡Muchas gracias a todos!