Práctico 9 - Ejercicio 5

Práctico 9 - Ejercicio 5

de Maria Paz Diaz Bergero -
Número de respuestas: 4

Hola, tengo una duda en cuanto a la letra de este ejercicio. Cuando dice 3-ciclos, ¿Se refiere a ciclos de largo 3? En caso de que así sea, podrían darme una mano por donde encarar el ejercicio, porque no me estaría dando cuanta como contarlos. 

Gracias!


En respuesta a Maria Paz Diaz Bergero

Re: Práctico 9 - Ejercicio 5

de Florencia Cubria -
Hola María Paz.

Así es, un 3 ciclo es un ciclo de largo 3.

Si bien no es lo mismo un ciclo de largo 3 (como camino cerrado que no repite vértices excepto el primero y el último) que un subgrafo isomorfo a C_3, por cada subgrafo isomorfo a C_3 tienes 3·2=6 ciclos de largo 3 (¿se entiende porqué?).

Mi recomendación entonces es que cuentes los subgrafos isomorfos a C_3 (que serían las "porciones de torta" y en W_3 también "el borde de la torta") y luego las multipliques por 6.

Dime si se entendió y si se te ocurre cómo generalizarlo a los 4 ciclos, 5 ciclos, etc.

Saludos, Florencia.
En respuesta a Florencia Cubria

Re: Práctico 9 - Ejercicio 5

de Lucas Cocolis Grosso -
Hola profe, llego a entender lo que explicaste cuando el largo del ciclo coincide con el "n" de W_n. Pero no logro para verlo en los demás casos. Ej: 3-ciclos en W_4
En respuesta a Lucas Cocolis Grosso

Re: Práctico 9 - Ejercicio 5

de Florencia Cubria -
Hola Lucas.

Si quieres contar los 3-ciclos en W_4, nuevamente cuentas los subgrafos isomorfos a C_3 y luego las multiplicas por 6. Observa que en W_n (si n es mayor o igual a 4) los subgrafos isomorfos a C_3 serán únicamente las "porciones de torta".

Si quieres contar los 4-ciclos, tendrás que contar los subgrafos isomorfos a C_4 y luego multiplicarlos por por 2·4 (¿se entiende porqué?).

¿Se te ocurre como contar los grafos subgrafos isomorfos a C_4 en W_3, W_4 y W_5? Informalmente serían "dos porciones de tortas contiguas" y en W_4 además tendrías "el borde de la torta".

Dime si se entendió, saludos, Florencia.