The graph is a weighted undirected connected 3-regular graph. The number of nodes is N.
For each node there is one loop with weight $= \frac{1}{N}, and two other edges which goes from the node to its two ``nearest neighburs with weight $= \frac{\epsilon}{N}, where \^epsilon is a small parameter.
Therefore, we would like to know for a given value of $N$ how many different paths of lenght $2T$ are possible to go from one node to another passing through $k$ edges with weight $= \frac{\epsilon}{N}$ ?
Thank you for your answer.
I would like to find an analytical solution for a given value of N and T.
Maybe I can find it by some numerical putting some small values to N and T.
its very easy using Maple to find such a solution. I would think there are only two cases between nodes x and y. Either x=y or x \neq y. The transition matrix is tridiagonal. I think its easy to doagonalize using orthogonal polys.
I agree with Prof. Patrick Solé. Maple is a very useful software for any kind of mathematical operations.
The number of paths of length n on the pair of given vertices (vi, vj) is the (i, j)th entry of An where A is the adjacency matrix of the given graph G.
You may refer refer the following link.
B Roberts, D P Kroese, Estimating the Number of s-t Paths in a Graph, http://jgaa.info/accepted/2007/RobertsKroese2007.11.1.pdf
Also visit the following page for a recursive algorithm to find all paths between two given vertices of a given graph. http://www.technical-recipes.com/2011/a-recursive-algorithm-to-find-all-paths-between-two-given-nodes/
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability
- Probability Theory