Bipartite Graph to solve the wolf river crossing problem

I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving this question, now I was wondering how can we describe the problem in bipartite graph, as to describe it we need to divide the problem into two disjoint and independent sets, I am getting very confused as how it can be done?

It will be helpful, if someone can help me understand it as there is no information about this wolf river crossing problem on the internet.

• The visualisation on wikipedia shows the problem in the form of a cube. That cube is a bipartite graph. Apr 3, 2021 at 11:11
• ok, the cube after crossing out the invalid situation is bipartite
– kiv
Apr 3, 2021 at 11:26
• @kiv. The cube is bipartite even without deleting the invalid edges. Apr 3, 2021 at 13:51

I have never really imagined solving this problem with a graph, but it is an interesting point of view.

My guess is that the graph you have to create is a bipartite graph with 16 vertices, each vertex representing the state of the situation, that is representing where is each of the different actors of the problem: the wolf, the goat, the cabbage and the boat. Each actor have two positions possibles (each side of the river), so $$2^4 = 16$$ different configurations. You might then delete forbidden configurations, representing a case where the wolf is alone with the goat or the goat alone with the cabbage.

Now, you can add an edge between two vertices $$v$$ and $$w$$ if and only if you can go from $$v$$ to $$w$$ by crossing the river with the boat, with one actor from wolf/goat/cabbage on board.

The graph is indeed bipartite, because there are no edges between two vertices where the boat is on the same side.

Solving the problem now results in finding a path between the two vertices where the four actors are on each side of the river.

• If we do not take boat in the consideration,will we have a graph with 8 vertices?
– kiv
Apr 3, 2021 at 11:17
• Well yes, that seems to be also a possibility, but I'm not sure the resulting graph will be bipartite. Apr 3, 2021 at 11:18
• How would the final graph with 16 vertices would look like, will it be 8 vertices on each side?
– kiv
Apr 3, 2021 at 11:21
• You can imagine a binary encoding $(b_0b_1b_2b_3)$ where the indexes $0, 1, 2, 3$ stand for wolf, goat, cabbage, boat, and $b_i = 0$ if $i$ is on the first side of the river, and $b_i=1$ otherwise. Each side of the graph would then correspond to $b_3 = 0$ and $b_3 = 1$. Apr 3, 2021 at 11:27

I think the best bet is to create a set of vertices which are permissible states (on one bank or the other), with the edges representing permitted transitions between them. Note that the presence of the farmer is also part of the state, so the two parts of the bipartite graph are nodes with & without the farmer. So this is a variation on the previous answer that limits the created nodes. Using the state on the starting bank and coding the presence or absence of each component in to a binary tuplet (farmer, wolf, sheep, cabbage) we have the permitted states: $$\begin{array}{c} & \text{with farmer} & \text{without farmer} \\ \text{initial state}& (1,1,1,1) & \\ & (1,1,1,0) & \\ & (1,1,0,1) & (0,1,0,1)\\ & & (0,1,0,0) \\ & (1,0,1,1) & \\ & (1,0,1,0) & (0,0,1,0) \\ & & (0,0,0,1) \\ & & (0,0,0,0) &\text{target state}\\ \end{array}$$

(As you may notice, the no-farmer states govern what is permissible; by inference, the state on the other bank eliminates some with-farmer states). Then the edges represent feasible journeys:

, and the problem is finding a path between the initial and target states.