My Math Forum  

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

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
January 22nd, 2013, 05:57 PM   #1
Newbie
 
Joined: Jan 2013

Posts: 2
Thanks: 0

Maximum number of path for simple acyclic directed graph

Say given a simple acyclic directed graph with n nodes , which includes a starting node s0 and ending node e0 (i.e., a kripke structure without loop)
what is the maximum number of path from s0 to e0?
jack1234 is offline  
 
January 22nd, 2013, 08:59 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Maximum number of path for simple acyclic directed graph

It seems like it's 2^(n-2)... at the least this is a lower bound.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
acyclic, directed, graph, maximum, number, path, simple



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Combinations to navigate a non-cyclic directed graph lfccruz Applied Math 0 September 3rd, 2013 09:08 PM
Number of path in Kripke Structure jack1234 Applied Math 1 January 27th, 2013 02:51 AM
path dependent function with a definite path aise5668 Real Analysis 3 March 5th, 2012 06:36 PM
Number of path components? skychan Real Analysis 3 November 5th, 2009 08:10 AM
Number of directed graphs with no cycles Rand Applied Math 4 May 23rd, 2009 05:11 PM





Copyright © 2018 My Math Forum. All rights reserved.