廣義θ-圖和廣義梅花圖φ的奇異性

馬海成, 攸曉杰

(青海民族大學 數學與統計學院, 西寧 810007)

1 引言與預備知識

本文僅考慮有限無向的簡單圖. 設G是一個n階圖, 它的鄰接矩陣A(G)=(aij)n×n定義為

顯然,A(G)是一個對角線元素均為0, 其他元素為0或1的實對稱矩陣, 其特征值都是實數.A(G)的特征值也稱為圖G的特征值, 圖G的n個特征值構成的全體稱為G的譜.在圖G的譜中, 非零特征根的個數和零特征根的個數分別稱為圖G的秩和零度, 分別記為r(G)和η(G), 顯然r(G)+η(G)=n.

在化學中, 用圖可以表示一個共軛烴分子, 稱為分子的分子圖.分子圖的零度(或秩)在化學中有重要應用[1-6].例如: 圖的零度等于0是其所表示分子化學性質穩定的一個必要條件[6].Collatz等[2]提出了刻畫所有零度大于零的圖問題.如果一個圖有0特征值, 即η(G)>0, 則稱其為奇異的.文獻[2]提出的問題相當于刻畫所有奇異圖的問題, 是一個非常難的問題.為研究該問題, 已得到了零度(或秩)與圖結構之間的許多結果[7-17].

奇異圖有許多等價的定義, 一個圖是奇異的當且僅當其鄰接矩陣的核空間不是零空間; 一個圖是奇異的當且僅當以鄰接矩陣為系數矩陣的齊次線性方程組AX=0有非零解.文獻[18-22]從這個角度研究了圖的奇異性, 給出了一個圖是奇異圖的許多必要條件和充分條件.一個圖是奇異的當且僅當存在一個非零的向量X=(x1,x2,…,xn), 用該向量對圖上的點賦權, 每個點u∈V(G)滿足

(1)

圖1給出了格子圖P5×P5和完全二分圖Km,n滿足式(1)的點上的賦權, 表明格子圖P5×P5和完全二部圖Km,n(m+n≥3)都是奇異的.

圖1 格子圖P5×P5(A)和完全二部圖Km,n(m+n≥3)(B)上滿足式(1)的一種賦權Fig.1 A kind of weight that satisfy equation (1) on lattice graph P5×P5(A) and complete bipartite graph Km,n(m+n≥3) (B)

一個圖是奇異的當且僅當其鄰接矩陣是奇異的, 即其鄰接矩陣的行列式的值為零.基于此, 文獻[23-24]給出了幾類三圈圖奇異的充分必要條件和這些圖中奇異圖發生的概率.文獻[25-28]研究結果表明, 奇異圖與數學中有限群的表示理論、 組合數學、 代數幾何等均有聯系.本文考慮廣義θ-圖和廣義梅花圖φ奇異的充分必要條件, 以及其中奇異圖發生的概率.

用Pn和Cn分別表示n個點的路和圈.分別連結k條路Pa1+2,Pa2+2,…,Pak+2的起點和終點得到的圖稱為廣義θ-圖, 記為θ(a1,a2,…,ak), 這里ai≥0(i=1,2,…,k)且它們中最多有一個為0.連結k條路Pa1+1,Pa2+1,…,Pak+1的起點和終點為一個點得到的圖稱為廣義梅花圖, 記為φ(a1,a2,…,ak), 這里ai≥3(i=1,2,…,k).廣義θ-圖θ(a1,a2,…,ak)和廣義梅花圖φ(a1,a2,…,ak)如圖2所示.用G∪H表示兩個圖G和H的點不交并圖.度數為1的點稱為懸掛點, 與懸掛點相鄰接的點稱為擬懸掛點.本文未說明的記號和術語可參 見 文 獻[1].

引理2[1]設圖G有一個懸掛點,H是從圖G中刪除該懸掛點以及和它鄰接的擬懸掛點后得到的圖, 則η(G)=η(H).等價地, 圖G非奇異當且僅當圖H非奇異.

每個分支都是孤立邊或圈的圖稱為基本圖.圖G的包含所有點的基本子圖稱為圖G的基本支撐子圖.僅有孤立邊組成的基本支撐子圖稱為圖G的完美匹配.顯然, 帶有完美匹配的圖的點數一定是偶數.

引理3[1]設G是n個點的圖, 其鄰接矩陣為A(G), 則

這里H表示圖G的所有基本支撐子圖構成的集合,p(H)表示H中分支的數目,c(H)表示H中圈的數目.

2 主要結果

定理1廣義梅花圖G=φ(a1,a2,…,ak)是奇異的當且僅當下列情形之一成立:

1)G的偶長圈多于一個;

2)G恰有一個偶長的圈, 且該圈的長為4的倍數;

3)G沒有偶長的圈, 且長模4余1的圈和長模4余3的圈各占1/2.

證明: 設G=φ(a1,a2,…,ak), 圖G可能的基本支撐子圖有兩類: 一類由一個圈和一些孤立邊組成; 另一類由孤立邊組成, 即完美匹配.

1) 圖G的偶長圈多于一個, 此時圖G沒有基本支撐子圖, 由引理3知,G是奇異的.

(-1)[(a2-1)+…+(ak-1)]/2+1×2+(-1)[a1+(a2-1)+…+(ak-1)]/2×2=0,

(2)

將式(2)兩邊乘以(-1)[a1+(a2-1)+…+(ak-1)]/2, 當且僅當(-1)a1/2=1, 當且僅當a1是4的倍數.

將式(3)兩邊乘以(-1)[(a1-1)+(a2-1)+…+(ak-1)]/2, 當且僅當

(-1)(a1-1)/2+(-1)(a2-1)/2+…+(-1)(ak-1)/2=0,

當且僅當數字a1,a2,…,ak中, 模4余1和模4余3的數各占1/2.證畢.

定理2設A={a1,a2,…,ak}是一些大于等于0的整數組成的可重集, 且其中最多只有一個0, 廣義θ-圖θ(a1,a2,…,ak)是奇異的當且僅當下列情形之一成立:

1) 集合A中沒有奇數, 且模4余0和模4余2的整數各占1/2;

2) 集合A中只有1個奇數, 且其余的數中模4余0和模4余2的整數各占1/2;

3) 集合A中只有2個奇數, 且這兩個奇數關于模4同余;

4) 集合A中多于2個奇數.

證明: 設G=θ(a1,a2,…,ak), 圖G可能的基本支撐子圖有兩類: 一類由一個圈和一些孤立邊組成; 另一類由孤立邊組成, 即完美匹配.

(-1)(a3+a4+…+ak)/2+1×2+(-1)(a1+a4+…+ak)/2+1×2+…+(-1)(a1+a2+…+ak-2)/2+1×2+

(-1)[(a1+2)+a2+…+ak]/2+(-1)[a1+(a2+2)+…+ak]/2+…+(-1)[a1+a2+…+ak-1+(ak+2)]/2=0,

(4)

將式(4)兩邊乘以(-1)(a1+a2+…+ak)/2+1, 當且僅當

[(-1)(a1+a2)/2+(-1)(a1+a3)/2+…+(-1)(ak-1+ak)/2]×2+k=0,

當且僅當

當且僅當(e-f)2=0, 當且僅當e=f.

2) 集合A中只有1個奇數, 不妨設a1是奇數, 集合A中模4余0的整數有e個, 模4余2的整數有f個,e+f=k-1.圖G的基本支撐子圖只有一類, 即奇數路和其中的另一條路(包括θ的兩個端點X,Y)構成一個圈, 其余路上的點構成完美匹配, 這樣的基本支撐子圖共有(k-1)個.于是由引理3知,θ(a1,a2,…,ak)奇異當且僅當

(-1)(a3+…+ak)/2+1×2+(-1)(a2+a4+…+ak)/2+1×2+…+(-1)(a2+a3…+ak-1)/2+1×2=0,

(5)

將式(5)兩邊乘以(-1)(a2+…+ak)/2+1, 當且僅當

(-1)a2/2+(-1)a3/2+…+(-1)ak/2=0,

當且僅當數字a2,a3,…,ak中模4余0和模4余2的整數各占1/2.

(-1)(a3+…+ak)/2+1×2+(-1)[(a1+1)+(a2+1)+a3+…+ak]/2×2=0,

(6)

將式(6)兩邊乘以(-1)[(a1+1)+(a2+1)+a3+…+ak]/2, 當且僅當(-1)(a1+a2)/2+1=0, 當且僅當數字a1,a2模4同余.

4) 集合A中多于2個奇數.此時圖G沒有基本支撐子圖, 由引理3知, 圖G是奇異的.證畢.

定理3設隨機給定一個圖G=φ(a1,a2,…,ak)是奇異圖的概率為p, 則

證畢.

定理4設隨機給定一個圖G=θ(a1,a2,…,ak)是奇異圖的概率為p, 則

于是由定理2知,

證畢.

文獻[25]給出了單圈圖、 雙圈圖以及部分三圈圖奇異的判別方法, 如一個圈Cn是奇異的當且僅當4|n.圖θ(a1,a2,…,ak)(或φ(a1,a2,…,ak))的某些點上長出一些樹, 即若干棵樹上的根點和圖θ(a1,a2,…,ak)(或φ(a1,a2,…,ak))上的某些點粘結后得到的圖的集合記為T(θ)(或T(φ)), 重復使用引理2, 即刪除圖上的懸掛點和擬懸掛點, 利用定理1、 定理2、 引理1和引理2, 可以確定T(θ)(或T(φ))中的奇異圖.