seccion 8.4

[Damian Schlimovich]

Ej 41: Utiliza el Teorema 2 para cálcular la longitud del camino mas
corto de a a f en el multigrafo de la fígura 1.

Teorema 2(version resumida):sea A la matriz de Adyacencia del grafo, y
sea r la long de un camino. ----> A^r = a la cantidad de caminos de
longitud r.

NO SE COMO RELACIONAR CANTIDAD DE CAMINOS CON LA LONGITUD DEL CAMINO
MAS CORTO....

gracias
saludos

[Juan Daniel]

Creo que deberías hacer A^r (con r=1,2,3....)hasta que en la posición A[a,f] sea distinta de 0, el r el cual te dio seria la longitud del camino mas corto desde a hasta f.

--
Prigioni Juan Daniel
<jdpri...@gmail.com>

[Damian Schlimovich]

Gracias viejo, sos el unico en responder!!!.

Pero es incorrecto, ya q si miras el teorema 2,este dice q por ej:

queres saber la cantidad de caminos, de long 3 desde un vertice "a" a un vertice "b", le das valor a r como 3 es decir r=3. A la matriz de adyacencia original del Grafo G la elevas a r(es decir, la multiplicas por si misma r veces) en nuestro caso seria elevarla a la cubo(3). Luego en la posicion ij es decir en la i=a y j=b, te queda de resultado la cantidad de caminos con esa longitud.

A q va esto? si hago lo q vos decis de darle valores a r, lo que haces es ir tanteando y no creo q ese sea el objetivo del problema.

Reitero Muchas gracias por tu respuesta, me estaba dando la sensacion q el grupo SOLO era para el primer parcial...

saludos

--
Damian E. Schlimovich

[exequiel lares]

Hola. Es como te dijeron, mira la matriz de adyacencia  del grafo del ej 41 es:

         a b c d e  f
     a[ 0 1 0 1 1 (0) ]
     b[ 1 0 1 0 1  1  ]
A= c[ 0 1 0 1 0  1  ]
     d[ 1 0 1 0 1  0  ]
     e[ 1 1 0 1 0  1  ]
      f[ 0 1 1 0 1  0  ]

que es la de la figura 1 (si no entendi mal el ejercicio), como se ve desde 'a' hasta 'f' hay 0 caminos de longitud 1 (entre parentesis en la matriz), entoces ahora te fijas si hay caminos de longitud 2, para eso calculas A^2, que es:

              a b c d e  f
          a[ 3 1 2 1 2 (2) ]
          b[ x x x x x  x  ]
A^2=   c[ x x x x x  x  ]
          d[ x x x x x  x  ]
          e[ x x x x x  x  ]
           f[ x x x x x  x  ]

Como ves al calular la primer fila ya vemos que hay 2 caminos desde 'a' hasta 'f' de longitud 2 (entre parentesis en la matriz) y como no habia ninguno de longitud 1, la longitud mas corta es 2. Las 'x' son porque no es necesario calcular el resto de las posiciones de la matriz.

Espero que te sirva. Saludos

[Juan Daniel]

En realidad lo que yo digo es que primero hagas con r=1 si A[a,f] te da algo distinto de cero es porque el camino mínimo de a a f es 1, sino probas con r=2 y si ahí te da distinto de cero es porque el camino mínimo es 2, sino seguís (secuencialmente) hasta que te de A[a,f] distinto de cero. Como ibas aumentando la "longitud del camino buscado" desde a a f de uno en uno, el primer valor de r que te de distinto de cero en A[a,f] va a ser el camino mínimo. No se me ocurre otra forma de hacerlo con ese teorema. Saludos.

[Juan Pablo Lescano]

Se podría aplicar el teoréma de dijkstra y modificr el grafo para qeu sea uno "ponderado" con peso 1 en cada arista, entonces eso creo yo daría la longitud minima

[Pablo A. Kler]

También lo haría de esa forma. Saludos.

[Damian Schlimovich]

Muchas Gracias, al final era como decíamos..."tanteando", yo pense q era algo mas complicado q eso...

saludos

--
Damian E. Schlimovich