Supongamos que existe un grafo cuyas aristas tienen pesos enteros. Quiero obtener el número de caminos de longitud n (número natural) desde un vértice concreto a otro. ¿Habría una forma adecuada de manipular la matriz de adjecencia o la matriz de incidencia o la exponencial de la matriz de incidencia o cualquier otra matriz para obtener este resultado?
Una mínima insinuación también será de gran ayuda.
Gracias de antemano.
Un enfoque sería construir un grafo dirigido en el que cada arista de longitud $k$ en el original se sustituye por dos caminos dirigidos, uno en cada dirección (cada uno con $k$ bordes y $k-1$ vértices completamente nuevos).
El problema de este enfoque es que el grafo dirigido resultante puede ser muy grande, especialmente si algunos de los pesos son grandes.
Por otro lado, la matriz de adyacencia de este grafo será muy dispersa, y es posible que se pueda aprovechar algún tipo de estructura de bloques dentro de ella.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
