Author |
Topic: Counting Graphs (Read 539 times) |
|
vphan
Guest
|
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?
|
|
 IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender: 
Posts: 1884
|
 |
Re: Counting Graphs
« Reply #1 on: Jul 6th, 2004, 7:21pm » |
 Quote  Modify
|
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 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. But probably in a while to help miss your deadline.
|
| « Last Edit: Jul 6th, 2004, 7:23pm by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Counting Graphs
« Reply #2 on: Jul 27th, 2004, 5:49am » |
Quote Modify
|
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 Ak corresponds to the number of paths of length k from node i to node j.
2) (I - A)-1 = I + A + A2 + ...
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).
|
| « Last Edit: Jul 27th, 2004, 5:51am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove