Buenas! Quisiera saber si, por ejemplo en este ejercicio, vamos a tomar los ciclos efg, fge, gef como 3 ciclos, o cuentan como uno, ya que en el libro lo cuenta como 3 ciclos, y en el openfing deciden corregirlo y tomarlos como uno.
Hola Ignacio. Estamos siguiendo las definiciones del libro de Grimaldi. Los ciclos efg, fge y gef son tres ciclos distintos (tienen la misma imagen, incluso la misma dirección pero el punto inicial cambia). En los ciclos importa la dirección y el punto de inicio. Igual ambos problemas son equivalentes, si contás los ciclos de longitud n (n>2) sin importar la dirección ni punto de inicio, entonces luego vas a tener que multiplicar esa cantidad por 2n. En el video de la clase 17 (desde el minuto 26:48 a 30:48) cuento todos los ciclos que pasan por g en el grafo de la Figura 1 (iii) y la idea es esa, cuento todas las copias de Cn dentro del grafo que pasan por g (es decir, los ciclos de largo n sin importar dirección ni punto inicial) y luego multiplico todo por 2n, eso para cada n posible, luego se suman.
En otros años por alguna razón decidieron modificar algunas definiciones del libro de Grimaldi, en el libro de Grimaldi hay algunos errores pero son simples de corregir por contexto. Mañana subiré un pdf con un resumen de las definiciones para evitar toda confusión.
Entonces si lo que importa es el punto de inicio y la dirección, si tomamos los ciclos de longitud 3, entre tres puntos adyacentes entre si, ¿hay 6 ciclos diferentes? ¿las dos direcciones posibles de cada uno de los 3 puntos?
Si, exacto. Entre tres vértices adyacentes se pueden definir 6 ciclos diferentes de longitud 3.
Hay otro tipo de problema en que dado un grafo G se pide hallar todos los subgrafos isomorfos a C3 (otra forma de preguntar lo mismo es pedir que cuenten cuantas copias de C3 hay en G). En ese caso habría que contar todos los ciclos de longitud 3 que tiene el grafo sin importar el punto inicial ni el sentido (aqui dados tres vértices adyacentes, el subgrafo inducido por esos vértices sería un subgrafo isomorfo a C3). Para pasar de un problema al otro simplemente hay que multiplicar el resultado por 6.