Number of routes between two cities?
there are seven cities - A, B, C, D, E, M, N-which are connected by roads to each other as: (one way routes): A to B, C to E, M to B, D to B, B to C, A to M, A to N. (two way routes): M and D, C and D, C and N, N and E. what is the total number of routes by which city E could be reached from A, such that no city is visited twice in any routes?
(Mar 19 '12 at 22:53)answerer
|
I am sure there will be many ways to solve this problem. Here is of the ways. The first thing I do with is these kind of problems is to draw a graph. Here it is -
Now, we need to find all the paths from A to E such that no city is visited twice. So I will convert this graph into a tree - A very deep tree which starts from A and keep traversing all the paths denoted by arrows unless two things happen - we come across E or we come across a city twice. After building the tree, count the number of Es and you will get the number of routes through which you can get to E from A. For better representation, I marked E with circles and repeat cities with squares. in the figure below -
 |
