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

馬海成, 攸曉杰

(青海民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 西寧 810007)

1 引言與預(yù)備知識

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

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

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

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

(1)

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

圖1 格子圖P5×P5(A)和完全二部圖Km,n(m+n≥3)(B)上滿足式(1)的一種賦權(quán)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)

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

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

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

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

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

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

2 主要結(jié)果

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

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

2)G恰有一個(gè)偶長的圈, 且該圈的長為4的倍數(shù);

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

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

1) 圖G的偶長圈多于一個(gè), 此時(shí)圖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, 當(dāng)且僅當(dāng)(-1)a1/2=1, 當(dāng)且僅當(dāng)a1是4的倍數(shù).

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

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

當(dāng)且僅當(dāng)數(shù)字a1,a2,…,ak中, 模4余1和模4余3的數(shù)各占1/2.證畢.

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

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

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

3) 集合A中只有2個(gè)奇數(shù), 且這兩個(gè)奇數(shù)關(guān)于模4同余;

4) 集合A中多于2個(gè)奇數(shù).

證明: 設(shè)G=θ(a1,a2,…,ak), 圖G可能的基本支撐子圖有兩類: 一類由一個(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, 當(dāng)且僅當(dāng)

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

當(dāng)且僅當(dāng)

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

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

(-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, 當(dāng)且僅當(dāng)

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

當(dāng)且僅當(dāng)數(shù)字a2,a3,…,ak中模4余0和模4余2的整數(shù)各占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, 當(dāng)且僅當(dāng)(-1)(a1+a2)/2+1=0, 當(dāng)且僅當(dāng)數(shù)字a1,a2模4同余.

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

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

證畢.

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

于是由定理2知,

證畢.

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