home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11071 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  2.2 KB
  1. Path: sparky!uunet!gatech!bloom-beacon!eru.mt.luth.se!lunic!sunic!aun.uninett.no!alf.uib.no!ii.uib.no!tage
  2. From: tage@ii.uib.no (Tage Steffensen)
  3. Newsgroups: sci.math
  4. Subject: Graph Problem
  5. Keywords: Combinatorial problem, bipartite graphs.
  6. Message-ID: <1992Sep7.084511.3401@alf.uib.no>
  7. Date: 7 Sep 92 08:45:11 GMT
  8. Sender: usenet@alf.uib.no (Bergen University Newsaccount)
  9. Organization: Dept. of Informatics, University of Bergen
  10. Lines: 47
  11.  
  12. Let G = (V,U,E) be a bipartite graph such that V and U are two disjunct sets of
  13. vertices and E is a set of edges connecting vertices from V to U. 
  14.  
  15. Further make the following assumptions. 
  16.  
  17.    - each V has exactly l edges. ( l < | V | )
  18.    - |V| <= |U|. 
  19.  
  20.    - foreach subsett v of V there are at least |v| distinct vertices in U that
  21.     are connected  to the vertices in v. 
  22.  
  23.     example. V = 1, 2, 3. 
  24.          U = ( a, b, c, d )
  25.          l = 2
  26.          E = { (1a) (1b) (2c) ( 2d) ( 3b ) ( 3d ) }
  27.           v = ( 1, 3 ). We then know that 1 and 3 must be connected to at
  28.          least 2 different vertices  in U. 
  29.          
  30.                  The vertices in U that is connected to a vertice in v is (a, b, d )
  31.  
  32. A perfect matching is a matching of pairs of vertices one from V and one from U,
  33. such that all  vertices in V is matched to a vertice in U. 
  34.  
  35. The vertices can onlu be matched if there is an edge from the vertice in V to the
  36. one in U. 
  37.  
  38. A perfect matching in the example is ( 1=a, 2=c, 3=b )
  39. Other solutions will be ( 1=a, 2=c, 3=d ) ( 1=a, 2=d, 3=b ) and ( 1=b, 2=c, 3=d)
  40.  
  41. My problem is : can anything be said of the number of perfect matching in this
  42. graph given the definitions over. 
  43.  
  44. I've been trying to find a formula that will tell me how many solutions there are 
  45. to this problem. The formula should take in account the number of vertices in V, the
  46. number of vertices in U and the costant l that says how many edges there are from each
  47. V. 
  48.  
  49. If it is not possible to find such a solution is ut possible to say anything of the range
  50. of the number. example there are at least k1 matching's and no more than k1. 
  51.  
  52. Also note that we are sure that there will exist at least one matching under the
  53. given conditions. 
  54.  
  55.  
  56. -- 
  57. I der treder her inn, lat alt haap fare. 
  58. -- Oppslag over hovedfagslesesal i informatikk.  
  59.