劉勝久,李天瑞?,謝鵬,劉佳
(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院,四川 成都 611756;2.四川省云計算與智能技術(shù)高校重點實驗室,四川 成都 611756)
圖能量最早是由Gutman 于1978 年正式提出的[1],對圖能量的研究可溯源到二十世紀三四十年代化學(xué)家對共軛的烴類化合物總π 能量的研究.烴類化合物總π 能量可通過Huckel 分子軌道理論近似求出[2-3].圖能量定義為圖的鄰接矩陣所有特征值絕對值之和.自圖能量提出以來,圖能量受到人們極大的關(guān)注,一系列能量,如距離能量[4]、擬Laplacian能量[5]、關(guān)聯(lián)能量[6]、匹配能量[7]、Laplacian 能量[8]、無符號Laplacian 能量[9]、Von Neumann 能量[10]、距離Laplacian 能量[11]、距離無符號Laplacian 能量[11]等其他類似能量,相繼提出.
圖能量自提出以來已在理論化學(xué)及代數(shù)圖論等領(lǐng)域得到極為廣泛的應(yīng)用,一些重要研究成果相繼問世.由于大規(guī)模矩陣特征值計算極為繁瑣,對圖能量的研究更多的集中在隨機圖、正則圖、樹圖、二部圖等幾類特殊的圖中[12-14].對圖能量的改進與拓展是圖能量研究的重要內(nèi)容,一系列類似能量的提出大大豐富了圖能量的研究內(nèi)容.但這些類似能量仍未脫離鄰接矩陣特征值計算的局限,應(yīng)用范圍受限.現(xiàn)今提出的圖能量及類似能量已有數(shù)十種之多[15],對圖能量的研究已由無向圖推廣應(yīng)用到有向圖[16-17]、混合圖[18-20]等其他多種類型的圖.由于混合圖節(jié)點之間連接的復(fù)雜性,對混合圖能量的研究遠較無向圖及有向圖復(fù)雜[21-22],實際上,對圖能量的研究目前仍以對無向圖的能量研究為主,并改進后逐步推廣應(yīng)用到有向圖及混合圖等[23].
先前,本文作者從網(wǎng)絡(luò)維數(shù)[24]的視角出發(fā),提出了網(wǎng)絡(luò)能量的概念,將網(wǎng)絡(luò)能量應(yīng)用于無向圖[25]及有向圖[26],并將無向圖的網(wǎng)絡(luò)能量與傳統(tǒng)意義上的圖能量及距離能量、擬Laplacian 能量、關(guān)聯(lián)能量、匹配能量等進行對比,得出了一些有意義的結(jié)論,同時將有向圖的網(wǎng)絡(luò)能量與無向圖的網(wǎng)絡(luò)能量及有向圖的斜能量等進行對比,也得出了一些有意義的結(jié)論.本文中,我們嘗試將網(wǎng)絡(luò)能量由無向圖及有向圖推廣應(yīng)用到混合圖,并分析研究混合圖網(wǎng)絡(luò)能量的若干重要性質(zhì).
式中:λ1A(G)、λ2A(G)、λ3A(G)、…、λiA(G)、…、λnA(G)表示A(G)的各個特征值.
對無向圖G 的所有邊賦予一個方向σ,則得到一個有向圖Gσ,其斜鄰接矩陣可記為S(Gσ).有向圖Gσ中,若節(jié)點vi與vj之間存在一條有向邊,則Aij=-Aji=1,否則,Aij=Aji=0.有向圖Gσ的斜能量εS(Gσ)定義為其斜鄰接矩陣S(Gσ)的所有特征值絕對值之和,即[16]
式中:λ1S(Gσ)、λ2S(Gσ)、λ3S(Gσ)、…、λiS(Gσ)、…、λnS(Gσ)表示S(Gσ)的各個特征值.
由于對無向邊賦予一個方向有兩種不同的選擇,一個無向圖G 對應(yīng)有2m個有向圖Gσ.圖的大部分類似能量均基于矩陣特征值的計算,如距離能量、擬Laplacian 能量、關(guān)聯(lián)能量等.對大規(guī)模矩陣而言,特征值計算極為困難,使得精確的圖能量分析殊為不便,圖能量只在極少數(shù)的特殊圖中得到較為深入的分析研究.對圖能量的研究更多的是關(guān)注圖能量的上下限,如對正則圖及隨機圖能量上限的研究等.
由于傳統(tǒng)意義上的圖能量依賴于對矩陣特征值的計算,對大規(guī)模圖的應(yīng)用受限,人們嘗試從其他的途徑得到圖能量,以避免對矩陣特征值計算的低效操作.我們從網(wǎng)絡(luò)維數(shù)的視角出發(fā),提出了網(wǎng)絡(luò)能量的概念.
圖G 的網(wǎng)絡(luò)能量EN(G)定義為[23]:
圖G 的網(wǎng)絡(luò)能量EN(G)與圖G 的能量E(G)二者之間有許多類似的性質(zhì),并且存在多個共同的上限.與無向圖的分析研究類似,對無向圖G 的所有邊賦予一個方向而得到的有向圖Gσ而言,其網(wǎng)絡(luò)維數(shù)DN(Gσ)可以表述為:
圖Gσ的網(wǎng)絡(luò)能量EN(Gσ)定義如下[24]:
圖Gσ的網(wǎng)絡(luò)能量EN(Gσ)與圖G 的網(wǎng)絡(luò)能量EN(G)及圖Gσ的斜能量ε(Gσ)三者之間存在極為密切的關(guān)聯(lián).對比式(4)及式(6),可以發(fā)現(xiàn),EN(G)與EN(Gσ)二者之間有著相似的形式,可以對它們進行深入細致的分析.
混合圖M 是對無向圖G 的部分邊賦予一個方向而得到的圖.對任一混合圖M 而言,其Hermitian鄰接矩陣可記為H(M).混合圖M 中,若節(jié)點vi與vj之間存在一條有向邊,則Hij=-Hji=i;若節(jié)點vi與vj之間存在一條無向邊,則Hij=Hji=1;若節(jié)點vi與vj之間不存在任何邊,則Hij=Hji=0.混合圖M 的Hermitian 能量εH(M)定義為其Hermitian 鄰接矩陣H(M)的所有特征值絕對值之和,即[18]
式中:λ1H(M)、λ2H(M)、λ3H(M)、…、λiH(M)、…、λnH(M)表示H(M)的各個特征值.
對混合圖而言,還有Hermitian-Randic 能量[19]、Hermitian 關(guān)聯(lián)能量[20]等其他多種形式的能量.
混合圖M 的Hermitian 能量εH(M)也有很多與無向圖G 的圖能量E(G)及有向圖Gσ的斜能量εS(Gσ)等類似的上下限.
對含有n 個節(jié)點m 條邊,且原始圖中節(jié)點最大度為Δ 的混合圖M 來說,其Hermitian 能量εH(M)上下限滿足下式[18]:
對比無向圖G 的圖能量E(G)及有向圖Gσ的斜能量εS(Gσ)的上限,很顯然,混合圖的Hermitian 能量εH(M)兼具E(G)及εS(Gσ)的一些特點.
特別地,當(dāng)混合圖M 的原始圖為k-正則圖時,有
可以發(fā)現(xiàn),混合圖的Hermitian 能量具備無向圖的網(wǎng)絡(luò)能量的一些特點.
由于混合圖遠較無向圖及有向圖復(fù)雜,對混合圖能量的研究尚在持續(xù)深入,相關(guān)的研究成果并不多.
對比式(1)(2)(7)可以發(fā)現(xiàn),無向圖、有向圖、混合圖的能量計算均是通過計算矩陣的特征值而得到的,計算復(fù)雜.通過式(3)對無向圖的網(wǎng)絡(luò)維數(shù)的研究,提出了無向圖的網(wǎng)絡(luò)能量;通過式(5)對有向圖的網(wǎng)絡(luò)維數(shù)的研究,提出了有向圖的網(wǎng)絡(luò)能量.同理,對適用于無向圖及有向圖的網(wǎng)絡(luò)維數(shù)進行拓展,將網(wǎng)絡(luò)維數(shù)應(yīng)用于混合圖中,提出混合圖的網(wǎng)絡(luò)能量.
混合圖既含有無向邊,又含有有向邊,是一類介于無向圖與有向圖之間的特殊的圖.通過對式(3)中無向圖的網(wǎng)絡(luò)維數(shù)及式(5)中有向圖的網(wǎng)絡(luò)維數(shù)的研究,可以得出混合圖的網(wǎng)絡(luò)維數(shù).
混合圖M 的網(wǎng)絡(luò)維數(shù)DN(M)可以表述為:
由于混合圖M 是對無向圖G 中的部分無向邊賦予方向而得到的,若賦予有向邊的比例為r,即
式(11)可改寫為:
對式(11)進行分析,可以發(fā)現(xiàn),當(dāng)r=0 時,混合圖M 退化為無向圖G,此時,式(13)退化為式(3);當(dāng)r=1 時,混合圖M 退化為有向圖Gσ,此時,式(13)退化為式(5).即式(3)所示的無向圖的網(wǎng)絡(luò)維數(shù)及式(5)所示的有向圖的網(wǎng)絡(luò)維數(shù)分別是式(13)所示的混合圖的網(wǎng)絡(luò)維數(shù)在r=0 及r=1 時的特例.于是,通過式(13)將無向圖、有向圖、混合圖三者通過網(wǎng)絡(luò)維數(shù)聯(lián)系起來了.
觀察式(4)及式(6),可以發(fā)現(xiàn),無向圖及有向圖的網(wǎng)絡(luò)能量均是通過其對應(yīng)的網(wǎng)絡(luò)維數(shù)式(3)及式(5)得到的,對式(11)所示的混合圖的網(wǎng)絡(luò)維數(shù)進行研究,可以得到混合圖M 的網(wǎng)絡(luò)能量EN(M),如式(14)所示:
對式(14)進行分析,可以得到等價的另一表述,如式(15)所示:
對式(15)進行分析,可以發(fā)現(xiàn),當(dāng)r=0 時,混合圖M 退化為無向圖G,此時,式(15)退化為式(4);當(dāng)r=1 時,混合圖M 退化為有向圖Gσ,此時,式(15)退化為式(6).即式(4)所示的無向圖的網(wǎng)絡(luò)能量及式(6)所示的有向圖的網(wǎng)絡(luò)能量分別是式(15)所示的混合圖的網(wǎng)絡(luò)能量在r=0 及r=1 時的特例.于是,通過式(15)將無向圖、有向圖、混合圖三者通過網(wǎng)絡(luò)能量進一步聯(lián)系起來了.
式(3)(5)(13)分別給出了無向圖、有向圖、混合圖的網(wǎng)絡(luò)維數(shù),對這些公式進行分析,可以得出它們之間的關(guān)系.
對式(3)及式(5)進行分析,可以得到:
對式(3)及式(13)進行分析,可以得到:
在實際計算中,只要得到有向圖、無向圖、混合圖三者之一的網(wǎng)絡(luò)維數(shù)及混合圖中有向邊的比例r,即可得到另外二者的網(wǎng)絡(luò)維數(shù).
式(4)(6)(15)分別給出了無向圖、有向圖、混合圖的網(wǎng)絡(luò)能量,對這些公式進行分析,可以得出它們之間的關(guān)系.
對式(4)及式(6)進行分析,可以得到:
對式(4)及式(13)進行分析,可以得到:
于是,在實際計算中,只要得到有向圖、無向圖、混合圖三者之一的網(wǎng)絡(luò)能量及混合圖中有向邊的比例r 與節(jié)點數(shù)目n,即可得到另外二者的網(wǎng)絡(luò)能量.
上文中通過對無向圖及有向圖的網(wǎng)絡(luò)維數(shù)及網(wǎng)絡(luò)能量的分析研究,提出了混合圖的網(wǎng)絡(luò)能量,下面,我們對混合圖的網(wǎng)絡(luò)能量性質(zhì)進行分析研究.
定理1 混合圖M 的網(wǎng)絡(luò)能量EN(M)介于其原始圖G 的網(wǎng)絡(luò)能量EN(G)及有向圖Gσ的網(wǎng)絡(luò)能量EN(Gσ)之間,即
證 根據(jù)定義,定理1 顯然成立.定理1 得證.證畢.
根據(jù)定理,可以得出混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限不超過原始圖G 的網(wǎng)絡(luò)能量EN(G)的上限,混合圖M 的網(wǎng)絡(luò)能量EN(M)的下限不低于有向圖G 的網(wǎng)絡(luò)能量EN(Gσ)的下限,即EN(G)的上限也是EN(M)的上限,EN(Gσ)的下限也是EN(M)的下限.
式(20)取等號的條件是無向圖G、有向圖Gσ、混合圖M 均為空圖,即三者均只含有節(jié)點,不含有邊,即,此時,有
于是,可以得出如下引理.
引理1 混合圖M 的網(wǎng)絡(luò)能量EN(M)的下限為1,即
證 根據(jù)定義,引理1 顯然成立.引理1 得證.證畢.
引理1 的結(jié)論可以推廣應(yīng)用到無向圖及有向圖中.實際上,無向圖G 的網(wǎng)絡(luò)能量EN(G)及有向圖G的網(wǎng)絡(luò)能量EN(Gσ)的下限均是1.
下面,對混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限進行分析研究.
定理2 混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足式(23):
式中:n 為混合圖M 的節(jié)點數(shù)目;m 為混合圖M 的邊數(shù)目;r 為混合圖M 中有向邊的比例.
證 根據(jù)式(15)所示的混合圖網(wǎng)絡(luò)能量的表述,欲證定理2,只需證式(24)即可:
定理2 顯然成立.定理2 得證.證畢.
當(dāng)r=0 及r=1 時,定理2 的結(jié)論也可以推廣應(yīng)用到無向圖及有向圖中.由于0 定理3 混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足式(27): 式中:n 為混合圖M 的節(jié)點數(shù)目;m 為混合圖M 的邊數(shù)目;r 為混合圖M 中有向邊的比例. 證 由于2m≤n(n-1),代入式(23),定理3 顯然成立.定理3 得證.證畢. 繼續(xù)對混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限進行分析研究,可以得到EN(M)的一個更為緊致的上限. 定理4 當(dāng)(2-r)m ≥n 時,混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足式(28): 式中:n 為混合圖M 的節(jié)點數(shù)目;m 為混合圖M 的邊數(shù)目;r 為混合圖M 中有向邊的比例. 證 根據(jù)式(15)所示的混合圖網(wǎng)絡(luò)能量的表述,欲證定理4,只需證明下式即可: 當(dāng)且僅當(dāng)x=n 時,f(x)的一階導(dǎo)數(shù)f′(x)=0. 于是,有 定理4 顯然成立.定理4 得證.證畢. 當(dāng)r=0 及r=1 時,定理4 的結(jié)論同樣可以推廣應(yīng)用到無向圖及有向圖中. 下面,對正則圖進行分析研究. 定理5 當(dāng)混合圖M 的原始圖G 是k-正則圖時,混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足下式: 式中:n 為混合圖M 的節(jié)點數(shù)目;r 為混合圖M 中有向邊的比例;k 為原始圖G 中任一節(jié)點的節(jié)點度. 證 在原始圖G 中,由于G 是k-正則圖,則有kn=2m,即 將式(34)代入式(23),即有: 定理5 顯然成立.定理5 得證.證畢. 由于0 在特殊情況下,當(dāng)G≌Cn,即G 是一個環(huán)圖時,有k=2,此時,可得到如下引理. 引理2 當(dāng)混合圖M 的原始圖G 是一個環(huán)圖,即G≌Cn時,混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足下式: 證 將k=2 代入式(33),即得到式(36).引理2顯然成立.引理2 得證.證畢. 此外,當(dāng)G≌Kn,即G 是一個完全圖時,有k=n-1,此時,可得到如下引理. 引理3 當(dāng)混合圖M 的原始圖G 是一個完全圖,即G≌Kn時,混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足下式: 引理3 顯然成立.引理3 得證.證畢. 當(dāng)r=0 及r=1 時,定理5 的結(jié)論及引理2、引理3 同樣可以推廣應(yīng)用到無向圖及有向圖中. 下面對隨機圖進行分析研究. 定理6 當(dāng)混合圖M 的原始圖G 是隨機圖Gn(p)時,混合圖M 的網(wǎng)絡(luò)能量EN(M)的上限滿足下式: 式中:n 為混合圖M 的節(jié)點數(shù)目;r 為混合圖M 中有向邊的比例;p 為原始圖G 中節(jié)點對之間隨機連接的概率. 證 在原始圖G 中,由于G 是隨機圖Gn(p),則有: 將式(40)代入式(23),即有: 定理6 顯然成立.定理6 得證.證畢. 從式(41)可以看出,當(dāng)p=2/n 時,G 為一個環(huán)圖,此時,定理6 退化為引理2;當(dāng)p=1 時,G 為一個完全圖,此時,定理6 退化為引理3.即定理6 是引理2 及引理3 在一般情形下的泛化與推廣. 當(dāng)r=0 及r=1 時,定理6 的結(jié)論同樣可以推廣應(yīng)用到無向圖及有向圖中. 無向圖的圖能量定義為圖的鄰接矩陣所有特征值絕對值之和.由于無向圖的圖能量在理論化學(xué)及代數(shù)圖論中的重要價值,圖能量自提出以來受到人們極大的關(guān)注,一系列的類似能量相繼提出,并逐步推廣應(yīng)用到有向圖及混合圖等其他多種類型的圖.大多數(shù)圖的能量均是基于矩陣特征值計算得到的,如無向圖的距離能量、有向圖的斜能量、混合圖的Hermitian 能量等.由于大規(guī)模矩陣的特征值計算極為繁瑣,傳統(tǒng)意義上對圖能量的研究不便于推廣應(yīng)用到大規(guī)模圖中.網(wǎng)絡(luò)能量脫離了傳統(tǒng)意義上圖能量基于矩陣特征值計算的局限,并在無向圖及有向圖中得到較為成功的應(yīng)用.本文將應(yīng)用于無向圖及有向圖中的網(wǎng)絡(luò)能量推廣到混合圖中,論述了混合圖的網(wǎng)絡(luò)能量,并分析研究了混合圖的網(wǎng)絡(luò)能量的若干重要性質(zhì).后續(xù)工作的重點在于對特定的混合圖的網(wǎng)絡(luò)能量進行分析,并嘗試對帶權(quán)圖、無限圖、超圖等更為復(fù)雜的不同類型圖的能量進行深入研究.4 結(jié)論