Ejercicio 5; práctico 9

Ejercicio 5; práctico 9

de Romina Belen Garcia Camargo -
Número de respuestas: 2

Hola

En este ejercicio se pide la cantidad de caminos de largo n que hay entre dos vértices opuestos del grafo-ciclo C4. Yo llegué a la conclusión de que si n era un número impar, entonces esta cantidad era cero. Sin embargo, al momento de contar los caminos pares, llegué a una conclusión que no sé si es del todo correcta. 

Por ejemplo, si yo tengo n=2, entonces los caminos posibles para ir de a hasta c son a-b-c, a-d-c, siento en total 2. Pero al tener n=4, el número de caminos crece porque empezamos a repetir aristas. Me quedaron: a-b-a-d-c, a-d-a-b-c, a-d-a-d-c, a-b-a-b-c. Mi pregunta es, al momento de contar las cantidades de caminos, ¿serían solo esos cuatro, o también cuento los equivalentes al empezar desde c (c-b-c-d-a, c-d-c-b-a, c-d-c-d-a, c-b-c-b-a)? Yo creo que tendría que contar los 8, porque son diferentes, mientras que en el caso n=2, si invierto los caminos (cambiando todas las a por c) obtengo exactamente lo mismo. ¿Es eso correcto?

Pido disculpas por usar el foro de intercambio general, pero el foro del práctico correspondiente aún no está habilitado.

Gracias,

Romina.

En respuesta a Romina Belen Garcia Camargo

Re: Ejercicio 5; práctico 9

de Claudio Qureshi -

Hola Romina.

La letra del ejercicio talvez no esté del todo clara. La idea es que tu te fijás un par de vértes (a,c) de C4 y luego contás todos los caminos desde a hasta c. 

Pero supongamos que queremos contar todos los caminos de largo n desde a hacia c y desde c hacia a. Entonces simplemente tenés que multiplicar por 2 el conteo anterior y listo (por cada camino a-b tomas el camino reverso b-a que recorre el camino en el sentido invertido). Hay un error cuando dices que en el caso n=2 obtenés lo mismo. Los caminos a-c de largo 2 son: a,b,c y a,d,c. Si los revertimos obtenemos los caminos c,b,a y c,d,a que son dos caminos distintos.

Creo que es importante remarcar lo siguiente: estamos trabajando en el contexto de grafos no dirigidos, pero cuando uno considera un camino (que por definición es una sucesión de vértices) este si tiene una dirección bien definida. Si invertis la dirección este resulta en un nuevo camino diferente al original (salvo que sea el camino trivial con un solo vértice, un loop o concatenación de loops). Lo mismo cuando contamos ciclos, en los ciclos importa la dirección y el punto de inicio. Fijate por ejemplo 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).

Cualquier otra dudas puedes usar este foro (creo que desde ahora vamos a usar solo este foro ya que desde los otros no me llegan notificaciones).