Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial problem: Directed Acyclic Graph

  1. Feb 6, 2014 #1
    How many unique landscapes exist in 5D DAG (directed acyclic graph)? There are 2^5 points (eg: 00000, 00001, ... 11111) and (2^5)! combinations.

    The problem is a combinatorial problem. It should be fun and interesting, and I am interested in discussing the solution here as well.

    It is classifying all distinct 5 dimensional landscapes. A landscape in 5-space is an assignment of edge direction to each edge between vertices such that a directed acyclic graph is formed (DAG).

    Classification might include the number of peaks, basins, or a metric like that.

    There are (2^5)! combinations so obviously iterating through each combination and testing if it is a new landscape or an orientation of an old one won't work.

    For example in the 2D case, there are (2^2)! permutations = 24. This 24 is made up of 3 landscapes. There are 8 orientations of each one.

    I am reluctant to draw a picture at first, because maybe the way you visualize it will help you find a solution.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted