1. 引言
图熵是图的信息理论度量,近年来,图熵慢慢成为测量图的结构信息测度的载体,引出了许多基于不同信息函数的图熵,图熵的研究也取得了丰富的成果。图熵作为图的不变量研究的一个重要方向,在信息论、生物学等领域都引起广泛关注。Chen等人在文献[1]中提出了距离熵的概念,并研究了距离等于2时树的熵及其相关性质,本文在文献[1]的基础上,主要研究了距离等于3时给定图的距离熵。Shannon在文献[2]中提出信息熵这个概念,并证明了香农熵的许多重要理论。文献[1] [3]主要探索了基于新的信息函数,即到给定顶点的距离为k的顶点数的图熵,描述了测量图熵的方法,并给出距离熵的一些性质。文献[4] [5]通过使用基于拓扑指数的图距离测度不等式推导了图距离测度的相互关系,研究了基于G的顶点离心率的新图熵。文献[6] [7]研究对于具有固定阶数和给定分支顶点或段数的树和
的化学树
,给出Wiener极性指数的最佳可能的下界,并描述了达到此下界的所有树。文献[8]探索了化学图树的最小Wiener 极性指数。文献[9]通过不等式推导了图距离度量之间的相互关系,使用著名的Wiener index,Randić index,基于特征值的量和图熵。文献[10]给出化学树Wiener极性指数的极值。文献[11]在描述了给定直径树中该指数的极值树,部分回答了Bollobás和Tyomkyn的问题。文献[12]给出具有n个顶点和最大度Δ的树的最小(最大) Wiener极性指数,并确定了相应的极值树。文献[13]给出了具有n个顶点和k个悬挂边的树的最大Wiener极性指数,对相应的极值树进行了描述。图运算不仅广泛用于计算机科学,而且运用于许多拓扑指数文献[14]-[21] (比如Wiener, Wiener polarity index, Zagreb, Randic’等指数)。
本文主要研究了树的距离熵及其应用,并且研究了给定图在笛卡尔积、强积和冠积运算下的距离熵。
2. 预备知识
本文所提到的图均是无自环、无孤立顶点、无重边的简单无向连通图。设
是一个简单连通图,其顶点集为
,边集为
。已知与一个顶点v相邻的所有顶点称为v的邻域,顶点
的邻集用
表示,
表示G中顶点v的闭邻集。对于图
,如果S的两个顶点在G中不相邻,则子集
称为G的独立集,空集是独立集。G中顶点u和v的距离用
表示,简记为
。G中顶点u的度用
表示,简记为
。本文所给出的对数log均时以2为底数的。
在下文中,我们通过使用基本公式来定义新的图熵测度
,
其中
是顶点概率。我们定义
的顶点概率值为
则G的熵由Dehmer [3]定义为
距离是最重要的图不变量之一,接下来我们定义一个新的基于距离的信息泛函。
定义1 [1]设
是有n个顶点的连通图,对于顶点
,用
表示距离k到
的顶点数,
即
。
其中k是一个整数,使得
。我们定义信息泛函为
。
因此,我们得到了基于距离的图熵
定理1 [7]令G是顶点集为
,边集为
的简单连通图,那么有
。
证明 令
,
。则有
。考虑函数
,由于
是凸函数,故
。我们有詹森不等式
可得,
,化简可得
,通过计算得到
。定理得证,等式成立当且仅当
。
3. 树和化学树的距离熵
在本节中,分别给出了树和化学树距离熵的计算公式,以及树和化学树的相关定理。
3.1. 树T
设
为图G中长度为k的路径个数,由于每条长度为k的路径在
中计算了两次,所以
。
由于
时的情况在文献中已经给,因此我们考虑
的情形。由定义1可得
。
Wiener极性指数是一类代数拓扑指数,主要描述了图G中距离为3的无序顶点对的个数,即
,
定义2 [6]设
为n阶树,
,
。其中
,
,
所以,
时,
的熵为
如果
,那么
;
如果
,那么
。
3.2. 化学树
设
为有n个顶点的化学树(即每个顶点的度最多为4的树)的集合[7]。其顶点序列为
,其中
为T的度为i顶点个数
。其中
。
然后,我们引入一种图变换[1],即
,其中w是树T的最大度,u是与w不相邻的叶子,v是与w相邻的叶子。
我们将利用这种图变换证明下述定理。
定理2 设
是一个化学树,其顶点序列为
,则存在树T经过上述图变换得到的
,使得
。
证明 根据定义2,有
,因此我们可以得到
,现在我们只需考虑
,对于给定的化学树T,我们定义一个序列
,由于在T上进行上述变换得到了
,经过计算可以得到
,故由定义3可得
,证毕。
4. 一些图的距离熵
在本节中,分别给出了5种特殊图在笛卡尔积、强积、冠积下的距离熵。
定理3 设
和
分别为有6个顶点的单圈图和有2个顶点的完全图,则在笛卡尔积运算下得到的新图为
,如图1,则有
。
证明 首先求出
所以
。考虑
,
依次类推,可以得到
。所以我们得到
证毕。
定理4 设
和
分别为有2个顶点的路图和有4个顶点的路图,则在强积运算下得到的新图为
,如图1,则有
。
证明 首先求出
所以
。考虑
,
依次类推,可以得到
所以我们得到
证毕。
Figure 1. The order is
图1. 依次为
定理5 设
和
分别为有4个顶点的单圈图和有2个顶点的完全图,则在冠积运算下得到的新图为
,如图1,则有
证明 首先求出
所以
。考虑
,
依次类推,可以得到
所以我们得到
证毕。
定理6 设
为3个
完全图作笛卡尔积得到的3超维立方体,如图1,则有
。
证明 首先求出
所以
。考虑
,
依次类推,可以得到
。所以我们得到
证毕。
定理7 设
为一个
-纳米管,如图1,则有
证明 首先求出
所以
。考虑
,
依次类推,可以得到
,
。所以我们得到
证毕。
5. 总结
本文通过香农熵来研究给定图的距离熵,主要研究树和化学树的距离熵及其相关性质,并且研究了给定图在笛卡尔积、强积和冠积运算下的距离熵。本文的主要贡献是探索一个新的信息泛函,即给定一个顶点到其他顶点的距离为3的顶点个数,研究了它的一些计算公式和相关应用,从而更好地理解这个新的信息论量。本文主要考虑给定图基于距离的图熵及其相关性质,在图的范围上存在局限性,可以进一步考虑图的普遍性。由于图熵的多样性,我们可以进一步探索新的基于距离的图熵,在定义新的图熵的基础上,进一步研究距离熵的基本性质。