網(wǎng)絡(luò)能量在混合圖中的研究與應(yīng)用

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

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

圖能量最早是由Gutman 于1978 年正式提出的[1]，對(duì)圖能量的研究可溯源到二十世紀(jì)三四十年代化學(xué)家對(duì)共軛的烴類化合物總π 能量的研究.烴類化合物總π 能量可通過(guò)Huckel 分子軌道理論近似求出[2-3].圖能量定義為圖的鄰接矩陣所有特征值絕對(duì)值之和.自圖能量提出以來(lái)，圖能量受到人們極大的關(guān)注，一系列能量，如距離能量[4]、擬Laplacian能量[5]、關(guān)聯(lián)能量[6]、匹配能量[7]、Laplacian 能量[8]、無(wú)符號(hào)Laplacian 能量[9]、Von Neumann 能量[10]、距離Laplacian 能量[11]、距離無(wú)符號(hào)Laplacian 能量[11]等其他類似能量，相繼提出.

圖能量自提出以來(lái)已在理論化學(xué)及代數(shù)圖論等領(lǐng)域得到極為廣泛的應(yīng)用，一些重要研究成果相繼問(wèn)世.由于大規(guī)模矩陣特征值計(jì)算極為繁瑣，對(duì)圖能量的研究更多的集中在隨機(jī)圖、正則圖、樹圖、二部圖等幾類特殊的圖中[12-14].對(duì)圖能量的改進(jìn)與拓展是圖能量研究的重要內(nèi)容，一系列類似能量的提出大大豐富了圖能量的研究?jī)?nèi)容.但這些類似能量仍未脫離鄰接矩陣特征值計(jì)算的局限，應(yīng)用范圍受限.現(xiàn)今提出的圖能量及類似能量已有數(shù)十種之多[15]，對(duì)圖能量的研究已由無(wú)向圖推廣應(yīng)用到有向圖[16-17]、混合圖[18-20]等其他多種類型的圖.由于混合圖節(jié)點(diǎn)之間連接的復(fù)雜性，對(duì)混合圖能量的研究遠(yuǎn)較無(wú)向圖及有向圖復(fù)雜[21-22]，實(shí)際上，對(duì)圖能量的研究目前仍以對(duì)無(wú)向圖的能量研究為主，并改進(jìn)后逐步推廣應(yīng)用到有向圖及混合圖等[23].

先前，本文作者從網(wǎng)絡(luò)維數(shù)[24]的視角出發(fā)，提出了網(wǎng)絡(luò)能量的概念，將網(wǎng)絡(luò)能量應(yīng)用于無(wú)向圖[25]及有向圖[26]，并將無(wú)向圖的網(wǎng)絡(luò)能量與傳統(tǒng)意義上的圖能量及距離能量、擬Laplacian 能量、關(guān)聯(lián)能量、匹配能量等進(jìn)行對(duì)比，得出了一些有意義的結(jié)論，同時(shí)將有向圖的網(wǎng)絡(luò)能量與無(wú)向圖的網(wǎng)絡(luò)能量及有向圖的斜能量等進(jìn)行對(duì)比，也得出了一些有意義的結(jié)論.本文中，我們嘗試將網(wǎng)絡(luò)能量由無(wú)向圖及有向圖推廣應(yīng)用到混合圖，并分析研究混合圖網(wǎng)絡(luò)能量的若干重要性質(zhì).

1 預(yù)備知識(shí)

1.1 圖能量

式中：λ1A（G）、λ2A（G）、λ3A（G）、…、λiA（G）、…、λnA（G）表示A（G）的各個(gè)特征值.

對(duì)無(wú)向圖G 的所有邊賦予一個(gè)方向σ，則得到一個(gè)有向圖Gσ，其斜鄰接矩陣可記為S（Gσ）.有向圖Gσ中，若節(jié)點(diǎn)vi與vj之間存在一條有向邊，則Aij=-Aji=1，否則，Aij=Aji=0.有向圖Gσ的斜能量εS（Gσ）定義為其斜鄰接矩陣S（Gσ）的所有特征值絕對(duì)值之和，即[16]

式中：λ1S（Gσ）、λ2S（Gσ）、λ3S（Gσ）、…、λiS（Gσ）、…、λnS（Gσ）表示S（Gσ）的各個(gè)特征值.

由于對(duì)無(wú)向邊賦予一個(gè)方向有兩種不同的選擇，一個(gè)無(wú)向圖G 對(duì)應(yīng)有2m個(gè)有向圖Gσ.圖的大部分類似能量均基于矩陣特征值的計(jì)算，如距離能量、擬Laplacian 能量、關(guān)聯(lián)能量等.對(duì)大規(guī)模矩陣而言，特征值計(jì)算極為困難，使得精確的圖能量分析殊為不便，圖能量只在極少數(shù)的特殊圖中得到較為深入的分析研究.對(duì)圖能量的研究更多的是關(guān)注圖能量的上下限，如對(duì)正則圖及隨機(jī)圖能量上限的研究等.

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

由于傳統(tǒng)意義上的圖能量依賴于對(duì)矩陣特征值的計(jì)算，對(duì)大規(guī)模圖的應(yīng)用受限，人們嘗試從其他的途徑得到圖能量，以避免對(duì)矩陣特征值計(jì)算的低效操作.我們從網(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è)共同的上限.與無(wú)向圖的分析研究類似，對(duì)無(wú)向圖G 的所有邊賦予一個(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).對(duì)比式（4）及式（6），可以發(fā)現(xiàn)，EN（G）與EN（Gσ）二者之間有著相似的形式，可以對(duì)它們進(jìn)行深入細(xì)致的分析.

1.3 混合圖

混合圖M 是對(duì)無(wú)向圖G 的部分邊賦予一個(gè)方向而得到的圖.對(duì)任一混合圖M 而言，其Hermitian鄰接矩陣可記為H（M）.混合圖M 中，若節(jié)點(diǎn)vi與vj之間存在一條有向邊，則Hij=-Hji=i；若節(jié)點(diǎn)vi與vj之間存在一條無(wú)向邊，則Hij=Hji=1；若節(jié)點(diǎn)vi與vj之間不存在任何邊，則Hij=Hji=0.混合圖M 的Hermitian 能量εH（M）定義為其Hermitian 鄰接矩陣H（M）的所有特征值絕對(duì)值之和，即[18]

式中：λ1H（M）、λ2H（M）、λ3H（M）、…、λiH（M）、…、λnH（M）表示H（M）的各個(gè)特征值.

對(duì)混合圖而言，還有Hermitian-Randic 能量[19]、Hermitian 關(guān)聯(lián)能量[20]等其他多種形式的能量.

混合圖M 的Hermitian 能量εH（M）也有很多與無(wú)向圖G 的圖能量E（G）及有向圖Gσ的斜能量εS（Gσ）等類似的上下限.

對(duì)含有n 個(gè)節(jié)點(diǎn)m 條邊，且原始圖中節(jié)點(diǎn)最大度為Δ 的混合圖M 來(lái)說(shuō)，其Hermitian 能量εH（M）上下限滿足下式[18]：

對(duì)比無(wú)向圖G 的圖能量E（G）及有向圖Gσ的斜能量εS（Gσ）的上限，很顯然，混合圖的Hermitian 能量εH（M）兼具E（G）及εS（Gσ）的一些特點(diǎn).

特別地，當(dāng)混合圖M 的原始圖為k-正則圖時(shí)，有

可以發(fā)現(xiàn)，混合圖的Hermitian 能量具備無(wú)向圖的網(wǎng)絡(luò)能量的一些特點(diǎn).

由于混合圖遠(yuǎn)較無(wú)向圖及有向圖復(fù)雜，對(duì)混合圖能量的研究尚在持續(xù)深入，相關(guān)的研究成果并不多.

對(duì)比式（1）（2）（7）可以發(fā)現(xiàn)，無(wú)向圖、有向圖、混合圖的能量計(jì)算均是通過(guò)計(jì)算矩陣的特征值而得到的，計(jì)算復(fù)雜.通過(guò)式（3）對(duì)無(wú)向圖的網(wǎng)絡(luò)維數(shù)的研究，提出了無(wú)向圖的網(wǎng)絡(luò)能量；通過(guò)式（5）對(duì)有向圖的網(wǎng)絡(luò)維數(shù)的研究，提出了有向圖的網(wǎng)絡(luò)能量.同理，對(duì)適用于無(wú)向圖及有向圖的網(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ù)

混合圖既含有無(wú)向邊，又含有有向邊，是一類介于無(wú)向圖與有向圖之間的特殊的圖.通過(guò)對(duì)式（3）中無(wú)向圖的網(wǎng)絡(luò)維數(shù)及式（5）中有向圖的網(wǎng)絡(luò)維數(shù)的研究，可以得出混合圖的網(wǎng)絡(luò)維數(shù).

混合圖M 的網(wǎng)絡(luò)維數(shù)DN（M）可以表述為：

由于混合圖M 是對(duì)無(wú)向圖G 中的部分無(wú)向邊賦予方向而得到的，若賦予有向邊的比例為r，即

式（11）可改寫為：

對(duì)式（11）進(jìn)行分析，可以發(fā)現(xiàn)，當(dāng)r=0 時(shí)，混合圖M 退化為無(wú)向圖G，此時(shí)，式（13）退化為式（3）；當(dāng)r=1 時(shí)，混合圖M 退化為有向圖Gσ，此時(shí)，式（13）退化為式（5）.即式（3）所示的無(wú)向圖的網(wǎng)絡(luò)維數(shù)及式（5）所示的有向圖的網(wǎng)絡(luò)維數(shù)分別是式（13）所示的混合圖的網(wǎng)絡(luò)維數(shù)在r=0 及r=1 時(shí)的特例.于是，通過(guò)式（13）將無(wú)向圖、有向圖、混合圖三者通過(guò)網(wǎng)絡(luò)維數(shù)聯(lián)系起來(lái)了.

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

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

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

對(duì)式（15）進(jìn)行分析，可以發(fā)現(xiàn)，當(dāng)r=0 時(shí)，混合圖M 退化為無(wú)向圖G，此時(shí)，式（15）退化為式（4）；當(dāng)r=1 時(shí)，混合圖M 退化為有向圖Gσ，此時(shí)，式（15）退化為式（6）.即式（4）所示的無(wú)向圖的網(wǎng)絡(luò)能量及式（6）所示的有向圖的網(wǎng)絡(luò)能量分別是式（15）所示的混合圖的網(wǎng)絡(luò)能量在r=0 及r=1 時(shí)的特例.于是，通過(guò)式（15）將無(wú)向圖、有向圖、混合圖三者通過(guò)網(wǎng)絡(luò)能量進(jìn)一步聯(lián)系起來(lái)了.

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

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

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

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

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

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

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

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

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

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

上文中通過(guò)對(duì)無(wú)向圖及有向圖的網(wǎng)絡(luò)維數(shù)及網(wǎng)絡(luò)能量的分析研究，提出了混合圖的網(wǎng)絡(luò)能量，下面，我們對(duì)混合圖的網(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）的上限不超過(guò)原始圖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）取等號(hào)的條件是無(wú)向圖G、有向圖Gσ、混合圖M 均為空?qǐng)D，即三者均只含有節(jié)點(diǎn)，不含有邊，即，此時(shí)，有

于是，可以得出如下引理.

引理1 混合圖M 的網(wǎng)絡(luò)能量EN（M）的下限為1，即

證 根據(jù)定義，引理1 顯然成立.引理1 得證.證畢.

引理1 的結(jié)論可以推廣應(yīng)用到無(wú)向圖及有向圖中.實(shí)際上，無(wú)向圖G 的網(wǎng)絡(luò)能量EN（G）及有向圖G的網(wǎng)絡(luò)能量EN（Gσ）的下限均是1.

下面，對(duì)混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限進(jìn)行分析研究.

定理2 混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足式（23）：

式中：n 為混合圖M 的節(jié)點(diǎn)數(shù)目；m 為混合圖M 的邊數(shù)目；r 為混合圖M 中有向邊的比例.

證 根據(jù)式（15）所示的混合圖網(wǎng)絡(luò)能量的表述，欲證定理2，只需證式（24）即可：

定理2 顯然成立.定理2 得證.證畢.

當(dāng)r=0 及r=1 時(shí)，定理2 的結(jié)論也可以推廣應(yīng)用到無(wú)向圖及有向圖中.由于0

定理3 混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足式（27）：

式中：n 為混合圖M 的節(jié)點(diǎn)數(shù)目；m 為混合圖M 的邊數(shù)目；r 為混合圖M 中有向邊的比例.

證 由于2m≤n（n-1），代入式（23），定理3 顯然成立.定理3 得證.證畢.

繼續(xù)對(duì)混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限進(jìn)行分析研究，可以得到EN（M）的一個(gè)更為緊致的上限.

定理4 當(dāng)（2-r）m ≥n 時(shí)，混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足式（28）：

式中：n 為混合圖M 的節(jié)點(diǎn)數(shù)目；m 為混合圖M 的邊數(shù)目；r 為混合圖M 中有向邊的比例.

證 根據(jù)式（15）所示的混合圖網(wǎng)絡(luò)能量的表述，欲證定理4，只需證明下式即可：

當(dāng)且僅當(dāng)x=n 時(shí)，f（x）的一階導(dǎo)數(shù)f′（x）=0.

于是，有

定理4 顯然成立.定理4 得證.證畢.

當(dāng)r=0 及r=1 時(shí)，定理4 的結(jié)論同樣可以推廣應(yīng)用到無(wú)向圖及有向圖中.

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

定理5 當(dāng)混合圖M 的原始圖G 是k-正則圖時(shí)，混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足下式：

式中：n 為混合圖M 的節(jié)點(diǎn)數(shù)目；r 為混合圖M 中有向邊的比例；k 為原始圖G 中任一節(jié)點(diǎn)的節(jié)點(diǎn)度.

證 在原始圖G 中，由于G 是k-正則圖，則有kn=2m，即

將式（34）代入式（23），即有：

定理5 顯然成立.定理5 得證.證畢.

由于0

在特殊情況下，當(dāng)G≌Cn，即G 是一個(gè)環(huán)圖時(shí)，有k=2，此時(shí)，可得到如下引理.

引理2 當(dāng)混合圖M 的原始圖G 是一個(gè)環(huán)圖，即G≌Cn時(shí)，混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足下式：

證 將k=2 代入式（33），即得到式（36）.引理2顯然成立.引理2 得證.證畢.

此外，當(dāng)G≌Kn，即G 是一個(gè)完全圖時(shí)，有k=n-1，此時(shí)，可得到如下引理.

引理3 當(dāng)混合圖M 的原始圖G 是一個(gè)完全圖，即G≌Kn時(shí)，混合圖M 的網(wǎng)絡(luò)能量EN（M）的上限滿足下式：

引理3 顯然成立.引理3 得證.證畢.

當(dāng)r=0 及r=1 時(shí)，定理5 的結(jié)論及引理2、引理3 同樣可以推廣應(yīng)用到無(wú)向圖及有向圖中.

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

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

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

證 在原始圖G 中，由于G 是隨機(jī)圖Gn（p），則有：

將式（40）代入式（23），即有：

定理6 顯然成立.定理6 得證.證畢.

從式（41）可以看出，當(dāng)p=2/n 時(shí)，G 為一個(gè)環(huán)圖，此時(shí)，定理6 退化為引理2；當(dāng)p=1 時(shí)，G 為一個(gè)完全圖，此時(shí)，定理6 退化為引理3.即定理6 是引理2 及引理3 在一般情形下的泛化與推廣.

當(dāng)r=0 及r=1 時(shí)，定理6 的結(jié)論同樣可以推廣應(yīng)用到無(wú)向圖及有向圖中.

4 結(jié)論

無(wú)向圖的圖能量定義為圖的鄰接矩陣所有特征值絕對(duì)值之和.由于無(wú)向圖的圖能量在理論化學(xué)及代數(shù)圖論中的重要價(jià)值，圖能量自提出以來(lái)受到人們極大的關(guān)注，一系列的類似能量相繼提出，并逐步推廣應(yīng)用到有向圖及混合圖等其他多種類型的圖.大多數(shù)圖的能量均是基于矩陣特征值計(jì)算得到的，如無(wú)向圖的距離能量、有向圖的斜能量、混合圖的Hermitian 能量等.由于大規(guī)模矩陣的特征值計(jì)算極為繁瑣，傳統(tǒng)意義上對(duì)圖能量的研究不便于推廣應(yīng)用到大規(guī)模圖中.網(wǎng)絡(luò)能量脫離了傳統(tǒng)意義上圖能量基于矩陣特征值計(jì)算的局限，并在無(wú)向圖及有向圖中得到較為成功的應(yīng)用.本文將應(yīng)用于無(wú)向圖及有向圖中的網(wǎng)絡(luò)能量推廣到混合圖中，論述了混合圖的網(wǎng)絡(luò)能量，并分析研究了混合圖的網(wǎng)絡(luò)能量的若干重要性質(zhì).后續(xù)工作的重點(diǎn)在于對(duì)特定的混合圖的網(wǎng)絡(luò)能量進(jìn)行分析，并嘗試對(duì)帶權(quán)圖、無(wú)限圖、超圖等更為復(fù)雜的不同類型圖的能量進(jìn)行深入研究.