劉勝久，李天瑞?，謝鵬，劉佳

（1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 611756；2.四川省云計算與智能技術(shù)高校重點實驗室，四川 成都 611756）

圖能量最早是由Gutman 于1978 年正式提出的[1]，對圖能量的研究可溯源到二十世紀(jì)三四十年代化學(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ī)模矩陣特征值計算極為繁瑣，對圖能量的研究更多的集中在隨機(jī)圖、正則圖、樹圖、二部圖等幾類特殊的圖中[12-14].對圖能量的改進(jìn)與拓展是圖能量研究的重要內(nèi)容，一系列類似能量的提出大大豐富了圖能量的研究內(nèi)容.但這些類似能量仍未脫離鄰接矩陣特征值計算的局限，應(yīng)用范圍受限.現(xiàn)今提出的圖能量及類似能量已有數(shù)十種之多[15]，對圖能量的研究已由無向圖推廣應(yīng)用到有向圖[16-17]、混合圖[18-20]等其他多種類型的圖.由于混合圖節(jié)點之間連接的復(fù)雜性，對混合圖能量的研究遠(yuǎn)較無向圖及有向圖復(fù)雜[21-22]，實際上，對圖能量的研究目前仍以對無向圖的能量研究為主，并改進(jìn)后逐步推廣應(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)能量、匹配能量等進(jìn)行對比，得出了一些有意義的結(jié)論，同時將有向圖的網(wǎng)絡(luò)能量與無向圖的網(wǎng)絡(luò)能量及有向圖的斜能量等進(jìn)行對比，也得出了一些有意義的結(jié)論.本文中，我們嘗試將網(wǎng)絡(luò)能量由無向圖及有向圖推廣應(yīng)用到混合圖，并分析研究混合圖網(wǎng)絡(luò)能量的若干重要性質(zhì).

1 預(yù)備知識

1.1 圖能量

式中：λ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)注圖能量的上下限，如對正則圖及隨機(jī)圖能量上限的研究等.

1.2 網(wǎng)絡(luò)能量

由于傳統(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σ）二者之間有著相似的形式，可以對它們進(jìn)行深入細(xì)致的分析.

1.3 混合圖

混合圖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ò)能量的一些特點.

由于混合圖遠(yuǎn)較無向圖及有向圖復(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ù)進(jìn)行拓展，將網(wǎng)絡(luò)維數(shù)應(yīng)用于混合圖中，提出混合圖的網(wǎng)絡(luò)能量.

2 混合圖的網(wǎng)絡(luò)能量研究

2.1 混合圖的網(wǎng)絡(luò)維數(shù)

混合圖既含有無向邊，又含有有向邊，是一類介于無向圖與有向圖之間的特殊的圖.通過對式（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）進(jìn)行分析，可以發(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)系起來了.

2.2 混合圖的網(wǎng)絡(luò)能量

觀察式（4）及式（6），可以發(fā)現(xiàn)，無向圖及有向圖的網(wǎng)絡(luò)能量均是通過其對應(yīng)的網(wǎng)絡(luò)維數(shù)式（3）及式（5）得到的，對式（11）所示的混合圖的網(wǎng)絡(luò)維數(shù)進(jìn)行研究，可以得到混合圖M 的網(wǎng)絡(luò)能量EN（M），如式（14）所示：

對式（14）進(jìn)行分析，可以得到等價的另一表述，如式（15）所示：

對式（15）進(jìn)行分析，可以發(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ò)能量進(jìn)一步聯(lián)系起來了.

2.3 不同類型圖的網(wǎng)絡(luò)能量

式（3）（5）（13）分別給出了無向圖、有向圖、混合圖的網(wǎng)絡(luò)維數(shù)，對這些公式進(jìn)行分析，可以得出它們之間的關(guān)系.

對式（3）及式（5）進(jìn)行分析，可以得到：

對式（3）及式（13）進(jìn)行分析，可以得到：

在實際計算中，只要得到有向圖、無向圖、混合圖三者之一的網(wǎng)絡(luò)維數(shù)及混合圖中有向邊的比例r，即可得到另外二者的網(wǎng)絡(luò)維數(shù).

式（4）（6）（15）分別給出了無向圖、有向圖、混合圖的網(wǎng)絡(luò)能量，對這些公式進(jìn)行分析，可以得出它們之間的關(guān)系.

對式（4）及式（6）進(jìn)行分析，可以得到：

對式（4）及式（13）進(jìn)行分析，可以得到：

于是，在實際計算中，只要得到有向圖、無向圖、混合圖三者之一的網(wǎng)絡(luò)能量及混合圖中有向邊的比例r 與節(jié)點數(shù)目n，即可得到另外二者的網(wǎng)絡(luò)能量.

3 混合圖的網(wǎng)絡(luò)能量性質(zhì)

上文中通過對無向圖及有向圖的網(wǎng)絡(luò)維數(shù)及網(wǎng)絡(luò)能量的分析研究，提出了混合圖的網(wǎng)絡(luò)能量，下面，我們對混合圖的網(wǎng)絡(luò)能量性質(zhì)進(jìn)行分析研究.

定理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）的上限進(jìn)行分析研究.

定理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）的上限進(jìn)行分析研究，可以得到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)用到無向圖及有向圖中.

下面，對正則圖進(jìn)行分析研究.

定理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)用到無向圖及有向圖中.

下面對隨機(jī)圖進(jìn)行分析研究.

定理6 當(dāng)混合圖M 的原始圖G 是隨機(jī)圖Gn（p）時，混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足下式：

式中：n 為混合圖M 的節(jié)點數(shù)目；r 為混合圖M 中有向邊的比例；p 為原始圖G 中節(jié)點對之間隨機(jī)連接的概率.

證 在原始圖G 中，由于G 是隨機(jī)圖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)用到無向圖及有向圖中.

4 結(jié)論

無向圖的圖能量定義為圖的鄰接矩陣所有特征值絕對值之和.由于無向圖的圖能量在理論化學(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ò)能量進(jìn)行分析，并嘗試對帶權(quán)圖、無限圖、超圖等更為復(fù)雜的不同類型圖的能量進(jìn)行深入研究.