-2

I have the solution to a word problem, which seems like a directed acyclic graph and I do not see how the author came up with the edges they did. The problem is if Tie can be worn after shirt. Socks after trousers and shirt. Shoes can be worn after socks. Belt can be worn after socks. How many different paths are there? Can someone provide the graph with nodes numbered from 0 - 5 for each event? The edges I have as the answer are 5-2, 5-0, 4-0, 4-1, 2-3, 3-1

Sean
  • 1
  • What do you mean by "how many different paths"? If you mean how many different orderings of the six events satisfy these conditions, then that makes the problem well-posed. Is this what you want? – Mark Fischler Jun 23 '17 at 00:54
  • yes, they asked for the number of ordering. – Sean Jun 23 '17 at 10:48

1 Answers1

0

The answer is that there are only six possible orderings. The key is that the socks have three items that must precede them, and two that must come after them.

So for each ordering of Tie, Shirt and Trousers, there are two distinct "paths", because the shoes can come before or after the belt; there is no other freedom because both are stuck being after the socks.

Now there are $3!=6$ conceivable orders for Tie, Shirt and Trousers, because they are stuck coming before the socks. Of those six conceivable orders, three must be discarded because they had shirt after tie.

So the total number of paths is $2\times 3 = 6$.

Mark Fischler
  • 41,743
  • -Thanks. I am trying to figure out how the solution provider numbered the graph to come up with the edges he/she did. I don't think that will impact the final answer, I just don't see what index number they assigned to socks for instance. I think they got the edges wrong, as there are no nodes with one edge only, and that is contrary to the definition of an acyclic graph. Also, are you saying finding the longest path in problems like this is the strategy to use to solve them? – Sean Jun 23 '17 at 08:55
  • I guess the more important question would be, is this problem solved or represented with an acyclic graph and would Khan's algorithm apply to it? These are the concepts I see within the context of the solution I got for this problem, and I am trying to fit all the pieces of puzzle. I also have to add the solution is not from an expert, I saw it online, and a few other people seem to agree on it, but it is not from a text book or anything like that. – Sean Jun 23 '17 at 10:22
  • They solved this problem by doing a Top Sort, which now that I see the solution you provided, was an overkill for a simple problem. – Sean Jun 23 '17 at 10:35