Encontrar la matriz de adyacencia del siguiente ejercicio y que es la siguiente
Dibuja la correspondiente gráfica
Para 0 < k < 5, encuentra nk, en donde nk es el numero de caminos de longitud
k de v1 a v4
2 respuestas
Antonio: la respuesta te la dio Valero y está perfecta. Solo como aclaración te comento que A^n te dice cuanto caminos de longitud n existen. Si bien este caso era "sencillo", si tenés una matriz muy grande puede ser útil primero identificar cuantos caminos deberías hallar. Te dejo las imágenes de A^2; A^3 y A^4 para que veas de que se trata
Notas:
- Por ejemplo, en A^2 se puede ver los caminos de longitud 2 que existen son: 1 camino entre v1 y v3; 1 entre v2 y v4 ; y 2 caminos entre v1 y v4.
- Es fácil ver en esta matriz que las próximas mátrices darán 0
- Insisto en que este método NO te dice cuales son los caminos, pero al menos te da una pista de cuantos caminos tenés que buscar en cada caso (para completar lo que te pidieron faltaría poner A^0, pero esto no tendría sentido en el recorrido ya que es imposible ir de un elemento a otro distinto en cero pasos)
·
Esta es la gráfica:
Para k=0 ==> nk=0 no hay camino entre v1 y v4 de longitud 0
Para k=1 ==> nk=0 no hay camino directo entre v1 y v4
Para k=2 ==> nk=2 son
v1-->v2-->v4
v1-->v3-->v4
Para k=3 ==> nk=1
v1-->v2-->v3-->v4
Para k=4 ==> nk=0 es imposible llegar en 4 pasos
Para k=5 ==> nk=0 no se puede llegar en 5 pasos
·
Y eso es todo.
Si habéis dado el teorema de que el número de caminos de longitud k entre el vértice v_i y el vértice v_j es el elemento (i, j)-ésimo de la matriz A^k tienes que hacerlo tal como lo ha hecho Gustavo, yo no conocía ese teorema.