My Math Forum Combinations to navigate a non-cyclic directed graph

 Applied Math Applied Math Forum

September 3rd, 2013, 10:08 PM   #1
Newbie

Joined: Aug 2013

Posts: 2
Thanks: 0

Combinations to navigate a non-cyclic 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.
Attached Images
 combinatorial.jpg (110.4 KB, 111 views)

 Tags combinations, directed, graph, navigate, noncyclic

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post jack1234 Applied Math 1 January 22nd, 2013 09:59 PM bugrocket Advanced Statistics 2 January 23rd, 2011 05:02 PM aimpro2000 Advanced Statistics 2 September 20th, 2010 03:12 PM Rand Applied Math 4 May 23rd, 2009 06:11 PM martsbradley Computer Science 0 April 10th, 2009 03:47 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top