Rincón Matemático

Matemática => Matemática Discreta y Algoritmos => Teoría de grafos => Mensaje iniciado por: Julio_fmat en 27 Octubre, 2019, 09:40 pm

Título: Grafos no isomorfos
Publicado por: Julio_fmat en 27 Octubre, 2019, 09:40 pm
Determine cuantos grafos no isomorfos existen que sean \( 4 \)-regulares con \( 7 \) vertices.
Título: Re: Grafos no isomorfos
Publicado por: Luis Fuentes en 28 Octubre, 2019, 07:35 am
Hola

Determine cuantos grafos no isomorfos existen que sean \( 4 \)-regulares con \( 7 \) vertices.

Estás preguntando continuamente por problema sobre grafos, pero ni muestras tus intentos ni apenas das respuesta a las indicaciones que te damos. Sería deseable que mostrases más trabajo de tu parte.

 Nota que dos grafos son isomorfos si y sólo si lo son sus complementarios. El complementario de un grafo 4-regular de 7 vértices es un grafo 2-regular de 7 vértices. Los únicos grafos 2-regulares conexos son los ciclos. Concluye.

Saludos.
Título: Re: Grafos no isomorfos
Publicado por: Julio_fmat en 06 Diciembre, 2019, 08:18 pm
Hola

Determine cuantos grafos no isomorfos existen que sean \( 4 \)-regulares con \( 7 \) vertices.

Estás preguntando continuamente por problema sobre grafos, pero ni muestras tus intentos ni apenas das respuesta a las indicaciones que te damos. Sería deseable que mostrases más trabajo de tu parte.

 Nota que dos grafos son isomorfos si y sólo si lo son sus complementarios. El complementario de un grafo 4-regular de 7 vértices es un grafo 2-regular de 7 vértices. Los únicos grafos 2-regulares conexos son los ciclos. Concluye.

Saludos.

Muchas Gracias, intentare de poner mis intentos de solucion.

No me queda claro este problema, el solucionario dice que hay solo 2 grafos no isomorfos que cumplen la propiedad, es decir, \( C_7 \) y \( C_3+C_4. \) ¿Por que?
Título: Re: Grafos no isomorfos
Publicado por: Bobby Fischer en 06 Diciembre, 2019, 10:01 pm
No me queda claro este problema, el solucionario dice que hay solo 2 grafos no isomorfos que cumplen la propiedad, es decir, \( C_7 \) y \( C_3+C_4. \) ¿Por que?

Hola, puedes suponer que el grafo complementario que indica Luis Fuentes tiene una única componente conexa, o dos. Tres o más componentes conexas no pueden ser, pues cada una de ellas debe tener al menos 3 vértices. No pueden tener 0 vértices, no pueden tener 1 y no pueden tener 2 porque no serían 2-regulares. Haz dibujos y ves si tienen "la misma forma". Descartas los que sí y te quedan los no isomorfos.

\( C_3+C_4 \)

Por otra parte, debería ser \( C_3\cup C_4 \), pues el grafo que se indica es unión de vértices y unión de aristas. La suma de grafos no creo que deba definirse de esa manera, porque luego habría que ver un símbolo nuevo para denotar la verdadera suma de grafos.

Suma de grafos (https://es.wikipedia.org/wiki/Suma_de_grafos)

Saludos.
Título: Re: Grafos no isomorfos
Publicado por: Luis Fuentes en 07 Diciembre, 2019, 07:29 pm
Hola

No me queda claro este problema, el solucionario dice que hay solo 2 grafos no isomorfos que cumplen la propiedad, es decir, \( C_7 \) y \( C_3+C_4. \) ¿Por que?

¿Qué cosa has ententdido y qué no has entendido de lo que te propuse?:

Nota que dos grafos son isomorfos si y sólo si lo son sus complementarios. El complementario de un grafo 4-regular de 7 vértices es un grafo 2-regular de 7 vértices. Los únicos grafos 2-regulares conexos son los ciclos. Concluye.

 No deberías de decir simplemente: "no me queda claro". Deberías de especificar tus dudas de manera mucho mas concreta.

 Esas dos posibilidades que citas ( \( C_7 \) y \( C_3+C_4 \)) no son grafos 4-regulares, sino sus complementarios. Vuelve a leer mi respuesta; vuelve a leer lo que dice Bobby Fischer y si todavía tienes dudas explica cuáles son.

Saludos.
Título: Re: Grafos no isomorfos
Publicado por: Richard R Richard en 07 Diciembre, 2019, 08:07 pm
Cuando  hayan terminado de responder a Julio_fmat pregunto....

grafos
de a poco intento ver como es la teoría de grafos

Estos son los únicos 3 grafos , no isomorfos, de v=4 regulares de n=7 vértices, o me falta alguno?


A que le llaman grafo complementario a un grafo \(  n-1-v \) regular de n vértices?

si no corresponde al tema  muevanlo a un nuevo hilo gracias!

[cerrar]
Título: Re: Grafos no isomorfos
Publicado por: Luis Fuentes en 07 Diciembre, 2019, 08:55 pm
Hola

Cuando  hayan terminado de responder a Julio_fmat pregunto....

de a poco intento ver como es la teoría de grafos

Estos son los únicos 3 grafos , no isomorfos, de v=4 regulares de n=7 vértices, o me falta alguno?

Pues en realidad te sobran dos y te falta 1.  :D

Los tres grafos que has puesto son isomorfos; si te fijas en el siguiente gráfico, he simplemente renombrado sus vértices con números adecuadamente. Verás que en cada grafo los vértices que están unidos por aristas son exactamente los mismos.

Por el contrario te faltaba la posibilidad que he añadido debajo.

(https://foro.rinconmatematico.com/index.php?action=dlattach;topic=111042.0;attach=21514)

Saludos.
Título: Re: Grafos no isomorfos
Publicado por: Richard R Richard en 07 Diciembre, 2019, 10:10 pm
Gracias Luis .....caray !!! que hay que estar entrenado.... sabia que no isomorfo era que no tuviera todas las mismas aristas conectadas a los mismos vértices... nose si se entiende... pero el último ... regular es que sea constante el número de aristas por vértice, y no con que sea simétrico graficamente no? (lo de polígono regular ...mmm nada que ver de ahi venia la confusión) creo que ya lo veo, pero no lo hubiese sacado nunca si no me lo dices.  :aplauso:


Pd donde puedo leer algo para eliminar el panel izquierdo y poder centrar la imagen que bajo del geogebra?

Gracias de nuevo.
Título: Re: Grafos no isomorfos
Publicado por: Luis Fuentes en 07 Diciembre, 2019, 10:54 pm
Hola

Gracias Luis .....caray !!! que hay que estar entrenado....

Bueno el truco para darme cuenta estuvo precisamente en el argumento que le dimos a Julio Fmat. Si en los tres grafos que dibujaste consideras el complemementario, es decir, precisamente el que resulta de unir los vértices que no están unidos por aristas en el original, obtienes un ciclo de orden siente (un anillo). Eso hace evidente que son el mismo grafo, por tener el mismo complementario.

Citar
sabia que no isomorfo era que no tuviera todas las mismas aristas conectadas a los mismos vértices... nose si se entiende...
Si es eso.

Citar
pero el último ... regular es que sea constante el número de aristas por vértice, y no con que sea simétrico graficamente no?

Exacto.

Fíjate que lo único relevante en la representación gráfica es que vértices están unidos por aristas y cuáles no; independientemente de como se ubiquen en el plano.

Citar
Pd donde puedo leer algo para eliminar el panel izquierdo y poder centrar la imagen que bajo del geogebra?

Vaya por delante que lo que yo he puesto es una imagen, no el archivo de GeoGebra.

Ahora bien antes de grabar el archivo en el propio GeoGebra usando los menús del mismo, en vista quita vista algebraica para que no te salgan las fórmulas.

Saludos.

Saludos.