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

刘胜久，李天瑞†，谢鹏，刘佳

（1.西南交通大学 信息科学与技术学院，四川 成都 611756；2.四川省云计算与智能技术高校重点实验室，四川 成都 611756）

图能量最早是由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 图能量

式中：λ1A（G）、λ2A（G）、λ3A（G）、…、λiA（G）、…、λnA（G）表示A（G）的各个特征值.

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

1.2 网络能量

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

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

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

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

图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]

式中：λ1H（M）、λ2H（M）、λ3H（M）、…、λiH（M）、…、λnH（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]：

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

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

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

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

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

2 混合图的网络能量研究

2.1 混合图的网络维数

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

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

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

式（11）可改写为：

对式（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）所示：

对式（14）进行分析，可以得到等价的另一表述，如式（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）进行分析，可以得到：

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

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

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

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

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

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

3 混合图的网络能量性质

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

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

证 根据定义，定理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 均为空图，即三者均只含有节点，不含有边，即，此时，有

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

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

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

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

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

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

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

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

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

当r=0 及r=1 时，定理2 的结论也可以推广应用到无向图及有向图中.由于0

定理3 混合图M 的网络能量EN（M）的上限满足式（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）：

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

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

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

于是，有

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

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

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

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

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

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

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

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

由于0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 结论

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