论文摘要
在本文中,首先介绍了图和Laplacian矩阵的一些基本概念和结果.利用代数连通度的二次型形式和瓶颈矩阵的Perron值,我们研究了当迁移或改变分支和变动一些边的权重时树的代数连通度的变化,得到了比过去更多的关于赋权树的代数连通度的结论.(1)以下几种情形时树的代数连通度将不会增加: (a)当不含有任何特征点的分支从较小非负Fiedler值的点或从较大非正Fiedler值的点迁移到较大非负Fiedler值的点或较小非正Fiedler值的点,同时这些分支中某些边的权重可以变小; (b)将接近特征点的较大权重的边与远离特征点的较小权重的边(要求接近特征点的的边位于连接特征点与远离特征点的路上)相交换; (c)减小某些边的权重; (d)增加若干条新的边.(2)以下几种情形时树的代数连通度将不会减小: (a)当不含有任何特征点的分支从较大非负Fiedler值的点或从较小非正Fiedler值的点迁移到较小非负Fiedler值的点或较大非正Fiedler值的点,同时这些分支中某些边的权重可以变大; (b)将接近特征点的较小权重的边与远离特征点的较大权重的边(要求接近特征点的的边位于连接特征点与远离特征点的路上)相交换; (c)增加某些边的权重; (d)删除掉若干条边.