Find a recurrence to count paths in a directed graph

291 Views Asked by At

Suppose we have an unweighted directed graph with vertices numbered as $1...n$

From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$.

My task is to find a recurrence $f(i,j)$ to compute the number of paths from vertex $i$ to vertex $j$.

My current toughs:

For a base case, if $i \geq j$ then $f(i,j)=0$. For example, there is no path from $1$ to $1$, or from $2$ to $2$. And there is no path from $2$ to $1$.

For a general case, and when $i < j$, from $i$ there are edges to $i+1$, $i+2$ and $i+7$. So we can reach $j$ from $j-1$, $j-2$ and $j-7$. I think the recurrence depends on $f(j-1,j)$, $f(j-2,j)$ and $f(j-7,j)$.

Im doing well?, really i don''t find this intuitive at all.

1

There are 1 best solutions below

6
On BEST ANSWER

You’re on the right track.

Suppose that $i<j$. Each path from $i$ to $j$ must end with an edge from one of the vertices $j-7,j-2,j-1$ to $j$. Let $k$ be one of these vertices; there are $f(i,k)$ paths from $i$ to $k$, each of which extends to a path from $i$ to $j$ whose last edge is $\{k,j\}$. Thus, you can almost set

$$f(i,j)=f(i,j-7)+f(i,j-2)+f(i,j-1)\;.\tag{1}$$

There are a couple of potential problems here. First, one or more of $k\in\{j-7,j-2,j-1\}$ may be less than $i$. That’s not really a problem, since in that case we set $f(i,k)=0$, as you already did. Next, $j-7$, for instance, might be less than $1$. We can solve that by agreeing that $f(i,j)=0$ if $i$ or $j$ is out of the range from $1$ through $n$.

The last problem is what to do if one of the numbers $j-7,j-2,j-1$ equals $i$. In order for $(1)$ to give the right answer, we must have $f(i,i)=0$, as you have it in your question. However, this isn’t actually correct: there is one path from $i$ to $i$, of length $0$.

One way around this difficulty is to set $f(i,i)=1$ for $i=1,\ldots,n$ as an initial condition and then modify $(1)$ to read

$$f(i,j)=f(i,j-7)+f(i,j-2)+f(i,j-1)-\big[i\in\{j-7,j-2,j-1\}\big]\;,$$

where the last term is an Iverson bracket.

There are other ways to make the necessary adjustment, but the irregularity of the set $\{1,2,7\}$ makes all of them a bit messy.