国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

圖的高階譜矩公式

2022-12-22 13:14:48周理泳薛振宇吳亞平
湖北工程學(xué)院學(xué)報 2022年6期
關(guān)鍵詞:條邊邊數(shù)條數(shù)

周理泳,薛振宇,吳亞平

(江漢大學(xué) 人工智能學(xué)院,湖北 武漢 430056)

圖的譜理論是代數(shù)圖論的一個重要研究領(lǐng)域[1],其研究的主要途徑是,通過圖的矩陣表示,建立圖的拓撲結(jié)構(gòu)和圖的矩陣表示的相似不變量之間的聯(lián)系,從而刻畫圖的結(jié)構(gòu)特征。

1987年,Cvetkovíc和Rowlinson[2]給出了圖的前4階譜矩的計算公式。文獻[3-5]給出圖的前8階譜矩的計算公式。吳亞平等[6]給出單圈圖前10階譜矩計算公式。Chen等[7]研究隨機圖的譜矩,基于Erd?s-Rényi模型,給出圖譜矩公式的精確估計。依據(jù)譜矩序?qū)D類的排序吸引了許多研究者的興趣,參看文獻[8-14]。章麗麗[15]借助于譜矩,求圖中某些子圖的個數(shù)。本文將給出任意簡單圖第9階譜矩計算公式。我們相信有了第9階譜矩的計算公式,圖類依據(jù)譜矩序排序又能往前推進一大步。

1 預(yù)備知識

本文只考慮簡單圖,文中出現(xiàn)而未介紹的定義參照文獻[1]。設(shè)G=(V(G),E(G)),其中V(G)表示G的頂點集,E(G)表示G的邊集,稱G是一個|V(G)|-階圖。若G中由頂點和邊構(gòu)成的一個交替序列v0e1v1e2v2…vm-1emvm滿足邊ei的兩個端點為vi-1和vi,i=1,…,m,稱此序列為G的一條(v0,vm)-途徑。若v0=vm,則稱它是一條閉途徑。

雙圈圖具有兩種類型的基圖(見圖1)。記B(p,l,q)是通過在2個點不交圈Cp和Cq之間連一條長為l-1(l≥1)的路v1v2…vl-1vl得到的圖,其中v1∈V(Cp),vl∈V(Cq)。特別地,B(p,1,q)將Cp和Cq中的兩個頂點粘合在一起得到的圖。將3條兩兩內(nèi)部不交的路Pp,Pq,Pr對應(yīng)的端點粘合在一起構(gòu)成的圖記為P(p,q,r)。

圖1 雙圈圖的基圖

圖2 三圈圖的基圖

當一條長為k的閉途徑W經(jīng)過圖H每條邊至少一次時,我們稱圖H能生成閉途徑W。用記號?G(H)表示G中H子圖的個數(shù),在不引起混淆情況下,用記號?(H)表示。

下面給出在證明主要結(jié)論時用到的幾個引理。

引理1[2]圖G的第k階譜矩等于G中長為k的閉途徑的條數(shù)。

引理2[6]二部圖只能生成長為偶數(shù)的閉途徑。

根據(jù)引理3,我們能得到下面推論。

推論1 令H是m圈圖。若它能生成一條長為奇數(shù)k的閉途徑W, 則|E(H)|≤k,等號成立當且僅當H是一個歐拉圖。

推論2 若連通圖G中恰有2個奇度點,且2個奇度點相鄰,則G生成最短閉途徑長度為|E(G)|+1。

證明設(shè)G中2個奇度點為u,v,令G′=G+uv,可知G′是歐拉圖。根據(jù)推論1,G′生成最短閉途徑長為|E(G′)|=|E(G)|+1。 由于G不是歐拉圖,則G生成閉途徑長度大于|E(G)|。故G生成最短閉途徑長度為|E(G)|+1。

推論3 若連通圖G中恰有4個奇度點u1,u2,u3,u4,且u1u2?E(G),u3u4?E(G),則G生成最短閉途徑長度為|E(G)|+2。

證明令G′=G+u1u2+u3u4,可知G′是歐拉圖。類似于推論2證明,G生成最短閉途徑長度為|E(G)|+2。

2 本文的主要結(jié)果

定理1 能生成長為9的閉途徑子圖為C3,C5,C7,C9,K4,H1,…,H46,B(3,1,3),B(3,1,4),B(3,1,6),B(3,2,6),B(4,2,5),B(4,3,5),P(3,2,3),P(3,2,4),P(3,2,5),P(4,2,5) (見圖3)。

證明樹子圖、偶圈C4,C6,C8及分別以C4,C6,C8為基圈的單圈圖,它們都是二部圖。根據(jù)引理2,它們都不能生成長為9的閉途徑。因此能生成長為9的閉途徑子圖一定含奇圈Ct,t∈{3,5,7,9}。K4是階數(shù)最小三圈圖,K5是階數(shù)最小六圈圖(其邊數(shù)是10),因此能生成長為9的閉途徑子圖一定是m圈圖,m=1,2,3,4,5。下面分成5種情形來討論。

情形1 生成長為9的閉途徑子圖是單圈圖。

根據(jù)文獻[6]中定理1.生成長為9的閉途徑單圈子圖是C3,C5,C7,C9,H1,...,H17。

情形2 生成長為9的閉途徑子圖是雙圈圖。

首先考慮雙圈圖不含懸掛樹的情形。根據(jù)推論1,基圖邊數(shù)不超過9。

首先設(shè)雙圈圖為B(p,l,q),這里q≥p≥3,l≥1??芍獆E(B(p,l,q))|=p+q+l-1≥6,且p+q+l≤10。若(p,q)=(3,3),則子圖為B(3,1,3),B(3,2,3),B(3,3,3),B(3,4,3)。若(p,q)=(3,4),則子圖為B(3,1,4),B(3,2,4),B(3,3,4)。若(p,q)=(3,5), 則子圖為B(3,1,5),B(3,2,5)。若(p,q)=(3,6), 則子圖為B(3,1,6)。若(p,q)=(4,5), 則子圖為B(4,1,5)。根據(jù)推論1,可知B(3,4,3),B(3,3,4),B(3,2,5)都不能生成長為9的閉途徑; 通過計算子圖鄰接矩陣9次冪的跡,可知B(3,2,3),B(3,3,3),B(3,1,5)生成長為9的閉途徑條數(shù)都是0。

下面設(shè)雙圈圖為P(p,q,r),這里r≥p≥q≥2??芍獆E(P(p,q,r))|=p+q+r-3≥5,且p+q+r≤12。若(p,q,r)=(3,2,3),則子圖為P(3,2,3);若(p,q,r)=(3,2,4),則子圖為P(3,2,4);若(p,q,r)=(3,2,5),則子圖為P(3,2,5);若(p,q,r)=(3,2,6),則子圖為P(3,2,6)。若(p,q,r)=(4,2,4),則子圖為P(4,2,4);若(p,q,r)=(4,2,5),則子圖為P(4,2,5);若(p,q,r)=(4,2,6),則子圖為P(4,2,6)。若(p,q,r)=(5,2,5),則子圖為P(5,2,5)。若(p,q,r)=(3,3,3),則子圖為P(3,3,3);若(p,q,r)=(3,3,4),則子圖為P(3,3,4);若(p,q,r)=(3,3,5),則子圖為P(3,3,5);若(p,q,r)=(3,3,6),則子圖為P(3,3,6)。若(p,q,r)=(4,3,4),則子圖為P(4,3,4);若(p,q,r)=(4,3,5),則子圖為P(4,3,5)。 根據(jù)推論1,可知P(4,2,6),P(5,2,5),P(3,3,6),P(4,3,5)都不能生成長為9的閉途徑;通過計算子圖鄰接矩陣9次冪的跡,可知P(4,2,4),P(3,3,3),P(3,3,5),P(4,3,4)生成長為9的閉途徑條數(shù)都是0。

下面考慮雙圈圖含懸掛樹的情形。則基圖的邊數(shù)只能是5、6或7。

基圖的邊數(shù)為5?;鶊D只能是P(3,2,3)。根據(jù)引理3, 它所有懸掛樹邊數(shù)和為1或2。若所有懸掛樹邊數(shù)和為1,此時圖為H18,H19。若所有懸掛樹邊數(shù)和為2,由于P(3,2,3)不是歐拉圖,根據(jù)引理3,此時圖生成長為9的閉途徑條數(shù)都是0。

基圖的邊數(shù)為6?;鶊D為P(3,2,4)或B(3,1,3)。根據(jù)引理3, 它們所有懸掛樹邊數(shù)和為1。P(3,2,4)與一個懸掛樹P2有3種不同粘合方式,依次得到圖H20,H21,H22。B(3,1,3)與一個懸掛樹P2有2種不同粘合方式,經(jīng)計算粘合后圖的鄰接矩陣9次冪的跡都是0。

基圖邊數(shù)等于7?;鶊D為B(3,2,3),B(3,1,4),P(3,3,4),P(3,2,5)。根據(jù)引理3, 它們所有懸掛樹邊數(shù)和為1,且要生成長為9的閉途徑,這些基圖必須是歐拉圖。只有B(3,1,4)是歐拉圖,B(3,1,4)與一個懸掛樹P2有4種不同粘合方式,依次得到圖H23,H24,H25,H26。

圖3 所有能生成長為9的閉途徑子圖

情形3 生成長為9的閉途徑子圖是三圈圖。

當{p,q,r}={1,2,2},h=2時,圖為H35;當{p,q,r}={1,2,2},h=3時,圖為H36;當{p,q,r}={2,2,2},h=2時,圖為H37;當{p,q,r}={1,2,3},h=2時,圖為H38。

當{p,q,r}={1,2,2},h=1時,圖為K4;當{p,q,r}={1,2,2},h=2時,圖同構(gòu)H39;當{p,q,r}={1,2,3},h=1時,圖為H40;當{p,q,r}={2,2,2},h=1時,圖為H41。

下面考慮三圈圖含懸掛樹的情形。則基圖的邊數(shù)只能是6或7。只有三圈圖H31,H35,H39,H40,H41,K4符合條件基圖?;鶊DH31,根據(jù)引理3,所有懸掛樹邊數(shù)和恰為1。此時有1種不同方式粘懸掛樹,得到圖分別為H42,H43。H35,H39,H40,H41它們都不是歐拉圖,根據(jù)引理3,以它們?yōu)榛鶊D的三圈圖都不能生成長為9的閉途徑。K4為基圖的三圈圖生成長為8,10,…的閉途徑。

情形4 生成長為9的閉途徑子圖是四圈圖。

當四圈圖頂點數(shù)是5時,它的邊數(shù)5+4-1=8即從K5中刪除2條邊。首先考慮這2條邊是一個最大匹配。通過計算可知,該圖生成0條長為9的閉途徑。再考慮2條邊不是最大匹配的情形,得到圖H44。 當四圈圖頂點數(shù)是6時,它的邊數(shù)6+4-1=9。即從K6中刪除6條邊,根據(jù)引理3,這個圖必須是歐拉圖??芍獔D度序列為(4,4,4,2,2,2)。若有2個4度點不相鄰,則它們與其余4個點都相鄰,這時我們得到4個2度點,與度序列為(4,4,4,2,2,2)矛盾。因此3個4度點兩兩相鄰。同理可證3個2度點是獨立集合,此時圖為H45。

情形5 生成長為9的閉途徑子圖是五圈圖。

從K5中刪除1條邊,得到階數(shù)最小五圈圖。這個圖度序列為(4,4,4,3,3),可知它不是歐拉圖。根據(jù)推論1,五圈圖生成長為9的閉途徑條數(shù)都是0。

綜上所述,定理1證畢。

下面我們給出9階譜矩的計算公式。首先我們設(shè)計了基于深度優(yōu)先的搜索算法,利用該算法求解對于任意給定一個子圖,由這個子圖生成長為k的不同閉途徑條數(shù)。這個算法為我們得到任意階譜矩公式提供一種可能。算法代碼,參看鏈接http://qr61.cn/oK6EzX/q3CuHpU。

任意階譜矩,只要能找到所有能生成階閉途徑的子圖,用上述算法就能找到階譜矩的公式。假設(shè)G中能生成長為k的閉途徑所有子圖為H1,…,Ht,我們能用算法確定每個子圖生成長為k的比途徑條數(shù)為Ci,則k階譜矩

Sk(G)=c1φ(H1)+…+ctφ(Ht),c1,…,ct∈Z+。

定理2 設(shè)G是n階圖,則

S9(G)=510φ(C3)+360φ(C5)+126φ(C7)+18φ(C9)+522φ(H1)+144φ(H2)+360φ(H3)+

18φ(H4)+36φ(H5)+108φ(H6)+36φ(H7)+180φ(H8)+36φ(H9)+18φ(H10)+18φ(H11)+144φ(H12)+18φ(H13)+36φ(H14)+18φ(H15)+18φ(H16)+18φ(H17)+288φ(H18)+216φ(H19)+

54φ(H20)+108φ(H21)+54φ(H22)+36φ(H23)+36φ(H24)+36φ(H25)+72φ(H26)+144φ(H27)+

72φ(H28)+216φ(H29)+108φ(H30)+1656φ(H31)+

108φ(H32)+108φ(H33)+108φ(H34)+324φ(H35)+

144φ(H36)+144φ(H37)+144φ(H38)+1872φ(K4)+

396φ(H39)+396φ(H40)+396φ(H41)+108φ(H42)+

216φ(H43)+3964φ(H44)+2884φ(H45)+ 288φ(B(3,1,3))+396φ(B(3,1,4))+36φ(B(3,1,6))+36φ(B(3,2,4))+72φ(P(3,2,6))+36φ(B(4,1,5))+144φ(B(4,3,5))+1584φ(P(3,2,3))+666φ(P(3,2,4))+72φ(P(3,2,5))+54φ(P(4,2,5))

證明由定理1知,生成長為9的閉途徑子圖C3,C5,C7,C9,K4,H1,…,H45,B(3,1,3),B(3,1,4),

B(3,1,6),B(3,2,6),B(4,2,5),B(4,3,5),P(3,2,3),

P(3,2,4),P(3,2,5),P(4,2,5)。根據(jù)算法,我們得到9階譜矩計算公式。故定理2成立。

猜你喜歡
條邊邊數(shù)條數(shù)
多邊形內(nèi)角和、外角和定理專練
圖的Biharmonic指數(shù)的研究
2018年第2期答案
巧算金魚條數(shù)
西江邊數(shù)大船
歌海(2016年3期)2016-08-25 09:07:22
人民網(wǎng)、新華網(wǎng)、中國非公企業(yè)黨建網(wǎng)兩新黨建報道條數(shù)排行
對多邊形對角線條數(shù)的探究
每只小貓給了貓媽媽幾條魚
認識平面圖形
最大度為10的邊染色臨界圖邊數(shù)的新下界
404 Not Found

404 Not Found


nginx
赫章县| 孟连| 隆回县| 西安市| 阳西县| 秭归县| 铅山县| 莫力| 灌阳县| 河西区| 洪湖市| 昭通市| 富阳市| 昆明市| 出国| 富锦市| 惠州市| 墨竹工卡县| 汨罗市| 兴海县| 武宣县| 隆德县| 红原县| 南丹县| 邵阳市| 滨海县| 新竹县| 衡阳县| 娱乐| 玉林市| 阿鲁科尔沁旗| 城步| 来安县| 资兴市| 玛多县| 龙岩市| 苗栗市| 阿拉善右旗| 永登县| 保定市| 鄂伦春自治旗|