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

A combinatoric problem of real life.

  1. Mar 12, 2006 #1


    User Avatar

    Here is an adjacency list of a graph:


    How many direct graphs, can this graph generates?

    If cycles are not allowed, how many direct graph can we form? (The cycle is if we start from a vertex follow the dirction of every edge, we can go throught vertices not all of them and back to the original vertex we started.)

    If cycles are not allowed, there is always the existence of sink and source vertices. ( sink is a vertex all directions are point into this vertex, source is just the opposite of sink.)

    How to work out the probabiliy for every single vertex to become a source or sink.

    And thanks to the helps you guys offered me last year, I got a good mark on discrete maths. By the way, this's not my assignment. I just applying things I learned to make some tricky propositions.
    Last edited: Mar 12, 2006
  2. jcsd
  3. Mar 12, 2006 #2
    how many directed graphs? huh? would you like to reiterate the question?
    are we assuming that we can remove some of these edge or that the adjacency list is directed/unidirected?
  4. Mar 12, 2006 #3


    User Avatar

    The adjacency list is a simple graph list, has no any direction. If we add two possible dirctions to every edge, then, I think we got 2^15 directed graphs, since there are 15 unique edges.

    How about the rest of the question? I cannot figure out.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook