1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ The visualisation on wikipedia shows the problem in the form of a cube. That cube is a bipartite graph. $\endgroup$
    – Hendrik Jan
    Apr 3, 2021 at 11:11
  • $\begingroup$ ok, the cube after crossing out the invalid situation is bipartite $\endgroup$
    – kiv
    Apr 3, 2021 at 11:26
  • 1
    $\begingroup$ @kiv. The cube is bipartite even without deleting the invalid edges. $\endgroup$
    – Steven
    Apr 3, 2021 at 13:51

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If we do not take boat in the consideration,will we have a graph with 8 vertices? $\endgroup$
    – kiv
    Apr 3, 2021 at 11:17
  • $\begingroup$ Well yes, that seems to be also a possibility, but I'm not sure the resulting graph will be bipartite. $\endgroup$
    – Nathaniel
    Apr 3, 2021 at 11:18
  • $\begingroup$ How would the final graph with 16 vertices would look like, will it be 8 vertices on each side? $\endgroup$
    – kiv
    Apr 3, 2021 at 11:21
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Nathaniel
    Apr 3, 2021 at 11:27
1
$\begingroup$

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:

enter image description here

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.