Why are graphs useful

Language: English/Inglês What is in this post: "Draw this figure wihout lifting your pencil" problem, Seven bridges of Königsberg problem, "Houdini's last trick"-simplified problem, graph representation of a problem, Eulerian trail, solution to problems

Wassup?
I've got 3 problems for you to solve. Ok, you don't need to solve them, but just try to read and understand them.

1. Drawing a figure

Can you draw this figure without lifting your pencil and writing any segment twice?

2. Seven Bridges of Königsberg

Find a walk through the city that would cross each and every bridge once and only once. The islands cannot be reached by any route other than the bridges, and every bridge must be crossed completely every time: one can't walk halfway onto the bridge and then turn around and later cross the other half from the other side.

3. Safe house

Mr. Vinci wants to close all the doors in his house. He wants to find a route such as he doesn't need to cross any door twice. He doesn't care whether he starts and finishes inside or outside the house. Can you help him?

Guess what... The problems are all the same with just different topologies. I know, it's kinda obvious now that you read them all in a row. But had I shown you problem 3 last week and now problem 2, you probably wouldn't realize they are the same kind of problem, unless you already knew this kind of stuff.

Just like there is a large amount of problems which can be translated into a simple equation, there is a large amount of problems which can be represented by a graph. What's the point? Well, many times, the context in which a problem is presented to you provides unnecessary details for it's resolution. If we can represent those problems in a consistent way that allows us to abstract ourselves from those details, we will be more successful at solving them. And a graph is a great representation for all these problems and many, many more (believe me, even some weirdest looking problems may end up being easily solved when represented through a graph) .
I bet that you can solve any of this problems easily, but just let me increase their dimensions and you will have a hard time unless you create a decent algorithm to do it. (even thought I won't focus on that  matter in this post, keep reading for some clues)

So what is a graph? Son, don't hope for me to explain you, but let me tell you, they aren't the plotting functions graphs in case you are thinking that. Just eat some wikipedia cerials!

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges.

So how would be the graphs for the problems presented above?
Like this:

Note: It is often good idea to label vertices or/and edges of the graph depending on the problem. In these problems, the focus is on the edges, so I labeled them. The numbers on the first image don't represent a weight of the edges in anyway: they are just labels. You can click on the image to see it in a bigger size.

There are graphs of various types and with different characteristics. For example, there can be weighted graphs when we have associated with each edge a cost (this cost can be money, gas, distance, time, etc..). We can have directed graphs where each edge can only be crossed in one direction... There is much to explore. Eat as many wiki cerials as you want on this.
In our case, our graphs are undirected (or directed if you double the number of edges by replacing each current edge \(x\) for \(x_\nearrow\) and \(x_\swarrow\)) and unweighted, since we don't care about any kind of cost associated with the edges.

My point with this post was to show you that graphs have the potential to reveal a "common denominator" for various problems and allow a -more focused on important things- approach.
But now it would be kinda anti climatic if I didn't talk about the solution for the problems so here we go...

All these problems challenge you to find the same thing, an Eulerian trail:

An Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. If such a path exists, the graph is called traversable or semi-eulerian.

Euler stated and it was later proven that an undirected graph has an Eulerian trail if and only if it has exactly 2 or 0 vertices with an odd number of edges. Why, might you ask? Well, you can convince yourself that this is true with empirical reasoning (although there are formal mathematical proofs for it).For example:

• You can think that every time you enter on a vertex, you will also need to leave it. If you enter it twice during your trail, you will also need to leave it twice. Also if you quited a vertex, you had to have entered on it before.The exception for this statements are the first and last vertex - you can leave the first vertex without ever entering on it, and you can enter on the last vertex without ever leaving it. So for every vertex in the middle of the trail, you need  a pair number of edges.
  
• You can imagine a squared shaped graph where your path will start and finish on the same vertex. If you add an edge to the graph on that vertex to make your possible path longer, you also have to add an edge somewhere else, otherwise the vertex would have an edge connecting to empty space.
• This operation took you from a graph with 0 odd degree vertices to a graph with 2 odd degree vertices. You just can't find an Eulerian trail with a different number of odd degree vertices, accept that xD
  

So the solutions to our problems are: 1-Really? 2-Impossible 3-I mean, really :| ?

There are many algorithms for finding Eulerian paths. Hell, you can even find them with elementary linear algebra, or a backtracking algorithm (not the best methods). If you use the first, you will need a veeeery big system to find the solution to all the variables. So, yeah, not a task for a human when the number of edges starts to get bigger then 5. Computers can do it ;). Check this out for much better algorithms to do it - which, by the way, I'm not familiar with:
http://en.wikipedia.org/wiki/Eulerian_path


Hasta la vista baby.