home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1788 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  1.4 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!mojo.eng.umd.edu!disney.src.umd.edu!eng.umd.edu!clin
  2. From: clin@eng.umd.edu (Charles Lin)
  3. Newsgroups: comp.theory
  4. Subject: Round robin problem
  5. Message-ID: <1992Aug20.170241.22798@src.umd.edu>
  6. Date: 20 Aug 92 17:02:41 GMT
  7. Sender: news@src.umd.edu (C-News)
  8. Reply-To: clin@eng.umd.edu (Charles C. Lin)
  9. Organization: College of Engineering, Maryversity of Uniland, College Park
  10. Lines: 34
  11.  
  12.  
  13.    Sorry, if this is the wrong place to post.
  14.  
  15.    Anyone know of a solution to the following problem:
  16.  
  17.    Given a complete graph of n nodes (vertices) where n is even, 
  18. and given n - 1 colors, color the edges so that:
  19.  
  20.    (1) each vertex has at least one edge with each of the n - 1
  21.        colors
  22.  
  23. which by definition of a complete graph implies
  24.  
  25.    (2) each vertex has at most one edge with each of the n - 1
  26.        colors.
  27.  
  28.    Basically all colors touch each vertex once and only once.
  29.  
  30.    This can also be restated as a round robin problem where
  31. there are n (n, even) players playing a tournament.  Every
  32. day, one match is played.  Every player plays every day, and
  33. must play every other player once.  Hence, it takes n - 1
  34. days to play this.
  35.  
  36.     I have a solution to this, but I want to know if there
  37. are references to previous solutions of this problem and
  38. more importantly, the complexity.
  39.  
  40.     E-mail preferred, but I will read this newsgroup as
  41. well.   Thanks in advance.
  42.  
  43. --
  44. Charles Lin
  45. clin@eng.umd.edu
  46.