1 Dwalin: Soo where do hobbits live? Oondergroond?
2 Lambert: We live in villages. The best houses are finely furnished shallow burrows, but many live in cottages.
3 Lambert: The village street layout is critical. They need to be arranged so you can visit every house without travelling the same street more than once.
4 Dwalin: Why?
4 Lambert: Otherwise the path won't be Hobbitonian!

Yep, it's been 100 strips since the last hobbit pun.

A Hamiltonian path is, in graph theory, a path that connects every vertex of a graph (or every house in a village, as a concrete example), without traversing any edge of the graph (or any street of the village) more than once.

Hamiltonian paths come up in the famous travelling salesman problem: Given a list of cities and the distances between them all, what is the shortest path that visits each city and returns to the starting point? This problem is an optimisation problem of finding a Hamiltonian path that visits the cities, with the extra constraint that the path must be the shortest possible Hamiltonian path. It is a well known problem in the field of computational complexity because it is a classic example of an NP-hard problem - a full explanation of which would require digging deep into the realms of computational complexity theory, but which may be summarised as being a problem that is incredibly difficult to solve as the number of cities increases.

Given that hobbits deal with this sort of problem all the time in their villages, one suspects that while it's a difficult optimisation problem, it's not a very difficult hobbitimisation problem.

---

Reader Alec Cawley writes:

I think you have discovered a major piece of Middle-earth anthropology - how the Shire kept its idyllic structure of scattered villages. Villages can only grow as long as its Hobbitonian-ness can be checked by brute force - that is, by hobbits wandering round visiting their friends while recording their path. Obviously, a new street cannot be built until this property has been checked, a task which becomes impossible when a village exceeds the optimum size.