Sunday, November 09, 2008

The Good Will Hunting Problem

Here is a problem from the movie Good Will Hunting, shown in the screenshot below.



For the the graph G(V,E) shown above, find the following :

  • The adjacency matrix A :
  • The matrix giving the number of 3 step walks in G : [Ak]ij is the number of paths of length k from i to j. So, the answer is A3.
  • The generating function for walks from point i to j : The generating function is as follows. Here are more examples of generating functions.
  • The generating function for walks from points 1 to 3 : Simplify the above formula using cramer's rule for i=1 and j=3.

2 comments:

Ivan Vučica said...

Interesting! Sadly, at the moment I only understand the first solution. Hopefully (or not) after going through some graph theory subject(s) I'll understand it better.

Interesting, anyway :)

Rajkamal said...

Excellent observation. Couldn't notice that while watching the movie.