雙圈圖的代數(shù)連通度的分類排序.pdf

1、設(shè) G=(V,E)是簡單連通圖，它的頂點(diǎn)集 V(G)={v1,v2,…,vn}和邊集E(G)={e1，e2,…，em}，分別用A(G)=(aij)和D(G)=diag(d1,d2,…,dn)表示圖G的鄰接矩陣和度對角矩陣，其中di表示頂點(diǎn)vi的度，當(dāng)vi和vj相鄰時(shí)aij=1，當(dāng)vi和vj不相鄰時(shí)aij=0.圖G的拉普拉斯矩陣L(G)=D(G)-A(G)，容易知道L(G)是一個(gè)半正定的實(shí)對稱奇異矩陣，把L(G)的特征值從大到小排列如下：

2、
　　λ1(G)≥λ2(G)≥…≥λn-1(G)≥λn(G)=0.
　　因?yàn)棣薾-1(G)>0當(dāng)且僅當(dāng)圖G是連通圖，所以λn-1(G)稱為圖G的代數(shù)連通度.
　　若m=n+1則稱圖G為雙圈圖.若圖中所含的兩個(gè)圈有且僅有一個(gè)公共頂點(diǎn)，則稱該圖為相切雙圈圖；若圖中所含的兩個(gè)圈沒有公共頂點(diǎn)，則稱該圖為相離雙圈圖；若圖中所含的兩個(gè)圈至少有兩個(gè)公共頂點(diǎn)，則稱該圖為相交雙圈圖.本文主要對相切雙圈圖中前六大代數(shù)連通度的圖類，相離雙圈