[manooooh]

Hola!

Dados los siguientes grafos indique la opción correcta y justifique:

• Existe un sólo isomorfismo entre ellos
• Existe más de un isomorfismo entre ellos
• Ambos poseen caminos de Euler
• El primer grafo tiene \( 4 \) puntos de corte

Me gustaría que por favor me corrijan en cada afirmación que hago:

El primer grafo, que es conexo y no dirigido, no puede tener \( 4 \) puntos de corte pues no tiene extremos; en consecuencia todos son puntos de corte.

Ambos no poseen caminos de Euler pues, si bien son conexos, para todo vértice sus grados de valencia son no pares (hay más de dos con grado impar).

Ahora viene mi duda...

Sabemos que un grafo \( n \)-regular es isomorfo a otro si y sólo si sus matrices de adyacencia coinciden. Ambos grafos son \( 3 \)-regulares. Ahora bien, ¿existen infinitas formas de representarlos?

Yo creo que sí... pero no sabría cómo probarlo y si es: 1) una propiedad, 2) un teorema, 3) un corolario de un teorema, 4) etc. ¿O ya está probado?

¿Cómo lo justificarían ustedes?

Gracias!
Saludos

[martiniano]

Hola.

El primer grafo, que es conexo y no dirigido, no puede tener \( 4 \) puntos de corte pues no tiene extremos; en consecuencia todos son puntos de corte.

Un grafo puede tener puntos de corte aunque no tenga vértices de grado 1 (no sé si con extremos te refieres a eso). Pero diría que un grafo regular conexo y no dirigido no puede tener puntos de corte.

Ambos no poseen caminos de Euler pues, si bien son conexos, para todo vértice sus grados de valencia son no pares (hay más de dos con grado impar).

Estoy de acuerdo.

Sabemos que un grafo \( n \)-regular es isomorfo a otro si y sólo si sus matrices de adyacencia coinciden.

En esto creo que te has equivocado. Mira aquí cuando habla de la matriz de adyacencia:

https://es.wikipedia.org/wiki/Isomorfismo_de_grafos

Ambos grafos son \( 3 \)-regulares. Ahora bien, ¿existen infinitas formas de representarlos?

Yo diría que existen exactamente \( 3!8=48 \) isomorfismos diferentes. Observa que puedes asociar el vértice \( a  \) del grafo de la izquierda a cualquiera de los ocho de la derecha. Una vez hecho esto tendrás tres vértices en el grafo de la derecha para los vértices \( b,\,g \) y \( c \), que podrás permutar como quieras, en total de \( 3! \) maneras distintas. Una vez hecho esto, los restantes vértices quedarán ya asignados de una sola manera.

Saludos.

[manooooh]

Hola!

Un grafo puede tener puntos de corte aunque no tenga vértices de grado 1 (no sé si con extremos te refieres a eso).

Sí, me refería a eso.

Pero diría que un grafo regular conexo y no dirigido no puede tener puntos de corte.

La verdad es que tuve que buscar la definición de punto de corte (o vértice de corte) en la Wikipedia porque no sabía qué era. Allí dice:

En general, un grafo conexo, no dirigido y con \( n \) vértices, puede tener no más que \( n-2 \) vértices de corte.

En nuestro caso, el primer grafo de \( 8 \) vértices tiene más que \( 8-2=6 \) vértices de corte (es claro que todos los vértices son puntos de corte). Por tanto no tiene \( 4 \), así que la afirmación es falsa. ¿Qué estoy malinterpretando? Si es así, ¿podrías explicarme un poco más tu definición, por favor?

En esto creo que te has equivocado. Mira aquí cuando habla de la matriz de adyacencia:

https://es.wikipedia.org/wiki/Isomorfismo_de_grafos

Ok, ¿es decir que existe un sólo isomorfismo entre ellos?

Yo tenía anotado en mi cuaderno que dos grafos simples (me olvidé de esto) son isomorfos cuando sus matrices de adyacencia coinciden . Ahora me fijo y cumplen que los dos son grafos simples, pues la definición de grafo simple es que no deben tener lazos ni aristas paralelas (también extraído de mi cuaderno). Haciendo las matrices de adyacencia estaríamos definiendo una cierta correspondencia entre los grafos, ya que debemos observar que haya la misma cantidad de ceros y unos entre ambos, además que estén dispuestos de la misma manera.

Quizás se pueda justificar también que una biyección entre dos conjuntos es única, por tanto el isomorfismo también lo es . ¿Te parecería?

Yo diría que existen exactamente \( 3!8=48 \) isomorfismos diferentes. Observa que puedes asociar el vértice \( a  \) del grafo de la izquierda a cualquiera de los ocho de la derecha. Una vez hecho esto tendrás tres vértices en el grafo de la derecha para los vértices \( b,\,g \) y \( c \), que podrás permutar como quieras, en total de \( 3! \) maneras distintas. Una vez hecho esto, los restantes vértices quedarán ya asignados de una sola manera.

Entiendo.

Gracias!
Saludos

[martiniano]

Hola,

En nuestro caso, el primer grafo de \( 8 \) vértices tiene más que \( 8-2=6 \) vértices de corte (es claro que todos los vértices son puntos de corte). Por tanto no tiene \( 4 \), así que la afirmación es falsa. ¿Qué estoy malinterpretando? Si es así, ¿podrías explicarme un poco más tu definición, por favor?

La definición que sigo yo es la misma que en wikipedia. Un punto de corte es aquel que cuando lo eliminamos junto a todas las aristas que en él inciden, el grafo pasa a tener más componentes conexas que las que tenía. Si no estoy equivocado este grafo no tiene ninguno.

Yo tenía anotado en mi cuaderno que dos grafos simples (me olvidé de esto) son isomorfos cuando sus matrices de adyacencia coinciden . Ahora me fijo y cumplen que los dos son grafos simples, pues la definición de grafo simple es que no deben tener lazos ni aristas paralelas (también extraído de mi cuaderno). Haciendo las matrices de adyacencia estaríamos definiendo una cierta correspondencia entre los grafos, ya que debemos observar que haya la misma cantidad de ceros y unos entre ambos, además que estén dispuestos de la misma manera.

Yo lo que pienso es que dos grafos con la misma matriz de adyacencia son isomorfos, pero el recíproco no es cierto, es decir, puede haber grafos isomorfos con matrices de adyacencia diferentes (mira el enlace que te he recomendado antes).

Quizás se pueda justificar también que una biyección entre dos conjuntos es única, por tanto el isomorfismo también lo es . ¿Te parecería?

No sé... Entre dos conjuntos puede haber más de una biyección, ¿no?

Saludos.

[manooooh]

Hola

La definición que sigo yo es la misma que en wikipedia. Un punto de corte es aquel que cuando lo eliminamos junto a todas las aristas que en él inciden, el grafo pasa a tener más componentes conexas que las que tenía. Si no estoy equivocado este grafo no tiene ninguno.

Pues ahora te comprendo... algo tan visual y yo queriéndole encontrar el pelo al huevo con definiciones formales .

Yo lo que pienso es que dos grafos con la misma matriz de adyacencia son isomorfos, pero el recíproco no es cierto, es decir, puede haber grafos isomorfos con matrices de adyacencia diferentes (mira el enlace que te he recomendado antes).

Creo que entiendo. Entonces decís que hay \( 3!\cdot8=48 \) isomorfismos diferentes entre ambos grafos, pero no es ninguna de las opciones que aparecen (se tiene que marcar una única opción correcta). ¿Qué no estoy viendo?

Saludos

[martiniano]

Hola.

Opción b): Existe más de un isomorfismo entre ellos.

Lo de decir cuántos es un extra. También porque por allá arriba me pareció que preguntaste si había infinitos.

Saludos.

[manooooh]

Opción b): Existe más de un isomorfismo entre ellos.

Lo de decir cuántos es un extra. También porque por allá arriba me pareció que preguntaste si había infinitos.

Sí, pensé que mi duda de decir "¿existen infinitos?" era una de las opciones. Gracias.

Saludos