LOG#055. Will Hunting problems.Posted: 2012/11/27 | |
The off-topic post today (I am trying to edit a complete long thread about “fundamental constants” and “units” in Physics for the next posts, so be patient, please) is graph theory through a wonderful film. I have always loved the movie Good Will Hunting. It has some remarkable problems I solved long ago…Here you are my solutions ( and a final challenge at the end of this blog post to test your mathematical skills).
Problem A. Given the graph G below:
1) Find the adjacency matrix L of G.
2) Find the matrix giving the number of 3 step walks in G.
3) Find the generating function of the graph G for walks from node (i) to node (j).
4) Find the generating function for walks from point/node 1 to point/node 3. Explain the final result.
The adjacency matrix L or encodes some beautiful features of the graph. The entry is equal to k if there are k connections/links/edges between node i and j. Otherwise, the entry is zero. Problem A1 is to find L and A2 asks to find the matrix which encodes all possible paths of length 3. is by definition of the matrix product the sum
Each term in this sum, like is not 0 if and only if there is at least one path of length 2 going from i to j passing through k. Therefore, the matrix is the number of paths of length 2 leading from node i to j.
Similarly, will be the number of paths of length n going from i to j. A walk/path of length k is an ordered sucession of vertices and edges and such as if the walk is “closed” after k-steps/jumps from node to node.
Generating function/Generating function matrix. To a graph one can assign for pair of nodes (i,j) a series
and where is the number of walks from i to j with n steps. Problem A3 asks for a formula for f(z) and problem A4 asks an explicit expression in the case i=1,j=3. In the movie, the generating function is written in a different notation
The formula for the summation of a geometric series holds also for matrices, since
The Cramer’s rule for the inverse of a matrix is
and it leads to the equivalent formulae
as . For , we get
It can also be written as
Especially, when i=1 and j=3, we get
and . Then, the generating function can be written as the fraction
Indeed, the computation can be done for every pair of nodes. The generating function matrix comes from
A long and tedious calculation provides
Finally, let us remark that if we expand the generating function into an infinite series, we can obtain the number of walks of k-length as the numerical coefficient in the kth-power of z. In our example and problem from the Will Hunting’s movie, we deduce that
or up to 12th degree in z
Then, from the node 1 to the node 3 there is 2 walks of length 2, 2 walks of length 3, 14 walks of length 4, 18 paths of length 5, 96 paths of length 6, 146 walks of length 7, 638 paths of length 8, 1138 walks of length 9, and so on.
The movie provides this cool picture of the problem and the solutions I have already deduced
1) State the Cayley’s theorem/formula and explain its meaning.
2) Find every homeomorphically irreducible tree of degree 10 ( i.e., irreducible trees of 10 nodes non-isomorphic to each other, and without vertices of degree 2).
Answer B1. Cayley’s formula is a result in graph theory named after the mathematician Arthur Cayley. It states that for any positive integer the number of trees with labeled vertices is , i.e, it says that the number of trees on n-labeled vertices is .
Remark: The formula equivalently counts the number of “spanning trees” of a complete graph with n-labeled vertices.
Answer B2. The solution is given by the following trees
Only 8 of these graphs are in the movie, since when Will Hunting is writing them on the blackboard, Prof. Lambeau appeared and Will didn’t continue with the solution to the problem.
Remark: The counting function for homeomorphically (inequivalent) irreducible trees is
Homeomorphically irreducible trees are also called series-reduced trees or topological trees. Indeed, the generating function expansion is a series formed by the so-called number of reduced trees with n-nodes. It is the Sloane series A000014, and it is given by the following numbers:
Here you are the complete list of homeomorphically irreducible trees up to n=12 ( n=0 is absent since it is the empty set) :
PS: A final poster of the Good Will Hunting movie and some of the problem B solutions, with solution in b) being wrong in one case AND incomplete ( be aware!)…
PS(II): A challenge for eager readers is…Are you able to guess AND prove the complicated formulae providing the last series and numbers? I mean, are you able to find the generating function producing the series above?
It is not easy but it is fun and enlightening!