| In graph theory, bipartite graph can be modeled as searching job. resource allocation, time allocation, making spouse and other issues, which is a very useful graph theory modeling tools. This paper studies perfect matchings in the bipartite graphs, for there is classical theory and algorithms finding out the maximum matching in bipartite graphs. However, finding out all perfect matchings in bipartite graphs is still little studied. In fact, the classical algorithm can find a perfect match, but finding out all perfect matchings, which can apply a variety of distribution options for policy-makers. will be more meaningful.In this paper, the problem is transformed into counting of forbidden permutations, then it is converted into operation of0-1matrix. For a given matrix A=(a(?). we define per(A)=Σa1/1a2/2...am.The value of per(A) is exactly the number offorbidden permut-ations and perfect matchings in corresponding bipartite graph. By analogying determinant, we studied the elementary arithmetic transformation properties as well as recurrence properties, then get proper calculating method of per(A) which gives the number of perfect matchings and generation algorithm of all perfect matchings. In this way, we get servel well-known counting problems. In particular, the number of all all perfect matchings in3-regular circulant bipartite graphs G(n) is Fn+Fn-2+2.In addition, the paper also studied two generalized problems of derangement, one of them is the number of1-factor in complete directed graphs which does not contain cycle with length k, the other is the number of mappings which does not contain k-fixed points. By using the generating function method, we derived the exponential generating functions of these two problems, resulting in their counting formulas and recursive formulas.The number of1-factor in complete directed graphs which does not contain cycle If k is a prime, then the number of mappings which does not contain k-fixed points... |
PDF Full Text Request