Thread: directed graph

three missionaries and three cannibals must cross a river using a boat which carries at most two persons.the constraint is that the missionaries present on any bank of the river cannot be outnumbered by cannibals(otherwise the cannibals would eat the missionaries) the boat cannot cross the river by itself.prove a solution for the same.also draw the directed graph.

i have made the cases but am not be able to make the directed graph of this problem

please help

I am not sure which graph the problem statement talks about, but I guess the vertices are states of the system. If so, then there are 10 vertices (m, c) where 0 ≤ c ≤ m ≤ 3 and m, c represent the number of missionaries and cannibals, respectively, on one bank (the number of missionaries and cannibals on the other bank is then uniquely determined). There is an edge from v1 to v2 if there is a way to convert v1 into v2 by crossing the river.

can yu explain in detail

Read the Wikipedia article about the problem. In particular, it describes how problem states are represented using triples of numbers.

I was wrong about the constraint on the states in post #2. Namely, I wrote that if there are m missionaries and c cannibals on the initial bank, the constraint is 0 <= c <= m <= 3. In fact, if 0 < m < 3 (i.e., there are missionaries on both banks), then we also must have 3 - c <= 3 - m, which, together with c <= m, implies that c = m. However, if m = 0 or m = 3 (i.e., all missionaries are on the same bank), then cannibals may be located on either bank since if there are no missionaries, there is no one to eat. Thus, ignoring the boat, the valid states (m, c) are (3, 3), (3, 2), (3, 1), (3, 0), (2, 2), (1, 1), (0, 0), (0, 1), (0, 2), (0, 3), i.e., 10 states.It is possible that not all of them can be reached from the initial state (3, 3). If we add the third component representing the boat, as the Wiki page describes, then there are 20 states that satisfy the constraint.

The Wiki page describes which state can result from another given state. If such states are connected with directed edges, you get a directed graph. Most likely, the graph is not connected, i.e., one cannot travel from every state to every other state in the direction of the edges. Since we are interested in the states reachable from the initial state and since the total number of states (20) is somewhat high, the Wiki page recommends drawing just the tree of states reachable from the initial state.