wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Counting Graphs
        
(Message started by: vphan on Jul 6^th, 2004, 12:01pm)

Title: Counting Graphs
Post by vphan on Jul 6^th, 2004, 12:01pm

hello all,

Any ideas to the following problem?

how many acyclic directed graphs with n vertices are there?

how many of them are also transitive closures?

Any ideas?

Title: Re: Counting Graphs
Post by Noke Lieu on Jul 6^th, 2004, 7:21pm

How's the course going?
There was just something about the way you asked that this seems like homework.

Sadly, I am of no help here whatsoever. I'd trawl through mathworld (http://mathworld.wolfram.com/AcyclicDigraph.html) until I felt I understood what the question was asking, and by then one of the seriously clever inhabitants here would come and do a far better job than I ever could.

Hold tight, the answer will come. [hide]But probably in a while to help miss your deadline.[/hide]

Title: Re: Counting Graphs
Post by william wu on Jul 27^th, 2004, 5:49am

I have to return to my homework soon, but for the first question, here's a possible approach ...

Note that we can represent any graph as a 0-1 adjacency matrix A, where entry (i,j) is 1 if there is a directed edge from i to j, and 0 otherwise. (For undirected graphs, the adjacency matrix is symmetric.) Then here are some facts:

1) Entry (i,j) in A^k corresponds to the number of paths of length k from node i to node j.

2) (I - A)^-1 = I + A + A² + ...

Combining 1) and 2), we see that (I-A) is invertible iff there are no cycles in the graph. (Recognize that if there is a cycle containing nodes i and j, then there are paths of every possible length from i to j.)

Then, to find the number of acyclic directed graphs with n vertices, one could count the number of distinct 0-1 matrices "A" such that (I - A) is invertible. Not sure if this is feasible, but seems easier to think about for me than the original problem. Also, this assumes you are counting labeled graphs; otherwise you will have to count classes of similar matrices (isomorphic graphs).