Thread replies: 6
Thread images: 1
Thread images: 1
File: Untitled.png (16KB, 1152x648px) Image search:
[Google]
16KB, 1152x648px
Hey guys, I have a graph theory/traversal/counting problem that I'm not sure how to figure out. For a graph/tree like the one posted, how do I count the number of possible depth-first search traversals through the tree? My intuition says the answer is something along the line of (options per branch)! + (options per branch 2)! + ... + (options per branch n)! , but I haven't found a rigorous solution. Any ideas?
>>
>>8736371
Its the number of leaves? Wait, no, it's a bit assymetric, so it's tricky
Number of leaves is the number of possible first traversals, then * n-1 for each n-branch already touched / or * n otherwise?
6 * 2^3
>>
>>8736371
Pascals triangle. Look it up
>>
[eqn]\prod_{v \in V \setminus L} (c(v)-1)[/eqn]
where L is the set of leaves and c(v) is the number of children of v
>>
>>8738182
sorry, typo
[eqn]\prod_{v \in V \setminus L} (c(v)-1)![/eqn]
Thread posts: 6
Thread images: 1
Thread images: 1