二部图生成树的新的计数公式(英文)

New Enumeration Formula of Spanning Trees in A Bipartite Graph

设G =(V ,U ,E)是一个连通的二部图 ,其中｜V｜=m ,｜U｜=n .令M (G)表示G的关联矩阵 ,Jk×s 表示元素全为 1的k ×s矩阵 ,R =M (G)M (G)′ , Jm +n =Jm -Jm×n-Jn×m Jn,t(G)表示G中生成树的个数 .在本文中我们不用对G的边定向而获得了下面的主要结论 :t(G) =(m +n) -2 det( Jm +n+R) .

Let G=(V,U,E) be a connected bipartite graph in which |V|=m and |U|=n, M(G) the incidence matrix of G,R=M(G)M(G)′,J k×s denote the k×s matrix of all 1's, m+n =J m-J m×n -J n×m J n and t(G) denote the number of spanning trees in G. In this paper, without orientation for G, we obtain the following main result t(G)=(m+n) -2 det( m+n +R)