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

劉勝久 李天瑞 謝鵬 劉佳

摘? ?要：傳統(tǒng)的混合圖的能量通過對(duì)方陣形式的矩陣特征值的計(jì)算而得到，難以推廣應(yīng)用到大規(guī)模的混合圖中. 針對(duì)這個(gè)問題，本文將網(wǎng)絡(luò)維數(shù)應(yīng)用于混合圖中，提出了混合圖的網(wǎng)絡(luò)能量，從而將網(wǎng)絡(luò)能量從無向圖及有向圖推廣應(yīng)用到混合圖. 混合圖的網(wǎng)絡(luò)能量可以通過混合圖的節(jié)點(diǎn)數(shù)目及有向邊與無向邊的數(shù)目而得到，同時(shí)給出了混合圖的網(wǎng)絡(luò)能量的若干上下限. 在與混合圖的Hermitian能量及有向圖與無向圖的網(wǎng)絡(luò)能量的對(duì)比中分析了所提出的混合圖的網(wǎng)絡(luò)能量的若干重要性質(zhì)，并論證了無向圖、有向圖及混合圖的網(wǎng)絡(luò)能量三者之間的內(nèi)在關(guān)聯(lián).

關(guān)鍵詞：圖能量;網(wǎng)絡(luò)能量;無向圖;有向圖;混合圖

中圖分類號(hào)：TP391? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：A

Research and Application of Network Energy on Mixed Graphs

LIU Shengjiu1，2，LI Tianrui1，2?，XIE Peng1，2，LIU Jia1，2

（1. School of Information Science and Technology，Southwest Jiaotong University，Chengdu 611756，China;

2. Sichuan Key Lab of Cloud Computing and Intelligent Technique，Chengdu 611756，China）

Abstract：The energy of the traditional mixed graph is obtained by calculating the eigenvalues of the matrix in the form of a square matrix，and it is difficult to be extended to large-scale mixed graphs.? In response to this problem， this paper applies the network dimension to the mixed graph， and proposes the network energy of the mixed graph， thus the network energy is extended from the undirected graph and the directed graph to the mixed graph. The network energy of a mixed graph can be obtained by the number of nodes and the number of directed and undirected edges of the mixed graph. At the same time，several upper and lower limits of the network energy of the mixed graph are given. Comparied with the Hermitian energy of mixed graph and the network energy of directed and undirected graphs， some important properties of the proposed network energy of the mixed graph are analyzed. The internal relationships among undirected graph， directed graph and mixed graph are also demonstrated.

Key words：graph energy;network energy;undirected graph;directed graph;mixed graph

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

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

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

1.1? ?圖能量

對(duì)任一無向圖G = （V，E）而言，其中，V = n，E = m，其鄰接矩陣可記為A（G）. 無向圖G中，若節(jié)點(diǎn)vi與vj之間存在一條無向邊，則Aij = Aji = 1，否則，Aij = Aji = 0. 無向圖G的圖能量E（G）定義為其鄰接矩陣A（G）的所有特征值絕對(duì)值之和，即[1]

E（G） = λi A（G）? ? ? ? ? （1）

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

對(duì)無向圖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]

εS（Gσ） = λi S（Gσ）? ? ? ? ? （2）

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

由于對(duì)無向邊賦予一個(gè)方向有兩種不同的選擇，一個(gè)無向圖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ò)能量的概念.

對(duì)任一無向圖G=（V，E），其中，V = n，E = m，其網(wǎng)絡(luò)維數(shù)DN（G）定義為[22]：

DN（G） =? = logn 2m? ? ? ? （3）

圖G的網(wǎng)絡(luò)能量EN（G）定義為[23]：

EN（G） = n? ? ? ? ? ?（4）

圖G的網(wǎng)絡(luò)能量EN（G）與圖G的能量E（G）二者之間有許多類似的性質(zhì)，并且存在多個(gè)共同的上限.? 與無向圖的分析研究類似，對(duì)無向圖G的所有邊賦予一個(gè)方向而得到的有向圖Gσ而言，其網(wǎng)絡(luò)維數(shù)DN（Gσ）可以表述為：

DN（Gσ） =? = logn m? ? ? ? （5）

圖Gσ的網(wǎng)絡(luò)能量EN（Gσ）定義如下[24]：

EN（Gσ） = n? ? ? ? （6）

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

εH（M） = λi H（M）? ? ? ? ? （7）

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

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

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

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

εH（M） ≤

≤ n

≤εH（M） ≤ 2m? ? ? ?（8）

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

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

εH（M） ≤ n? ? ? （9）

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

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

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

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

設(shè)混合圖M的節(jié)點(diǎn)數(shù)為n，邊數(shù)為m，其中，無向邊數(shù)目為m，有向邊數(shù)目為[m][→]. 則有：

m = m + [m][→]? ? ? （10）

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

DN（M）==logn（2m + [m][→]）? ? ?（11）

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

r =? =? ? ? ? ? （12）

式（11）可改寫為：

DN（M） =? =

= logn （2 - r）m? ? ? ?（13）

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

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

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

EN（M） = n? ? ? ? （14）

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

EN（M） = n? ? ? ? （15）

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

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

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

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

= 2? ? ? ? ?（16）

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

=? ? ? ? ? （17）

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

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

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

= n = 2? ? ? ? （18）

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

= n =? ? ? ? ?（19）

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

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

上文中通過對(duì)無向圖及有向圖的網(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σ）之間，即

EN（Gσ） ≤ EN（M） ≤ EN（G）? ? ? ?（20）

證? ?根據(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）取等號(hào)的條件是無向圖G、有向圖Gσ、混合圖M均為空?qǐng)D，即三者均只含有節(jié)點(diǎn)，不含有邊，即Gσ ? M ? G ? Kn，此時(shí)，有

EN（Gσ）=EN（M）=EN（G）=EN（Kn）=1? ? ? ? （21）

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

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

EN（M）≥1? ? ? ? ? （22）

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

引理1的結(jié)論可以推廣應(yīng)用到無向圖及有向圖中. 實(shí)際上，無向圖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）：

EN（M）≤? ? ? ? ? ?（23）

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

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

logn EN（M） - logn? ≤ 0? ? ? （24）

有

logn EN（M） - logn? =

- logn? =

- logn

（25）

對(duì)式（25）中的 按照泰勒公式展開，只取前兩項(xiàng)，則有：

logn EN（M） - logn? ≤

1+logn - logn? =

logn - logn? = 0

（26）

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

當(dāng)r = 0及r = 1時(shí)，定理2的結(jié)論也可以推廣應(yīng)用到無向圖及有向圖中. 由于0 < r < 1，結(jié)合式（8），本文提出的混合圖的網(wǎng)絡(luò)能量具備與其對(duì)應(yīng)的Hermitian能量類似的一些特性. 在混合圖M中，同樣有2m≤n（n-1），可以得到混合圖M的網(wǎng)絡(luò)能量EN（M）的另一個(gè)上限.

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

EN（M） ≤ n? ? ? ? （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）：

logn EN（M）-

logn

+≤0

（28）

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

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

logn EN（M）-

logn

+≤0

（29）

有

logn EN（M）-

logn

+≤

logn-logn{+

}? ? ? ? ? ? ?（30）

令f（x）=+，當(dāng)x≤n時(shí)，f（x）為增函數(shù);當(dāng)x>n時(shí)，f（x）為減函數(shù)，即f（x）的一階導(dǎo)數(shù)f ′（x）在區(qū)間（-∞，n）為非負(fù)數(shù)，在區(qū)間（n，+∞）為非正數(shù).

f ′（x）=->0，x

=0，x=n

<0，x>n （31）

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

于是，有

logn EN（M）-

logn

+≤

logn-logn{+

}=logn-

logn=0? ? ? ? ? ? ?（32）

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

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

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

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

EN（M） ≤ n? ? ? （33）

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

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

m = kn? ? ? ? ?（34）

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

EN（M） ≤? =

= n （35）

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

由于0 < r < 1，結(jié)合式（9），我們提出的混合圖的網(wǎng)絡(luò)能量也具備與其對(duì)應(yīng)的Hermitian能量類似的一些特性.

在特殊情況下，當(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）的上限滿足下式：

EN（M） ≤ n? ? ? ? ?（36）

證? ?將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）的上限滿足下式：

EN（M） ≤ n3 / 2? ? ? ? ?（37）

證? ?將k=n-1代入式（33），得到：

EN（M） ≤ n ≤

n = n3 / 2

（38）

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

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

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

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

EN（M） ≤ n3 / 2? ? ? ? ? ? （39）

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

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

m = n（n-1）p? ? ? ? ? ? ? （40）

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

EN（M） ≤? ≤

= n3 / 2

（41）

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

4? ?結(jié)? ?論

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

參考文獻(xiàn)

[1]? ?GUTMAN I. The energy of graph[J]. Ber Math Statist Sekt Forschungsz Graz，1978，103：1—22.

[2]? ? DEWAR M J S. The molecular orbital theory of organic chemistry[M]. New York：McGraw-Hill，1969：192.

[3]? ?COULSON C A，O'LCARY B，MALLION R B. Huckel theory for organic chemists[M]. London：Academic Press，1978：8—42.

[4]? ? INDULAL G，GUTMAN I，VIJAYAKUMAR A. On distance energy of graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry，2008，60（2）：461—472.

[5]? ? LIU J P，LIU B L. A Laplacian-energy like invariant of a graph[J]. MATCH Communications in Mathematical and in Computer Chemistry，2008，59（2）：355—372.

[6]? ? JOOYANDEH M，KIANI D，MIRZAKHAH M. Incidence energy of a graph[J]. MATCH Communications in Mathematical and in Computer Chemistry，2009，62（3）：561—572.

[7]? ? GUTMAN I，WAGNER S. The matching energy of a graph[J]. Discrete Applied Mathematics，2012，160（15）：2177—2187.

[8]? ? GUTMAN I，ZHOU B. Laplacian energy of a graph[J]. Linear Algebra and Its Applications，2006，414（1）：29—37.

[9]? ? SO W，ROBBIANO M，DE ABREU N M M，et al. Applications of a theorem by Ky Fan in the theory of graph energy[J]. Linear Algebra and Its Applications，2010，432（9）：2163—2169.

[10]? BRYC W，DEMBO A，JIANG T F. Spectral measure of large random Hankel，Markov and Toeplitz matrices[J]. The Annals of Probability，2006，34（1）：1—38.

[11]? DAS K C，AOUCHICHE M，HANSEN P. On （distance） Laplacian energy and （distance） signless Laplacian energy of graphs[J]. Discrete Applied Mathematics，2018，243：172—185.

[12]? DU W X，LI X L，LI Y Y. The Laplacian energy of random graphs[J]. Journal of Mathematical Analysis and Applications，2010，368（1）：311—319.

[13]? DU W X，LI X L，LI Y Y. Various energies of random graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry，2010，64（1）：251—260.

[14]? CHEN X L，LI X L，LIAN H S. The matching energy of random graphs[J]. Discrete Applied Mathematics，2015，193：102—109.

[15]? GUTMAN I，F(xiàn)URTULA B. Survey of graph energies[J]. Mathematics Interdisciplinary Research，2017，2：85—129.

[16]? ADIGA C，BALAKRISHNAN R，SO W. The skew energy of a digraph[J]. Linear Algebra and Its Applications，2010，432（7）：1825—1835.

[17]? LI J，LI X L，LIAN H S. Extremal skew energy of digraphs with no even cycles[J]. Transactions on Combinatorics，2014，3（1）：37—49.

[18]? LIU J X，LI X L. Hermitian-adjacency matrices and Hermitian energies of mixed graphs[J]. Linear Algebra and Its Applications，2015，466：182—207.

[19]? LU Y，WANG L G，ZHOU Q N. Hermitian-Randi? matrix and Hermitian-Randi? energy of mixed graphs[J]. Journal of Inequalities and Applications，2017，2017（1）：1—14.

[20]? 王維忠，周琨強(qiáng). 混合圖的埃爾米特-關(guān)聯(lián)能量[J]. 山東大學(xué)學(xué)報(bào)（理學(xué)版），2019，54（6）：53—58.

WANG W Z，ZHOU K Q. On the Hermitian-incidence energy of mixed graphs[J]. Journal of Shandong University （Natural Science），2019，54（6）：53—58. （In Chinese）

[21]? YU G H，QU H. Hermitian Laplacian matrix and positive of mixed graphs[J]. Applied Mathematics and Computation，2015，269：70—76.

[22]? YU G H，LIU X，QU H. Singularity of Hermitian （quasi-）Laplacian matrix of mixed graphs[J]. Applied Mathematics and Computation，2017，293：287—292.

[23]? LI X L，LIAN H S. A survey on the skew energy of oriented graphs[EB/OL]. arXiv：1304.5707.

[24]? 劉勝久，李天瑞，劉小偉. 網(wǎng)絡(luò)維數(shù)：一種度量復(fù)雜網(wǎng)絡(luò)的新方法[J]. 計(jì)算機(jī)科學(xué)，2019，46（1）：51—56.

LIU S J，LI T R，LIU X W. Network dimension：a new measure for complex networks[J]. Computer Science，2019，46（1）：51—56. （In Chinese）

[25]? LIU S J，LI T R，ZHU J，et al. Network energy：a new energy of a graph[C]//2019 IEEE 14th International Conference on Intelligent Systems and Knowledge Engineering （ISKE）. Dalian，China：IEEE，2019：785—789.

[26]? LIU S J，LI T R，ZHANG X B，et al. On network energy of oriented graphs[C]//Proceedings of the 14th International FLINS Conference on Robotics and Artificial Intelligence/IEEE 15th International Conference on Intelligent Systems and Knowledge Engineering （FLINS 2020/ISKE 2020）. Cologne，Germany：World Scientific，2020：11—18.