Non-Hamiltonian Thoughts

A Graph (in computer science terms) is a collection of points and lines (edges) that connect them. Like this:

The points and the lines can symbolize many different things. For instance, points can be cities and lines can be roads. Or points can be people and an edge can mean that the two people it connects are friends.

For the purposes of this post, the points are different thoughts and facts and the line between any two of them means that they are connected.

Now, when I start writing an essay (or a blog post), one of the first things I do is gather up all my thoughts that might be relevant to the topic in my head. I then try to find a narrative that passes through all of them but proceeds smoothly from one thought to the next. This usually means that every new thought has to be connected to the one directly preceding it, which means that the essay turns out to be a "walk" in the Thought graph - you start at one point and then move along the edges until you eventually finish at some other point.

You usually have an idea what thought you want to end up at. And finding a path from the starting thought to the ending one is usually not hard. So, in formal terms, essay writing is in P.

However, imagine a different problem. You have some problem that you want to discuss with a friend. You want to give her all the relevant background information.. and you would prefer to give an essay-like presentation, smoothly moving from one point to the other without repeating yourself. In graph-theoretic terms, this is the problem of finding a Hamiltonian path.

And the sad fact is that for most graphs, this is impossible to do, and, even when it is theoretically possible, it is NP-hard to find such a graph.

So even when you have a fairly good idea about all that you would like to talk about, it is still hard, if not impossible, to formulate them in a linear and coherent way - especially if the graph is not connected enough.

As a corollary: topic jumps and/or repeating yourself are sometimes unavoidable, and should thus be seen as a normal part of conversation. After all, they are the only two solutions that still allow you to cover all of the graph.