[sxemi]

"Sea \( x \) el conjunto de los grafos (no dirigidos) \( G = (V,E) \) conexos y no isomorfos entre ellos tales que \( |V|+|E| \leq{9} \). Señale la opción correcta:
A) \( |x| \leq{10} \).
B) Todos los vértices de todos los grafos de \( x \) tienen grado menor o igual a 3.
C) No existe \( G \in x \) con más de un ciclo.
D) En \( x \) hay al menos 7 árboles.
E) \( C_i \in x, i \in \left\{{3,4,5}\right\}  \)."

No sé ni por dónde empezar este ejercicio, si alguien me puede dar una mano se agradece!
(Por las dudas, \( |V|\ y\ |E| \) son los cardinales de los vértices y aristas respectivamente).

[manooooh]

Hola

"Sea \( x \) el conjunto de los grafos (no dirigidos) \( G = (V,E) \) conexos y no isomorfos entre ellos tales que \( |V|+|E| \leq{9} \). Señale la opción correcta:
A) \( |x| \leq{10} \).
B) Todos los vértices de todos los grafos de \( x \) tienen grado menor o igual a 3.
C) No existe \( G \in x \) con más de un ciclo.
D) En \( x \) hay al menos 7 árboles.
E) \( C_i \in x, i \in \left\{{3,4,5}\right\}  \)."

No sé ni por dónde empezar este ejercicio, si alguien me puede dar una mano se agradece!
(Por las dudas, \( |V|\ y\ |E| \) son los cardinales de los vértices y aristas respectivamente).

No me queda claro cuáles son los grafos \( C_i \).

Cada elemento de \( x \) es un grafo conexo cuya suma de vértices y aristas es menor o igual a \( 9 \). Por lo tanto, algunos grafos no isomorfos entre sí de \( x \) son:

¿Puedes ir descartando opciones? ¿Alguna duda?

Saludos

AGREGADO Considera estos grafos de \( x \) y saca conclusiones:

[sxemi]

\( C_i \) son aquellos grafos cíclicos. Por ejemplo \( C_5 \) sería:



Guiándome con lo que me escribiste puedo descartar la opción A, pues me diste más de 10 ejemplos que cumplen con las condiciones de la letra, lo mismo con la opción B, existe un grafo que posee un grado igual a 4.
La opción E puedo descartarla también ya que la suma de \( |V| \) y \( |E| \) de \( C_5 \) es igual a 10.
Las opciones C y D fueron las que más me costaron, pero creo que puedo descartar la opción C, ya que tomando de ejemplo el grafo G6 y teniendo en cuenta la definición de ciclo (camino cerrado que no repite vértices salvo el primero y último):



El camino cerrado \( \left\{{B,A,B}\right\} \) es un ciclo, y por otro lado \( \left\{{B,C,B}\right\} \) también lo es, y ahí hay más de un ciclo.

Por lo que la respuesta final sería la opción D. Corregime si me equivoqué en algo.

La única duda que me surgió es: ¿hay alguna forma para darme cuenta rápidamente que 2 grafos son no isomorfos sin tener que guiarme por la definición? Porque la definición me marea un poco.

[manooooh]

Hola

Guiándome con lo que me escribiste puedo descartar la opción A, pues me diste más de 10 ejemplos que cumplen con las condiciones de la letra, lo mismo con la opción B, existe un grafo que posee un grado igual a 4.
La opción E puedo descartarla también ya que la suma de \( |V| \) y \( |E| \) de \( C_5 \) es igual a 10.

Bien.

Las opciones C y D fueron las que más me costaron, pero creo que puedo descartar la opción C, ya que tomando de ejemplo el grafo G6 y teniendo en cuenta la definición de ciclo (camino cerrado que no repite vértices salvo el primero y último):



El camino cerrado \( \left\{{B,A,B}\right\} \) es un ciclo, y por otro lado \( \left\{{B,C,B}\right\} \) también lo es, y ahí hay más de un ciclo.

Por lo que la respuesta final sería la opción D. Corregime si me equivoqué en algo.

Yo también tengo la misma duda de los ciclos.

Originalmente había pensado en el grafo \( G_8 \) que es un \( C_3 \) con un bucle en uno de los vértices. Ahí es más obvio que tiene 2 ciclos: Uno que recorre todas las aristas del \( C_3 \) sin el bucle, y el otro lo mismo pero pasando por el bucle.

La única duda que me surgió es: ¿hay alguna forma para darme cuenta rápidamente que 2 grafos son no isomorfos sin tener que guiarme por la definición? Porque la definición me marea un poco.

Si son NO isomorfos, pues lo primero que haría sería fijarme que no tengan la misma cantidad de vértices. Si tienen, paso a contar las aristas. Si son iguales, reviso si hay existencia de bucles. Si tienen, reviso los grados de cada vértice. Y así. Pero no es un método infalible, puede ser muy difícil encontrar cuándo dos grafos son isomorfos, como menciona Luis aquí:

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

Saludos

[geómetracat]

Un par de cosas. Primero, cuando se habla de grafos no dirigidos normalmente se entiende que no tienen bucles (aristas que unan un vértice consigo mismo). De todas maneras esto es algo que hay que comprobar en el libro o la asignatura que se esté siguiendo o de dónde se haya sacado el ejercicio.

Segundo:

El camino cerrado \( \left\{{B,A,B}\right\} \) es un ciclo, y por otro lado \( \left\{{B,C,B}\right\} \) también lo es, y ahí hay más de un ciclo.

Eso no son ciclos. En un ciclo se exige que las aristas del camino sean todas distintas, de manera que no se puede ir por un arista y volver por la misma. Sí no fuera así, todos los grafos con al menos una arista tendrían ciclos y el concepto de ciclo no sería demasiado útil.

[manooooh]

Hola

Primero, cuando se habla de grafos no dirigidos normalmente se entiende que no tienen bucles (aristas que unan un vértice consigo mismo). De todas maneras esto es algo que hay que comprobar en el libro o la asignatura que se esté siguiendo o de dónde se haya sacado el ejercicio.

Tiene lógica por la forma en que dice el enunciado \( G=(V,E) \), pero para mí la palabra "dirigido" hace referencia al dígrafo: las aristas tienen un sentido de orientación.

Si fuera sin bucles o lazos, ¿la respuesta correcta seguiría siendo la misma?

Veremos qué dice sxemi.

Eso no son ciclos. En un ciclo se exige que las aristas del camino sean todas distintas, de manera que no se puede ir por un arista y volver por la misma. Sí no fuera así, todos los grafos con al menos una arista tendrían ciclos y el concepto de ciclo no sería demasiado útil.

Muchas gracias!

Saludos

AGREGADO

[geómetracat]

Tiene lógica por la forma en que dice el enunciado \( G=(V,E) \), pero para mí la palabra "dirigido" hace referencia al dígrafo: las aristas tienen un sentido de orientación.

Veremos qué dice sxemi.

Sí, lo de "no dirigido" hace referencia a que las aristas no están orientadas, eso está claro.
Lo que yo digo es que si se habla de "grafo" o de "grafo no dirigido" a secas, sin especificar más, normalmente se entiende que es sin bucles. O al menos esa es la convención que estoy acostumbrado a ver en contextos matemáticos.

Pero vaya, a ver qué dice sxemi que es quien sabe las definiciones que están usando.

[Richard R Richard]

C) No existe \( G \in x \) con más de un ciclo.

Este 




tiene más de un ciclo y \( 9 =|V|+|E| \)


porque no sería ejemplo , es isormorfo?


Saludos

[manooooh]

Hola

Este 




tiene más de un ciclo y \( 9 =|V|+|E| \)


porque no sería ejemplo , es isormorfo?

Está bien ese contraejemplo. ¿Por qué dices que no sería ejemplo?

Saludos

[Richard R Richard]

Hola
Está bien ese contraejemplo. ¿Por qué dices que no sería ejemplo?
Saludos

Creo que era la forma mas fácil de invalidar c) para que d) sea la correcta. Pero no tengo clara la noción de isomorfismo entonces quizá el ejemplo no era válido.

Gracias

Saludos