Hi there!
My name is Xavier and here is an interesting puzzle for you.
Imagine you’re a farmer who just purchased a wolf, a sheep and a cabbage on the local
market.
Kind of a strange situation, but just go with it…
On your way back home you have to cross a river with your boat.
However, the boat is so small that it can only carry you and 1 other item.
To complicate matters even further, you can’t leave the sheep alone with the wolf because
the wolf will eat it.
Likewise, the sheep will eat the cabbage if you leave them unattended.
This is called a “river crossing puzzle”, a type of “transportation puzzle” and
it’s a relatively simple one.
You can probably solve it with a minute of thinking.
So go ahead, pause this video and think about it for a bit.
I’ll wait here…
It probably didn’t take too long for you to realize that you have to take the sheep
across first because the wolf won’t eat the cabbage.
Then you go back to fetch wolf, but since you can’t leave these two unattended, you
take the sheep back across the river.
Then you take the cabbage across because the wolf won’t eat it and finally you go back
to fetch the sheep.
Tada!
All of your purchases have now made it safely across the river.
Because the puzzle is so easy, you can solve it with trial and error.
But how do we know that the solution we found is the only solution?
And how do we solve more complex puzzles?
Our guesswork isn’t very scalable and becomes harder if we add more variables to constrain
this puzzle.
So, instead, we can use something called Graph Theory, a field in mathematics which studies
graphs.
A graph is a representation of elements that are connected by lines.
Each element is called a node and the connections between nodes are called edges.
Now let’s solve our puzzle by using graph theory.
We’ll start by writing down all the valid states for our puzzle.
The starting state is simple: the wolf, sheep, cabbage, and farmer are all on one side of
the river.
The desired end state is also easy: all of them have to be on the other side of the river.
From there we can for instance start by transporting the sheep across the river (2).
We can do that because the wolf won’t eat the cabbage and we can travel back as well
because the sheep is fine by itself (3).
The inverse of these two states is also valid so we can write those down as well (4, 5).
Now let’s go back to state 2, from here we can transport the cabbage across (6) and
leave the wolf alone.
Just like before, the inverse is valid as well (7).
But now we have a problem.
We can’t leave the sheep and cabbage alone so we have to take one of them back with us.
If we take the cabbage back with us, we end up in state 3, so let’s take the sheep back
across instead (8), and once again the opposite situation is valid as well (9).
And that’s it.
That leaves us with 10 valid states for our puzzle.
With this list in hand, we can start constructing our graph.
We’ll start by creating a node for each of the possible states of our puzzle and we
will connect two nodes if we can move between those states.
So our first node is number 1, where everyone is on one side of the river.
From there we can only go to state 2 because we can’t leave the wolf with the sheep or
the cabbage with the sheep.
Then we can only go to state number 3, where the farmer goes back across the river.
But now he faces a choice.
He can either go to state 9 and take wolf across or he can go to state 6 and take the
sheep across.
From there both routes have just one state they can go to until they converge together
on state 5 and finally end up in the desired state.
What we drew here is a simple graph and it clearly shows us that there are two different
solutions to this puzzle.
Who would’ve thought!
Now it’s important to note that this is not a directed graph even though I used arrows
to connect the nodes.
You can always go back and forth between states.
But going back and forth between states is rather pointless if you want to get to the
desired end state.
So, we solved our puzzle by using graph theory, but where did it come from?
Well, it all started in 1736 when Leonhard Euler became fascinated by a game that the
citizens of Königsberg were playing.
The city is built around a river and had 7 bridges that connected the different parts
of the city together.
Citizens were trying to walk around the city by crossing all 7 bridges but never crossing
the same bridge twice.
Euler wanted to solve the problem with mathematics and started by reformulating the problem in
more abstract terms.
He stripped away all of the information that isn’t relevant like for instance the route
you take on the land.
Only the sequence of bridges you cross is important.
So you could translate the city into this graph where each node represents a landmass
and the edges represent the bridges between them.
Euler also realized that each node in the graph needs an even number of edges for the
puzzle to be solved.
The number of edges that a node has, is called its degree and it makes a lot of sense that
these have to be even to solve the puzzle.
When there are 2 bridges towards a particular part of the city, you need 2 other bridges
to leave it again if you want to travel across each bridge just once.
However, not all of the nodes need to have an even degree.
If there are nodes with an odd degree, then your path has to begin at one of them and
end at the other.
But in this particular situation, there are 4 nodes with an odd degree, so you can’t
walk across the city and only cross each bridge once.
Our puzzle has no solution and Euler was the first to prove it mathematically.
Because his work kickstarted the field of graph theory, other researches gave a name
to the path that goes through all of the edges without visiting the same edge twice, a Eulerian
path or Euler walk.
One interesting side-fact: here we’re visualizing a graph by using circles and lines to represent
nodes and edges.
The way you represent them however is not important and in fact visualizations aren’t
necessary when studying graphs.
Euler himself didn’t draw any graph in his original paper.
Kind of a bummer that we can’t solve the Königsberg problem.
However, since Euler’s paper, the city has changed substantially.
During a bombing in World War 2, two of the seven bridges were destroyed and later, two
others were demolished.
An updated graph representation would now look like this.
Two of the nodes now have a degree of 2 while the remaining nodes have a degree 3.
That means that we can now walk across all of the bridges without crossing the same bridge
twice.
That is if we begin on one island and end on the other.
So with graph theory, you can solve transportation puzzles, but what else?
Well, how about navigating around a city?
Navigation software, like Google Maps, uses a graph to represent the road network and
to calculate the fastest route to your destination.
Each road is represented by an edge that has a certain weight.
This could be the travel time or the distance of the road.
Finding the shortest or fastest route between point A to point B can then be solved by applying
a graph algorithm like A* or Dijkstra’s algorithm.
Or think about social networks that can use graphs to visualize the friendships between
people.
Or cryptocurrencies like IOTA who use a directed acyclic graph to store transactions.
More about that in this video right here.
To summarize, graph theory can be applied to a variety of topics and can solve interesting
problems.
So, that was it for this video.
If you found it interesting to learn about graph theory and about farmers who make weird
purchases, hit the thumbs button and consider getting subscribed.
Thank you so much for watching and I’ll see you in the next one!