
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 3rd, 2013, 10:08 PM  #1 
Newbie Joined: Aug 2013 Posts: 2 Thanks: 0  Combinations to navigate a noncyclic directed graph
Hello, I need a formula and way (algorithm) to find all possibilities to navigate in a graph, with the following characteristics:  The graph will have n number of nodes;  The graph is directed (arrows);  The graph is not cyclic, that is, the edges tend always to the next nodes;  There are m types of edges, where m>=1;  An edge 1 can reach the next node, an edge 2 achieves the second subsequent node (the next is jumping), and so on;  Note that the last node will only receive nodes, and the latest will have restrictions on the number of edges because there are no more distant nodes; I made a figure (half ugly I know) to help in understanding. It has nodes n = 12, m = 3 edges; black=1, red=2, blue = 3. I need to know all the ways to navigate the graph, for example, the sequence of edges would these possibilities (and many others of course): 11111111111 1111111112 1211111111 121111121 2113211 33212 Note that the sum of the edges always give n  1 (do not know if this helps) I need a formal explanation, is for my dissertation. I thank you! Sorry my bad english, im brazilian. 

Tags 
combinations, directed, graph, navigate, noncyclic 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Maximum number of path for simple acyclic directed graph  jack1234  Applied Math  1  January 22nd, 2013 09:59 PM 
Complex Combinations Within Combinations Problem?  bugrocket  Advanced Statistics  2  January 23rd, 2011 05:02 PM 
Combinations within combinations possibilities?  aimpro2000  Advanced Statistics  2  September 20th, 2010 03:12 PM 
Number of directed graphs with no cycles  Rand  Applied Math  4  May 23rd, 2009 06:11 PM 
Directed Tree Calculator.  martsbradley  Computer Science  0  April 10th, 2009 03:47 PM 