The Strangest Construction Manager
Imagine, for a moment, that you're building a factory. It's your job to decide where the machines go, and how to connect them. You've not been told what you're going to be building, so you need to know what you can possibly put in the factory.
Unfortunately your construction manager is a rather eccentric fellow. He's built a factory floor with infinite floor space, but no third dimension. He's also wanting to know what machine layouts we can build in the factory without building them. Sounds easy, right? We have infinite space. We can do ANYTHING.
He might look something like this.
But hold on, you've just remembered another of his particular quirks. He insists on having the machines in nice neat rows and columns. He's also a cheapskate, so has only ordered one size of conveyor belt to get the machines connected together.
Schematic of possible layouts illustrating the construction rules.
Does this restriction limit the kinds of setups we want to put in the factory? Read on to find out...
We're going to take a small detour for a second- don't worry, we're going to keep our construction rules in the back of our minds. What we're going to do is introduce what we're really talking about- Graphs.
...Probably most of your reactions right about now.
4 kinds of graphs (top left to bottom right): A 5-vertex, 7-edge graph; K4; P5; K3,3.
Hold on, don't run away! I don't mean those kinds of Graph! I mean this kind of graph, with vertexes (points) and edges (lines)! In the diagram to the right, you can see 4 graphs. The first could represent a group of friends where some of the people live within walking distance. If they do, they have an edge connecting them.
The second is what is known as "The Complete Graph on 4 vertices, K4" and represents an important kind of Graph. A Complete Graph is one where every vertex is connected to every other vertex.
The third kind of Graph in the picture is a Linear or Path Graph. These will also be important to us. These could represent a production chain with intermediate steps, but without any extra materials being added at any stage. This could also represent a list of places a bus stops at along its journey.
Finally, the fourth graph represented is another famous graph- the Three Utilities Problem. We won't talk about the problem itself here, but Grant Sanderson of 3Blue1Brown has a very good video on it here. What we want to take from this graph, however, is that it is non-planar- it cannot be drawn on a page without the lines crossing in at least one place.
Now we've learned what a graph is, how the hell does this help us?
If you've not seen our little trick yet, here's a clue. Think of the machines for a possible layout as the vertices of some graph, and the conveyor belts as the edges of that graph. Don't worry about thier direction- that can be safely ignored!
What we've created is what proper mathematicians like to call a Surjective Map. (I won't dwell on the mathematical terms here, but if I ever do a series on mappings and categories, this will be good to note). What this means concretely for us now is that for every factory layout, there is a single graph, but multiple layouts may map to the same graph.
A couple of examples of our mapping.
Why is this mapping to graphs useful? It allows us to tap into the machinery of Graph Theory very easily! It also allows us to abstract away the unimportant details and get right to the heart of the problem at hand. Finally, it lets us use the results we get in other situations- so long as we can map to graphs and lattices, we can use these findings! We've managed to unite a whole class of disparate situations into one neat framework of ideas.
Overall, we've gained a starting insight into the problem we're trying to solve. Those of you paying attention, however, will have noticed something sneaky in the last paragraph- the word Lattices. What are those? Well, I think I've said enough for this week. You'll just have to tune in soon to find out!
-Wolfie <3
