樹的代數(shù)連通度.pdf

1、在本文中,首先介紹了圖和Laplacian矩陣的一些基本概念和結(jié)果.利用代數(shù)連通度的二次型形式和瓶頸矩陣的Perron值,我們研究了當遷移或改變分支和變動一些邊的權(quán)重時樹的代數(shù)連通度的變化,得到了比過去更多的關(guān)于賦權(quán)樹的代數(shù)連通度的結(jié)論.(1)以下幾種情形時樹的代數(shù)連通度將不會增加:(a)當不含有任何特征點的分支從較小非負Fiedler值的點或從較大非正Fiedler值的點遷移到較大非負Fiedler值的點或較小非正Fiedler值的點

2、,同時這些分支中某些邊的權(quán)重可以變小;(b)將接近特征點的較大權(quán)重的邊與遠離特征點的較小權(quán)重的邊(要求接近特征點的的邊位于連接特征點與遠離特征點的路上)相交換;(c)減小某些邊的權(quán)重;(d)增加若干條新的邊.(2)以下幾種情形時樹的代數(shù)連通度將不會減小:(a)當不含有任何特征點的分支從較大非負Fiedler值的點或從較小非正Fiedler值的點遷移到較小非負Fiedler值的點或較大非正Fiedler值的點,同時這些分支中某些邊的權(quán)重可