一類賦權(quán)圖的代數(shù)連通度.pdf

1、賦權(quán)圖的研究已經(jīng)被用來解決許多實(shí)際問題，網(wǎng)絡(luò)設(shè)計(jì)以及電路設(shè)計(jì)實(shí)際上都依賴于賦權(quán)圖.設(shè)G為一個(gè)簡(jiǎn)單圖，頂點(diǎn)集為V=fv1; v2:::vng，邊集為E=fe1; e2:::emg.設(shè)集合W=fw1;w2:::wmg，其中wi 依次遞減且wi＞0，I=1; 2:::m.定義一個(gè)函數(shù)f ：E ! W，則f 叫做賦權(quán)函數(shù).Gf=（V;E;W; f)被稱為賦權(quán)圖. Gf（W)的Laplacian 矩陣為L(zhǎng)f.Lf的特征值稱為賦權(quán)圖的Laplaci

2、an 特征值.1973年，F(xiàn)ielder 提出圖G 是連通的當(dāng)且僅當(dāng)圖G的第2個(gè)最小的Laplacian 特征值un 1＞0.因此un 1 被稱為圖G的代數(shù)連通度，記為a(G). 類似的賦權(quán)圖Gf的第2個(gè)最小的Laplacian 特征值被稱為賦權(quán)圖Gf的代數(shù)連通度.本文在此基礎(chǔ)上，通過移接變形討論了賦權(quán)圖代數(shù)連通度的變化情況. 本文主要研究了三個(gè)方面的內(nèi)容: k 正則圖如何賦權(quán)；對(duì)于k 正則圖的每個(gè)頂點(diǎn)均增加一個(gè)含有l(wèi)個(gè)點(diǎn)的集合Ni,1

3、 · l · n,I=1; 2:::n，對(duì)于Ni中的每個(gè)點(diǎn)都與vi 連一條邊. 在賦權(quán)函數(shù)f 作用下，對(duì)新圖進(jìn)行賦權(quán)，記為Hf，討論了Gf與Hf的特征多項(xiàng)式的關(guān)系；Hf 進(jìn)行移接變形后代數(shù)連通度的變化情況, 得到了具有盡可能小的代數(shù)連通度的賦權(quán)圖.本文共分為四節(jié).
　　 本文第一節(jié)是前言，介紹了賦權(quán)圖代數(shù)連通度的發(fā)展史及其已經(jīng)取得的成果.
　　 第二節(jié)介紹了文章的一些基本概念.
　　 在本文第三節(jié)中，我們首先給出

4、了perron 向量與賦權(quán)函數(shù)f的關(guān)系，得到如下主要結(jié)果：
　　 定理3.1：設(shè)Gf 是具有n(n＞3)個(gè)頂點(diǎn)m 條邊的k 正則賦權(quán)圖，則賦權(quán)函數(shù)為f(e)=w1=:::=wm(e 2 Gf ,wi＞0,I=1; 2:::m).
　　 定理3.3：設(shè)Af 是賦權(quán)圖Gf的鄰接矩陣，Lf 是賦權(quán)圖Gf的Laplacian 矩陣，對(duì)于賦權(quán)圖Gf的任意一點(diǎn)來說，賦權(quán)度是一個(gè)常數(shù)C(C＞0).如果Af的特征值為μ1; μ2:::μ

5、n，則Lf的特征值為C Μ1;C Μ2:::C Μn.
　　 定理3.4：設(shè)Gf 是一個(gè)具有n(n 2)個(gè)頂點(diǎn)的k 正則賦權(quán)圖，Hf的構(gòu)造方式如下：
　　 （1)Gf的每個(gè)頂點(diǎn)增加一個(gè)含有l(wèi)個(gè)點(diǎn)的集合Ni,1 · l · n,I=1; 2:::n.
　　 （2)對(duì)于Ni中的每個(gè)點(diǎn)都與相應(yīng)的點(diǎn)vi 連一條邊.如果f(e)=w1,e 2 Gf ,那么在Hf中，f(viNi)=w2 并且w1＞w2＞0.
　　

6、定理3.5：Hf和Gf分別是定理3.4中的賦權(quán)圖，設(shè)Paf（)是賦權(quán)圖Gf 鄰接矩陣的特征多項(xiàng)式，PLf（)是賦權(quán)圖Gf Laplacian 矩陣的特征多項(xiàng)式,PA0f（)是賦權(quán)圖Hf 鄰接矩陣的特征多項(xiàng)式，PL0f（)是賦權(quán)圖Hf Laplacian矩陣的特征多項(xiàng)式,則有:
　　 （1)PA0f（)=nkPAf（Nkw22),(2)PL0f（)=nkPLf（Nkw22Kw2).
　　 在本文第四節(jié)中，我們利用移接變形，

7、討論了賦權(quán)圖Hf和Tf的代數(shù)連通度變化情況，得到了具有盡可能小的代數(shù)連通度的賦權(quán)圖，得到如下主要結(jié)果：
　　 定理4.2：設(shè)v1，v2 是賦權(quán)圖Hf的兩個(gè)不同懸掛點(diǎn)，設(shè)v1 2 N(v0),v2 2N(v0),wv0v1=wv0v2=w2 6=a(Hf ),如果H0f=Hfnfv0v1g+fv1v2g,且新邊上的權(quán)wv1v2=wv0v2=w2 6=a(Hf ),則a(H0f ) · a(Hf ).
　　 定理4.4：在賦

8、權(quán)圖Hf中的一點(diǎn)u0 處接一條長(zhǎng)為pk的路，pk=u0u1:::uk,k 1 且路上每條邊的賦權(quán)均為w,w＞a＞0，設(shè)X 是賦權(quán)圖Hf的代數(shù)連通度af 對(duì)應(yīng)的單位特征向量，若X的分量xu0>0，則fxpkg 為正的嚴(yán)格單調(diào)上升數(shù)列.
　　 定理4.5：設(shè)X 是賦權(quán)圖Hf的代數(shù)連通度af 對(duì)應(yīng)的單位特征向量，xvi 是X 對(duì)應(yīng)于點(diǎn)vi的分量，若在點(diǎn)u0 處分別接出兩條長(zhǎng)為k和l的路，k L 1,分別記為Pk+1=u0u1:::uk

9、，Pl+1=u0v1:::vk,k L 1,且pk和pl中每條邊的權(quán)值為w2，H0f=Hfnfvl 1vlg+fukvlg, 則a(H0f ) · a(Hf )等號(hào)成立僅有可能在xu0=0 處.
　　 定理4.9：設(shè)u1,v1 是賦權(quán)樹Tf的2個(gè)懸掛頂點(diǎn)，v1 2 N(v),u1 2 N(u),wuu1=w1,wvv1=w2, w1＞w2,若T0f=Tfnfvv1g+fu1v1g，xu＞xu1＞xv＞0,則a(T0f )