首页 > 代码库 > 矩阵树定理速证

矩阵树定理速证


凯莱公式:

spanning_trees_num( G ) = spanning_trees_num( G - e ) + spanning_trees_num( G · e )


矩阵树定理:

G 相应的拉普拉斯矩阵(度矩阵 - 邻接矩阵)L( G )  

删除随意一行一列得到的行列式的值det( L*( G ) )

即生成树的个数,即spanning_trees_num( G ) = det( L*( G ) )


证:

归纳如果 spanning_trees_num( G - e ) = det( L*( G - e ) )

spanning_trees_num( G · e ) = det( L*( G · e ) )

目的就是仅仅须要证 det( L*( G · e ) ) + det( L*( G - e ) ) = det( L*( G ) )

能够重标记顶点。取第一个点和第二个点之间的边做实验。能够得到例如以下矩阵

(易证删除第一行第一列的行列式值加起来相等,不废话,盯图看一会儿就明了了)

技术分享


import networkx as nx
import matplotlib.pyplot as mpl

graph = nx.Graph()
graph.add_nodes_from( range( 4 ) )
graph.add_edge( 0, 1 )
graph.add_edge( 1, 2 )
graph.add_edge( 2, 3 )
graph.add_edge( 3, 0 )
graph.add_edge( 0, 2 )

nx.draw( graph )  
mpl.show()

生成图:

技术分享


其 det( L*( G ) ):

import numpy as np

M = nx.to_numpy_matrix( graph )
A = np.asarray( M )
I = np.identity( A.shape[0] )
D = I * np.sum( A, axis = 1 )
L = D - A
L_ = L[ 1:, 1: ]
print np.linalg.det( L_ )

为 8




矩阵树定理速证