My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
September 3rd, 2013, 09:08 PM   #1
Joined: Aug 2013

Posts: 2
Thanks: 0

Combinations to navigate a non-cyclic directed graph


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):

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
File Type: jpg combinatorial.jpg (110.4 KB, 111 views)
lfccruz is offline  

  My Math Forum > College Math Forum > Applied Math

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 08:59 PM
Complex Combinations Within Combinations Problem? bugrocket Advanced Statistics 2 January 23rd, 2011 04:02 PM
Combinations within combinations possibilities? aimpro2000 Advanced Statistics 2 September 20th, 2010 02:12 PM
Number of directed graphs with no cycles Rand Applied Math 4 May 23rd, 2009 05:11 PM
Directed Tree Calculator. martsbradley Computer Science 0 April 10th, 2009 02:47 PM

Copyright © 2018 My Math Forum. All rights reserved.