Graph Theory: A wonderful world of dots and lines.

I took a great graph theory class 2 years ago in college...it was ok, but I think our professor kind of had a vendetta against computer science for some reason, so we skipped most of the cool applications and the class just became another class whose sole purpose seemed to be to teach us how to write proofs.

Now I don't have anything against proofs...in fact I quite like them, but a graph theory class where you don't learn about Dijkstra's algorithm or an adjacency matrix just isn't complete in my opinion...

Because of this, I've decided to look into some of the stuff we didn't learn about...some of the cool flow network problems and such. In an attempt to do that, I stumbled upon the "Art Gallery Problem." Enjoy ;)

The Art Gallery Problem

Imagine you are hired to oversee security for an art gallery. You've never actually been to this art gallery before, but you've been given an aerial picture layout of the building. You want to know how many security guards you will need to hire in order to have every inch of the gallery under surveillance at all times. For example, the following layout with four guards:

The gallery can be thought of as a polygon with n vertices.
In general it turns out, you can always guard this polygon with at most floor(n/3) guards and there's a really simple proof!

First, however, I have to prove a simple lemma:
You can always color the vertices of a triangulated polygon with at most 3 colors.
(so that no two adjacent vertices share a color)
The argument is simple.

1.) Take away some outside triangle.
2.) Inductively color the vertices of the rest of the graph with only 3 colors.
3.) Add back the triangle which you took away, coloring it with the only possible colors. (two of the three vertices will already be colored)

Proof:

Step one: Triangulate the polygon.
Step two: color the vertices of the polygon using 3 colors (as we showed you could do).
Step three: choose one of those colors to be our security guards and notice that every triangle is convex and can be seen fully by that color that is present in every triangle!

Thanks for reading this post. I hope to post more about graph theory in the future.

If you want to see more math like this,
check out my Introduction to Abstract Algebra posts
and follow me at @jackeown ;)