[Math] Recurrence relations – walk on a graph

discrete mathematicsrecurrence-relations

given the following undirected graph:

enter image description here

I need to find a recurrence relation that describes the number of possible walks starting at point A.

Well, naive me Iv'e defined $ a_n $ and tried to find the rule, but I got to a dead end.
Eventually, I looked up the answer and found that they have defined two relations:

$ a_n $ – for walks start from A or D
$ b_n $ – for walks start from B or C

Then, it is easy to see that:
$$
a_n = 2b_{n-1} \quad\quad
b_n = 2a_{n-1} + b_{n-1}
$$

And this one is pretty easy to solve..

BUT it did not come to my mind before looking at the answers!

In a matter of fact, I never really understood in what cases I should define more than one relation, and why in this specific case it is the right way to do that?

As you understand, I don't need the answers for the specific problem, but want to learn the way of thinking about this kind of questoins, since I keep doing mistakes in them.

Thanks!

Best Answer

There is a general tool to reason about various numbers of walks in an (undirected) graph - the adjacency matrix. If we have a graph $G$ with adjacency matrix $A$, then the row of a vertex $v$ in $A$ tells us the number of length-1 walks to each other vertex. Similarly, the row of $v$ in $A^2$ tells us the number of length-2 walks, and so on, the row of $v$ in $A^n$ tells us the numbers of length $n$-walks to any other vertex. The recurrence you're looking for will pop up from the equality $A^{n+1}=A\times A^n$.

You can compute fancier things than that, if you multiply $A^n$ on the left with an appropriate vector, such as find the number of walks that start in a given set of the vertices and end in a given set of the vertices and so on. The idea also generalizes to directer graphs and multigraphs.

EDIT: oops that's not what the question was about. OK, so general intuition for recurrences is not that easily made explicit, it takes some time and experience. However, there are several things that help:

  • usually you have some situation for $n$ and you want to find some quantity $q(n+1)$ describing the situation for $n+1$. Don't shy away from assuming any information about the $n$ case you might, and just try to write down an expression for $q(n+1)$ even if it involves things other than $q(n)$, such as some $r(n)$ or $s(n)$ or whatever. Then when you've identified which parts of the information about the $n$ case are useful, you can think about finding them recursively; often, they will be related to one another and to $q$. You need to get a feeling for when you need to assume you have more information (the $r,s$) at the $n$ case than the problem explicitly asks from you.
  • Do dynamic programming questions, I think they help a lot with that kind of problems.
Related Question