摘要
本文提出了对给定图 G来说 ,计算它的所有的生成树棵数的一种方法 ,即由 Cayley定理与 Binet-Cauchy定理来推导一个公式τ(G) =det(KKT) ,为了证明此公式的成立 ,还证明了从一个图的完全关联矩阵 M(G)中删去任意一行后 ,得到的矩阵 K和 K的转置 KT满足 Binet-Cauchy条件。公式τ(G) =det(KKT)的证明是由一个图的生成树的棵数公式τ(G) =τ(G -e) +τ(G . e)与具有以上性质的矩阵 K与 KT且 det(KKT) =∑ Ki Ki=∑K2i 合起来证明。
This paper puts forward a method that camputate all spanning trees of a graph G.It is formula:τ(G)=det(KK Τ),which is derived by Cayley theorem and Binet Cauchy theorem.In order to prove the formula,we bear out Matris K,which is obtained by means of deleting any row form a graphs chcidence matris M(G) and its transposed matrix K T satisfied Binet Cauchy condition The proof of the formula τ(G)=det(KK T)is obtained by means of the formula τ(G)=τ(G-e)+τ(Ge),which is a formala about computing quantities about a graphs spanning trees,and matrix K and K T which possess the above mentioned properties,and the formula det(KK T)=ZK iK i=ZK 2 i
出处
《新疆师范大学学报（自然科学版）》
2004年第4期41-44,共4页
Journal of Xinjiang Normal University(Natural Sciences Edition)
