关联矩阵与树的关系

Relationship Between Incidence Matrix and Tree

根据图G的关联矩阵的部分性质,得出了关联矩阵与树之间的关系,即G的树的总数=|AAT|,其中A为图G的关联矩阵。另一方面,根据大子阵的边集合是G的一棵生成树当且仅当A的大子阵非退化,给出了一种快速找出任意图G中生成树的个数的求法。

According to the parts of properties of incidence matrix of graph G,the relationship between incidence matrix and tree is obtained,that is,the number of trees of G is equal to|AA^T|,in which A is the incidence matrix of graph G.On the other hand,we find a method to calculate the number of the tree of G according to the condition that the edge set is a generating tree if and only if the submatrix is non-degeneracy.