网络能量在混合图中的研究与应用

刘胜久 李天瑞 谢鹏 刘佳

摘   要：传统的混合图的能量通过对方阵形式的矩陣特征值的计算而得到，难以推广应用到大规模的混合图中. 针对这个问题，本文将网络维数应用于混合图中，提出了混合图的网络能量，从而将网络能量从无向图及有向图推广应用到混合图. 混合图的网络能量可以通过混合图的节点数目及有向边与无向边的数目而得到，同时给出了混合图的网络能量的若干上下限. 在与混合图的Hermitian能量及有向图与无向图的网络能量的对比中分析了所提出的混合图的网络能量的若干重要性质，并论证了无向图、有向图及混合图的网络能量三者之间的内在关联.

关键词：图能量;网络能量;无向图;有向图;混合图

中图分类号：TP391                       文献标志码：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]，对图能量的研究可溯源到二十世纪三四十年代化学家对共轭的烃类化合物总π能量的研究. 烃类化合物总π能量可通过Huckel分子轨道理论近似求出[2-3]. 图能量定义为图的邻接矩阵所有特征值绝对值之和. 自图能量提出以来，图能量受到人们极大的关注，一系列能量，如距离能量[4]、拟Laplacian能量[5]、关联能量[6]、匹配能量[7]、Laplacian能量[8]、无符号Laplacian能量[9]、Von Neumann能量[10]、距离Laplacian能量[11]、距离无符号Laplacian能量[11]等其他类似能量，相继提出.

图能量自提出以来已在理论化学及代数图论等领域得到极为广泛的应用，一些重要研究成果相继问世. 由于大规模矩阵特征值计算极为繁琐，对图能量的研究更多的集中在随机图、正则图、树图、二部图等几类特殊的图中[12-14]. 对图能量的改进与拓展是图能量研究的重要内容，一系列类似能量的提出大大丰富了图能量的研究内容. 但这些类似能量仍未脱离邻接矩阵特征值计算的局限，应用范围受限. 现今提出的图能量及类似能量已有数十种之多[15]， 对图能量的研究已由无向图推广应用到有向图[16-17]、混合图[18-20]等其他多种类型的图. 由于混合图节点之间连接的复杂性，对混合图能量的研究远较无向图及有向图复杂[21-22]，实际上，对图能量的研究目前仍以对无向图的能量研究为主，并改进后逐步推广应用到有向图及混合图等[23].

先前，本文作者从网络维数[24]的视角出发，提出了网络能量的概念，将网络能量应用于无向图[25]及有向图[26]，并将无向图的网络能量与传统意义上的图能量及距离能量、拟Laplacian能量、关联能量、匹配能量等进行对比，得出了一些有意义的结论，同时将有向图的网络能量与无向图的网络能量及有向图的斜能量等进行对比，也得出了一些有意义的结论. 本文中，我们尝试将网络能量由无向图及有向图推广应用到混合图，并分析研究混合图网络能量的若干重要性质.

1   预备知识

1.1   图能量

对任一无向图G = （V，E）而言，其中，V = n，E = m，其邻接矩阵可记为A（G）. 无向图G中，若节点vi与vj之间存在一条无向边，则Aij = Aji = 1，否则，Aij = Aji = 0. 无向图G的图能量E（G）定义为其邻接矩阵A（G）的所有特征值绝对值之和，即[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的所有边赋予一个方向σ，则得到一个有向图Gσ，其斜邻接矩阵可记为S（Gσ）. 有向图Gσ中，若节点vi与vj之间存在一条有向边，则Aij = -Aji = 1，否则，Aij = Aji = 0. 有向图Gσ的斜能量εS（Gσ）定义为其斜邻接矩阵S（Gσ）的所有特征值绝对值之和，即[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对应有2m个有向图Gσ. 图的大部分类似能量均基于矩阵特征值的计算，如距离能量、拟Laplacian能量、关联能量等. 对大规模矩阵而言，特征值计算极为困难，使得精确的图能量分析殊为不便，图能量只在极少数的特殊图中得到较为深入的分析研究. 对图能量的研究更多的是关注图能量的上下限，如对正则图及随机图能量上限的研究等.

1.2   网络能量

由于传统意义上的图能量依赖于对矩阵特征值的计算，对大规模图的应用受限，人们尝试从其他的途径得到图能量，以避免对矩阵特征值计算的低效操作. 我们从网络维数的视角出发，提出了网络能量的概念.

对任一无向图G=（V，E），其中，V = n，E = m，其网络维数DN（G）定义为[22]：

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

图G的网络能量EN（G）定义为[23]：

EN（G） = n           （4）

图G的网络能量EN（G）与图G的能量E（G）二者之间有许多类似的性质，并且存在多个共同的上限.  与无向图的分析研究类似，对无向图G的所有边赋予一个方向而得到的有向图Gσ而言，其网络维数DN（Gσ）可以表述为：

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

图Gσ的网络能量EN（Gσ）定义如下[24]：

EN（Gσ） = n        （6）

图Gσ的网络能量EN（Gσ）与图G的网络能量EN（G）及图Gσ的斜能量ε（Gσ）三者之间存在极为密切的关联. 对比式（4）及式（6），可以发现，EN（G）与EN（Gσ）二者之间有着相似的形式，可以对它们进行深入细致的分析.

1.3   混合图

混合图M是对无向图G的部分边赋予一个方向而得到的图. 对任一混合图M而言，其Hermitian邻接矩阵可记为H（M）. 混合图M中，若节点vi与vj之间存在一条有向边，则Hij = -Hji = i;若节点vi与vj之间存在一条无向边，则Hij = Hji = 1;若节点vi与vj之间不存在任何边，则Hij = Hji = 0. 混合图M的Hermitian能量εH（M）定义为其Hermitian邻接矩阵H（M）的所有特征值绝对值之和，即[18]

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

式中：λ1 H（M）、λ2 H（M）、λ3 H（M）、…、λi H（M）、…、λn H（M）表示H（M）的各个特征值.

對混合图而言，还有Hermitian-Randic能量[19]、Hermitian关联能量[20]等其他多种形式的能量.

混合图M的Hermitian能量εH（M）也有很多与无向图G的图能量E（G）及有向图Gσ的斜能量εS（Gσ）等类似的上下限.

对含有n个节点m条边，且原始图中节点最大度为Δ的混合图M来说，其Hermitian能量εH（M）上下限满足下式[18]：

εH（M） ≤

≤ n

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

对比无向图G的图能量E（G）及有向图Gσ的斜能量εS（Gσ）的上限，很显然，混合图的Hermitian能量εH（M）兼具E（G）及εS（Gσ）的一些特点.

特别地，当混合图M的原始图为k-正则图时，有

εH（M） ≤ n      （9）

可以发现，混合图的Hermitian能量具备无向图的网络能量的一些特点.

由于混合图远较无向图及有向图复杂，对混合图能量的研究尚在持续深入，相关的研究成果并不多.

对比式（1）（2）（7）可以发现，无向图、有向图、混合图的能量计算均是通过计算矩阵的特征值而得到的，计算复杂. 通过式（3）对无向图的网络维数的研究，提出了无向图的网络能量;通过式（5）对有向图的网络维数的研究，提出了有向图的网络能量. 同理，对适用于无向图及有向图的网络维数进行拓展，将网络维数应用于混合图中，提出混合图的网络能量.

2   混合图的网络能量研究

2.1   混合图的网络维数

混合图既含有无向边，又含有有向边，是一类介于无向图与有向图之间的特殊的图. 通过对式（3）中无向图的网络维数及式（5）中有向图的网络维数的研究，可以得出混合图的网络维数.

设混合图M的节点数为n，邊数为m，其中，无向边数目为m，有向边数目为[m][→]. 则有：

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

混合图M的网络维数DN（M）可以表述为：

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

由于混合图M是对无向图G中的部分无向边赋予方向而得到的，若赋予有向边的比例为r，即

r =  =          （12）

式（11）可改写为：

DN（M） =  =

= logn （2 - r）m       （13）

对式（11）进行分析，可以发现，当r=0时，混合图M退化为无向图G，此时，式（13）退化为式（3）;当r=1时，混合图M退化为有向图Gσ，此时，式（13）退化为式（5）. 即式（3）所示的无向图的网络维数及式（5）所示的有向图的网络维数分别是式（13）所示的混合图的网络维数在r=0及r=1时的特例. 于是，通过式（13）将无向图、有向图、混合图三者通过网络维数联系起来了.

2.2   混合图的网络能量

观察式（4）及式（6），可以发现，无向图及有向图的网络能量均是通过其对应的网络维数式（3）及式（5）得到的，对式（11）所示的混合图的网络维数进行研究，可以得到混合图M的网络能量EN（M），如式（14）所示：

EN（M） = n        （14）

对式（14）进行分析，可以得到等价的另一表述，如式（15）所示：

EN（M） = n        （15）

对式（15）进行分析，可以发现，当r=0时，混合图M退化为无向图G，此时，式（15）退化为式（4）;当r=1时，混合图M退化为有向图Gσ，此时，式（15）退化为式（6）. 即式（4）所示的无向图的网络能量及式（6）所示的有向图的网络能量分别是式（15）所示的混合图的网络能量在r=0及r=1时的特例. 于是，通过式（15）将无向图、有向图、混合图三者通过网络能量进一步联系起来了.

2.3   不同类型图的网络能量

式（3）（5）（13）分别给出了无向图、有向图、混合图的网络维数，对这些公式进行分析，可以得出它们之间的关系.

对式（3）及式（5）进行分析，可以得到：

= 2         （16）

对式（3）及式（13）进行分析，可以得到：

=          （17）

在实际计算中，只要得到有向图、无向图、混合图三者之一的网络维数及混合图中有向边的比例r，即可得到另外二者的网络维数.

式（4）（6）（15）分别给出了无向图、有向图、混合图的网络能量，对这些公式进行分析，可以得出它们之间的关系.

对式（4）及式（6）进行分析，可以得到：

= n = 2        （18）

对式（4）及式（13）进行分析，可以得到：

= n =         （19）

于是，在实际计算中，只要得到有向图、无向图、混合图三者之一的网络能量及混合图中有向边的比例r与节点数目n，即可得到另外二者的网络能量.

3   混合图的网络能量性质

上文中通过对无向图及有向图的网络维数及网络能量的分析研究，提出了混合图的网络能量，下面，我们对混合图的网络能量性质进行分析研究.

定理1   混合图M的网络能量EN（M）介于其原始图G的网络能量EN（G）及有向图Gσ的网络能量EN（Gσ）之间，即

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

证   根据定义，定理1显然成立. 定理1得证. 证毕.

根据定理，可以得出混合图M的网络能量EN（M）的上限不超过原始图G的网络能量EN（G）的上限，混合图M的网络能量EN（M）的下限不低于有向图G的网络能量EN（Gσ）的下限，即EN（G）的上限也是EN（M）的上限，EN（Gσ）的下限也是EN（M）的下限.

式（20）取等号的条件是无向图G、有向图Gσ、混合图M均为空图，即三者均只含有节点，不含有边，即Gσ ? M ? G ? Kn，此时，有

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

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

引理1   混合图M的网络能量EN（M）的下限为1，即

EN（M）≥1          （22）

证   根据定义，引理1显然成立. 引理1得证. 证毕.

引理1的结论可以推广应用到无向图及有向图中. 实际上，无向图G的网络能量EN（G）及有向图G的网络能量EN（Gσ）的下限均是1.

下面，对混合图M的网络能量EN（M）的上限进行分析研究.

定理2   混合图M的网络能量EN（M）的上限满足式（23）：

EN（M）≤           （23）

式中：n为混合图M的节点数目;m为混合图M的边数目;r为混合图M中有向边的比例.

证   根据式（15）所示的混合图网络能量的表述，欲证定理2，只需证式（24）即可：

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

有

logn EN（M） - logn  =

- logn  =

- logn

（25）

对式（25）中的 按照泰勒公式展开，只取前两项，则有：

logn EN（M） - logn  ≤

1+logn - logn  =

logn - logn  = 0

（26）

定理2显然成立. 定理2得证. 证毕.

当r = 0及r = 1时，定理2的结论也可以推广应用到无向图及有向图中. 由于0 < r < 1，结合式（8），本文提出的混合图的网络能量具备与其对应的Hermitian能量类似的一些特性. 在混合图M中，同样有2m≤n（n-1），可以得到混合图M的网络能量EN（M）的另一个上限.

定理3   混合图M的网络能量EN（M）的上限满足式（27）：

EN（M） ≤ n        （27）

式中：n为混合图M的节点数目;m为混合图M的边数目;r为混合图M中有向边的比例.

证   由于2m≤n（n-1），代入式（23），定理3显然成立. 定理3得证. 证毕.

继续对混合图M的网络能量EN（M）的上限进行分析研究，可以得到EN（M）的一个更为紧致的上限.

定理4   当（2 - r）m ≥ n时，混合图M的网络能量EN（M）的上限满足式（28）：

logn EN（M）-

logn

+≤0

（28）

式中：n为混合图M的节点数目;m为混合图M的边数目;r为混合图M中有向边的比例.

证   根据式（15）所示的混合图网络能量的表述，欲证定理4，只需证明下式即可：

logn EN（M）-

logn

+≤0

（29）

有

logn EN（M）-

logn

+≤

logn-logn{+

}             （30）

令f（x）=+，当x≤n时，f（x）为增函数;当x>n时，f（x）为减函数，即f（x）的一阶导数f ′（x）在区间（-∞，n）为非负数，在区间（n，+∞）为非正数.

f ′（x）=->0，x

=0，x=n

<0，x>n （31）

当且仅当x=n时，f（x）的一阶导数 f ′（x）=0.

于是，有

logn EN（M）-

logn

+≤

logn-logn{+

}=logn-

logn=0             （32）

定理4显然成立. 定理4得证. 证毕.

当r=0及r=1时，定理4的结论同样可以推广应用到无向图及有向图中.

下面，对正则图进行分析研究.

定理5   当混合图M的原始图G是k-正则图时，混合圖M的网络能量EN（M）的上限满足下式：

EN（M） ≤ n      （33）

式中：n為混合图M的节点数目;r为混合图M中有向边的比例;k为原始图G中任一节点的节点度.

证   在原始图G中，由于G是k-正则图，则有kn = 2m，即

m = kn         （34）

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

EN（M） ≤  =

= n （35）

定理5显然成立. 定理5得证. 证毕.

由于0 < r < 1，结合式（9），我们提出的混合图的网络能量也具备与其对应的Hermitian能量类似的一些特性.

在特殊情况下，当G≌Cn，即G是一个环图时，有k = 2，此时，可得到如下引理.

引理2   当混合图M的原始图G是一个环图，即G≌Cn时，混合图M的网络能量EN（M）的上限满足下式：

EN（M） ≤ n         （36）

证   将k=2代入式（33），即得到式（36）. 引理2显然成立. 引理2得证. 证毕.

此外，当G≌Kn，即G是一个完全图时，有k = n - 1，此时，可得到如下引理.

引理3   当混合图M的原始图G是一个完全图，即G≌Kn时，混合图M的网络能量EN（M）的上限满足下式：

EN（M） ≤ n3 / 2         （37）

证   将k=n-1代入式（33），得到：

EN（M） ≤ n ≤

n = n3 / 2

（38）

引理3显然成立. 引理3得证. 证毕.

当r = 0及r = 1时，定理5的结论及引理2、引理3同样可以推广应用到无向图及有向图中.

下面对随机图进行分析研究.

定理6   当混合图M的原始图G是随机图Gn（p）时，混合图M的网络能量EN（M）的上限满足下式：

EN（M） ≤ n3 / 2            （39）

式中：n为混合图M的节点数目;r为混合图M中有向边的比例;p为原始图G中节点对之间随机连接的概率.

证   在原始图G中，由于G是随机图Gn（p），则有：

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

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

EN（M） ≤  ≤

= n3 / 2

（41）

定理6显然成立. 定理6得证. 证毕.

从式（41）可以看出，当p = 2/n时，G为一个环图，此时，定理6退化为引理2;当p = 1时，G为一个完全图，此时，定理6退化为引理3. 即定理6是引理2及引理3在一般情形下的泛化与推广.

当r = 0及r = 1时，定理6的结论同样可以推广应用到无向图及有向图中.

4   结   论

无向图的图能量定义为图的邻接矩阵所有特征值绝对值之和. 由于无向图的图能量在理论化学及代数图论中的重要价值，图能量自提出以来受到人们极大的关注，一系列的类似能量相继提出，并逐步推广应用到有向图及混合图等其他多种类型的图. 大多数图的能量均是基于矩阵特征值计算得到的，如无向图的距离能量、有向图的斜能量、混合图的Hermitian能量等. 由于大规模矩阵的特征值计算极为繁琐，传统意义上对图能量的研究不便于推广应用到大规模图中. 网络能量脱离了传统意义上图能量基于矩阵特征值计算的局限，并在无向图及有向图中得到较为成功的应用. 本文将应用于无向图及有向图中的网络能量推广到混合图中，论述了混合图的网络能量，并分析研究了混合图的网络能量的若干重要性质. 后续工作的重点在于对特定的混合图的网络能量进行分析，并尝试对带权图、无限图、超图等更为复杂的不同类型图的能量进行深入研究.

参考文献

[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，FURTULA 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]  王維忠，周琨强. 混合图的埃尔米特-关联能量[J]. 山东大学学报（理学版），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]  劉胜久，李天瑞，刘小伟. 网络维数：一种度量复杂网络的新方法[J]. 计算机科学，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.