Skip to content

Good Will Hunting – Graph problems – The Gauntlet has been thrown down.

February 12, 2011

One of my favorite movies is “Good Will Hunting” as it’s filled some memorable and inspiring scenes. In this post i would like to discuss the exact problems the mystery Mathmagician ‘Will’ solves in the movie.

The first problem : This is a movie still of the blackboard Will notices

The question is : For the graph G

1) Find the adjacency matrix A
2) Find the matrix giving the number of 3 step walks
3) Find the generating function for walks from point i to j.
4) Find the generating function for walks from points 1 to 3.

I came across this page from Harvard that takes a look at the the above problem.

I was able to solve question 1 and 2, while i needed help through the Harvard page to understand the next 2 questions.Well question 1 is simple all you need is to map the graph to an adjacency matrix.
An Adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices.

So the graph looks like this

The adjacency matrix is:

For a adjacency matrix L of a undirected graph the entry Lij is equal to k if there are k connections between node i and j. Otherwise, the entry is zero

In question 2 we have to find all paths of length 3.

For adjacency matrix L. The matix [Lk]ij is the number of paths of length k from i to j. So, solution is L3.

matrix giving the number of 3 step walks in G :

Let me walk through the number of paths between nodes 1 and 2 of length 3:
There are 7 paths in total and thus the value for L12 is 7.

NOTE: for an undirected graph between two nodes 1 and 2 without cycles the length of path from node 1 to itself is 2 i.e 1 to 2 and back from 2 to 1.

a) 1 – 2 – 4 – 2
b) 1 – 2 – 1 – 2
c) 1 – 4 – 1 – 2
d) 1 – 2 – 3 – 2
e) 1 – 2 – 3 – 2
f) 1 – 2 – 3 – 2
g) 1 – 2 – 3 – 2

Notice the last 4 paths are in fact not repeats since 2 – 3 is a loop there are 4 paths between 2 and 3
one path across first line,
second path across second line,
third path across first and second line,
fourth path across second and first line.

so this is what’s on the board, at least the director made sure to put the correct answer on the board ;)

Kindly look into the Harvard article for the solution of question 3 and 4.

The Second problem:

Professor Gerald Lambeau comes to the class and announces a problem that has taken MIT professors 2 years to solve and that the gauntlet has been thrown down for the students.

Problem :Find all Homeomorphically Irreducible Trees of degree ten (i.e ten nodes)

An irreducible (or series-reduced) tree is a tree in which there is no vertex of degree 2 and is also called Homeomorphically Irreducible Tree.

It means we need to join ten nodes together such that all nodes are connected to at least one other node.No cycles are allowed and only one line is allowed between two nodes. Most important property of a homeomorphic tree must be satisfied i.e all nodes must have 1 or more lines connecting to other node and no node can have degree of 2(i.e a node should not have 2 lines coming out of it or going out of it whichever way you see it)

the silent rogue ‘Will’ solves this problem in this famous scene:

Will unmasks 8 of the graphs before being confronted by Professor Gerald Lambeau. This is his answer :

Here is the solution:


About these ads

From → Algorithms, Trees

  1. alex mills permalink

    So I was curious how important this problem is because I believe it is incorrect. I have found more solutions to trees of size n=10 and n=11. Mostly curious if its even worth sharing to the world.

Trackbacks & Pingbacks

  1. Quora

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: