首页 > 代码库 > 矩阵树定理速证
矩阵树定理速证
凯莱公式:
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
矩阵树定理速证
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。