Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - directed graph

  1. #1
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778

    Re: directed graph

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34

    Re: directed graph

    can yu explain in detail
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778

    Re: directed graph

    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.
    Thanks from prasum
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. directed graph question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2011, 12:10 PM
  2. Directed graph statistics
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 10th 2011, 12:19 PM
  3. Replies: 0
    Last Post: April 28th 2010, 10:26 PM
  4. directed acyclic graph completion time distribution
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: August 14th 2009, 11:28 PM
  5. Drawing a directed graph
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2008, 08:38 AM

Search Tags


/mathhelpforum @mathhelpforum