home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13202 < prev    next >
Encoding:
Internet Message Format  |  1992-10-14  |  1.1 KB
  1. Path: sparky!uunet!think.com!ames!pacbell.com!network.ucsd.edu!ucsbcsl!lo-yosemite.ucsb.edu
  2. From: rodolfo@lo-yosemite.ucsb.edu (Resende)
  3. Newsgroups: sci.math
  4. Subject: isomorphic acyclic digraph problem
  5. Keywords: graph isomorphic classes combinatorial algorithms
  6. Message-ID: <6057@ucsbcsl.ucsb.edu>
  7. Date: 14 Oct 92 22:03:50 GMT
  8. Sender: root@ucsbcsl.ucsb.edu
  9. Organization: University of California, Santa Barbara
  10. Lines: 25
  11.  
  12. I would like to receive insights/references on the following problems
  13. (unlabeled partial orders)
  14.  
  15. 1)Is there a closed formula that gives the number of classes of
  16. isomorphic acyclic digraphs with n verices?
  17.  
  18. 2)How to generate a list of one diagram from each class of the question
  19. above?
  20.  
  21. 3)How to generate one diagram from a class such that each class has
  22. uniform probability of being chosen?
  23.  
  24. Example:
  25. n=3
  26. 1)I think there are 5 classes of isomorphic acyclic digraphs
  27. 2)the list
  28.  
  29. 1. * * *   2. *->* *  3. *->*    4 *->*   5. *->*->*
  30.                             ^      |
  31.                             |      v 
  32.                             *      *
  33.  
  34. Thanks in advance!
  35.  
  36. ---Rodolfo      rodolfo@cs.ucsb.edu
  37.