给定图的距离熵及其应用
Distance Entropy of a Given Graph and Its Application
DOI: 10.12677/orf.2024.143368, PDF, HTML, XML, 下载: 34  浏览: 79 
作者: 杨 晨, 魏远振, 赵渭娟:青海师范大学数学与统计学院,青海 西宁;刘婷婷:宝鸡文理学院数学与信息科学学院,陕西 宝鸡
关键词: 图熵距离熵化学树图运算Graph Entropy Distance Entropy Chemical Tree Graph Operation
摘要: 图熵是图的信息理论测度,近年来,图熵慢慢成为测量图的结构信息测度的载体,距离是最重要的图不变量之一。本文主要研究了树和化学树的距离熵及其相关应用,并且研究了给定图在笛卡尔积、强积和冠积运算下的距离熵值。
Abstract: Graph entropy is the information theory measure of graphs. In recent years, graph entropy has gradually become the carrier to measure the structure information of graphs, and distance is one of the most important graph invariants. In this paper, we mainly study the range entropy of tree and chemical tree and its related applications, and study the range entropy of given graph under Cartesian product, strong product and crown product operations.
文章引用:杨晨, 魏远振, 赵渭娟, 刘婷婷. 给定图的距离熵及其应用[J]. 运筹与模糊学, 2024, 14(3): 1389-1396. https://doi.org/10.12677/orf.2024.143368

1. 引言

图熵是图的信息理论度量,近年来,图熵慢慢成为测量图的结构信息测度的载体,引出了许多基于不同信息函数的图熵,图熵的研究也取得了丰富的成果。图熵作为图的不变量研究的一个重要方向,在信息论、生物学等领域都引起广泛关注。Chen等人在文献[1]中提出了距离熵的概念,并研究了距离等于2时树的熵及其相关性质,本文在文献[1]的基础上,主要研究了距离等于3时给定图的距离熵。Shannon在文献[2]中提出信息熵这个概念,并证明了香农熵的许多重要理论。文献[1] [3]主要探索了基于新的信息函数,即到给定顶点的距离为k的顶点数的图熵,描述了测量图熵的方法,并给出距离熵的一些性质。文献[4] [5]通过使用基于拓扑指数的图距离测度不等式推导了图距离测度的相互关系,研究了基于G的顶点离心率的新图熵。文献[6] [7]研究对于具有固定阶数和给定分支顶点或段数的树和 n7 的化学树 C T n ,给出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. 预备知识

本文所提到的图均是无自环、无孤立顶点、无重边的简单无向连通图。设 G=( V,E ) 是一个简单连通图,其顶点集为 V( G ) ,边集为 E( G ) 。已知与一个顶点v相邻的所有顶点称为v的邻域,顶点 vV( G ) 的邻集用 N G ( v )={ w| wvE } 表示, N G [ v ]={ v } N G ( v ) 表示G中顶点v的闭邻集。对于图 G=( V,E ) ,如果S的两个顶点在G中不相邻,则子集 SV 称为G的独立集,空集是独立集。G中顶点uv的距离用 d G ( u,v ) 表示,简记为 d( u,v ) G中顶点u的度用 d G ( u ) 表示,简记为 d( u ) 。本文所给出的对数log均时以2为底数的。

在下文中,我们通过使用基本公式来定义新的图熵测度

I( G )= i=1 | V | p i log p i

其中 p i 是顶点概率。我们定义 v i V 的顶点概率值为

p( v i ):= f( v i ) j=1 | V | f( v j ) .

G的熵由Dehmer [3]定义为

I f ( G )=log( i=1 | V | f( v i ) ) i=1 | V | f( v i ) j=1 | V | f( v j ) log( f( v i ) ).

距离是最重要的图不变量之一,接下来我们定义一个新的基于距离的信息泛函。

定义1 [1] G=( V,E ) 是有n个顶点的连通图,对于顶点 v i V ,用 n k ( v i ) 表示距离k v i 的顶点数,

n k ( v i )=| S k ( v i ,G ) |=| { u:d( u, v i )=k,uV( G ) } |

其中k是一个整数,使得 1kD( G ) 。我们定义信息泛函为 f( v i ):= n k ( v i )

因此,我们得到了基于距离的图熵

I k ( G )= I f ( G )=log( i=1 n n k ( v i ) ) i=1 n n k ( v i ) log n k ( v i ) j=1 n n k ( v j ) .

定理1 [7]G是顶点集为 { v 1 , v 2 ,, v n } ,边集为 { e 1 , e 2 ,, e m } 的简单连通图,那么有 I 3 ( G )logn

证明 令 n 3 ( v i )= x i i=1 n x i =A 。则有 I 3 ( G )=logX 1 X i=1 n x i log x i 。考虑函数 f( x )=xlogx ,由于 f( x ) 是凸函数,故 f ( x )= 1 x >0 。我们有詹森不等式 i=1 n f( x i ) f( i=1 n x i ) 可得, logX 1 X i=1 n f( x i ) logX 1 X nf( 1 n i=1 n x i ) ,化简可得 1 n i=1 n x i log x i i=1 n x i log( 1 n i=1 n x i )= i=1 n x i n ( log i=1 n x i logn ) ,通过计算得到 I 3 ( G )=logX 1 X i=1 n x i log x i logn 。定理得证,等式成立当且仅当 x 1 = x 2 == x n

3. 树和化学树的距离熵

在本节中,分别给出了树和化学树距离熵的计算公式,以及树和化学树的相关定理。

3.1. 树T

p k 为图G中长度为k的路径个数,由于每条长度为k的路径在 i=1 n n k ( v i ) 中计算了两次,所以 i=1 n n k ( v i )=2 p k

由于 k=1,2 时的情况在文献中已经给,因此我们考虑 k=3 的情形。由定义1可得 I 3 ( G )= I f ( G )=log( 2 p 3 ( G ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 p 3 ( G )

Wiener极性指数是一类代数拓扑指数,主要描述了图G中距离为3的无序顶点对的个数,即 W p ( G )=| { ( u,v )| d G ( u,v )=3,u,vV( G ) } |

定义2 [6] T=( V,E ) n阶树, W p ( T )= p 3 ( T )= uvE ( d T ( u )1 ) ( d T ( v )1 ) i=1 n n 3 ( v i ) =2 p 3 ( T ) 。其中 d G ( v )=| N G ( v ) | N G i ( v )={ uV( G )| d( u,v )=i }

所以, k=3 时, I 3 ( T ) 的熵为

I 3 ( T )=log( 2 uvE ( d T ( u )1 ) ( d T ( v )1 ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 uvE ( d T ( u )1 ) ( d T ( v )1 ) .

如果 T S n ,那么 I 3 ( S n )=0

如果 T P n ,那么 I 3 ( P n )=log( 2( n3 ) ) ( n6 )2log2 2( n3 ) =log( n3 )+ 3 n3

3.2. 化学树

ϒ n 为有n个顶点的化学树(即每个顶点的度最多为4的树)的集合[7]。其顶点序列为 ( n 1 , n 2 , n 3 , n 4 ) ,其中 n i T的度为i顶点个数 ( 1i4 ) 。其中 n 1 + n 2 + n 3 + n 4 =n, n 1 +2 n 2 +3 n 3 +4 n 4 =2n2

然后,我们引入一种图变换[1],即 T =Tu+uv ,其中w是树T的最大度,u是与w不相邻的叶子,v是与w相邻的叶子。

我们将利用这种图变换证明下述定理。

定理2 T ϒ n ( n5 ) 是一个化学树,其顶点序列为 ( n 1 , n 2 , n 3 , n 4 ) ,则存在树T经过上述图变换得到的 T ϒ n ,使得 I 3 ( T )= I 3 ( T )

证明 根据定义2,有 W p ( T )= p 3 ( T )= uvE ( d T ( u )1 ) ( d T ( v )1 ) ,因此我们可以得到 W p ( T )= p 3 ( T )= W p ( T )= p 3 ( T ) ,现在我们只需考虑 i=1 n n 3 ( v i ) log n 3 ( v i ) ,对于给定的化学树T,我们定义一个序列 s( n 3 ,T )=( n 3 ( v 1 ), n 3 ( v 2 ),, n 3 ( v n ) ) ,由于在T上进行上述变换得到了 T ϒ n ,经过计算可以得到 s( n 3 ,T )=s( n 3 , T ) ,故由定义3可得 I 3 ( T )= I 3 ( T ) ,证毕。

4. 一些图的距离熵

在本节中,分别给出了5种特殊图在笛卡尔积、强积、冠积下的距离熵。

定理3 C 6 K 2 分别为有6个顶点的单圈图和有2个顶点的完全图,则在笛卡尔积运算下得到的新图为 C 6 × K 2 ,如图1,则有 I 3 ( C 6 × K 2 )=log2log3

证明 首先求出

p 3 ( C 6 × K 2 )=| { v 1 , v 4 },{ v 1 , v 11 },{ v 1 , v 9 },{ v 2 , v 5 },{ v 2 , v 10 },{ v 2 , v 8 }, { v 3 , v 6 },{ v 3 , v 9 },{ v 3 , v 7 },{ v 4 , v 12 },{ v 4 , v 8 },{ v 5 , v 11 }, { v 5 , v 7 },{ v 6 , v 12 },{ v 6 , v 10 },{ v 7 , v 10 },{ v 8 , v 11 }, { v 9 , v 12 }| =18,

所以 i=1 12 n 3 ( v i )=2 p 3 ( C 6 × K 2 )=36 。考虑 i=1 n n 3 ( v i ) log n 3 ( v i )

n 3 ( v 1 )=| S 3 ( v 1 , C 6 × K 2 ) |=| { u| d( v 1 ,u )=3 },uV( C 6 × K 2 ) |=| { v 4 , v 9 , v 11 } |=3,

n 3 ( v 2 )=| S 3 ( v 2 , C 6 × K 2 ) |=| { u| d( v 2 ,u )=3 },uV( C 6 × K 2 ) |=| { v 5 , v 8 , v 10 } |=3,

依次类推,可以得到 n 3 ( v 1 )= n 3 ( v 2 )== n 3 ( v 12 )=3 。所以我们得到

I 3 ( C 6 × K 2 )=log( 2 p 3 ( C 6 × K 2 ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 p 3 ( C 6 × K 2 ) =log( 218 ) 123log3 218 =log2log3.

证毕。

定理4 P 2 P 4 分别为有2个顶点的路图和有4个顶点的路图,则在强积运算下得到的新图为 P 2 P 4 ,如图1,则有 I 3 ( P 2 P 4 )=2log2

证明 首先求出

p 3 ( P 2 P 4 )=| { v 1 , v 4 },{ v 1 , v 5 },{ v 4 , v 8 },{ v 5 , v 8 } |=4,

所以 i=1 8 n 3 ( v i )=2 p 3 ( P 2 P 4 )=8 。考虑 i=1 n n 3 ( v i ) log n 3 ( v i )

n 3 ( v 1 )=| S 3 ( v 1 , P 2 P 4 ) |=| { u| d( v 1 ,u )=3 },uV( P 2 P 4 ) |=| { v 4 , v 5 } |=2,

n 3 ( v 2 )=| S 3 ( v 2 , P 2 P 4 ) |=| { u| d( v 2 ,u )=3 },uV( P 2 P 4 ) |=0= n 3 ( v 3 ),

依次类推,可以得到

n 3 ( v 1 )= n 3 ( v 4 )= n 3 ( v 5 )= n 3 ( v 8 )=2, n 3 ( v 2 )= n 3 ( v 3 )= n 3 ( v 6 )= n 3 ( v 7 )=0.

所以我们得到

I 3 ( P 2 P 4 )=log( 2 p 3 ( P 2 P 4 ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 p 3 ( P 2 P 4 ) =log( 24 ) 42log2 24 =2log2.

证毕。

Figure 1. The order is C 6 × K 2 , P 2 P 4 , C 4 K 2 ,R

1. 依次为 C 6 × K 2 , P 2 P 4 , C 4 K 2 ,R

定理5 C 4 K 2 分别为有4个顶点的单圈图和有2个顶点的完全图,则在冠积运算下得到的新图为 C 4 K 2 ,如图1,则有

I 3 ( C 4 K 2 )= 23 6 log2+log3 5 6 log5.

证明 首先求出

p 3 ( C 4 K 2 )=| { v 1 , v 9 },{ v 1 , v 10 },{ v 2 , v 11 },{ v 2 , v 12 },{ v 3 , v 5 },{ v 3 , v 6 }, { v 4 , v 7 },{ v 4 , v 8 },{ v 5 , v 7 },{ v 5 , v 8 },{ v 5 , v 11 },{ v 5 , v 12 }, { v 6 , v 7 },{ v 6 , v 8 },{ v 6 , v 11 },{ v 6 , v 12 },{ v 7 , v 9 },{ v 7 , v 10 }, { v 8 , v 9 },{ v 8 , v 10 },{ v 9 , v 11 }{ v 9 , v 12 },{ v 10 , v 11 }, { v 10 , v 12 }| =24,

所以 i=1 12 n 3 ( v i )=2 p 3 ( C 4 K 2 )=48 。考虑 i=1 n n 3 ( v i ) log n 3 ( v i )

n 3 ( v 1 )=| S 3 ( v 1 , C 4 K 2 ) |=| { u| d( v 1 ,u )=3 },uV( C 4 K 2 ) |=| { v 9 , v 10 } |=2,

n 3 ( v 2 )=| S 3 ( v 2 , C 4 K 2 ) |=| { u| d( v 2 ,u )=3 },uV( C 4 K 2 ) |=| { v 11 , v 12 } |=2,

依次类推,可以得到

n 3 ( v 1 )= n 3 ( v 2 )= n 3 ( v 3 )= n 3 ( v 4 )=2,

n 3 ( v 5 )= n 3 ( v 6 )= n 3 ( v 7 )= n 3 ( v 8 )= n 3 ( v 9 )= n 3 ( v 10 )= n 3 ( v 11 )= n 3 ( v 12 )=5.

所以我们得到

I 3 ( C 4 K 2 )=log( 2 p 3 ( C 4 K 2 ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 p 3 ( C 4 K 2 ) =log( 224 ) 42log2+85log5 224 = 23 6 log2+log3 5 6 log5.

证毕。

定理6 Q 3 为3个 K 2 完全图作笛卡尔积得到的3超维立方体,如图1,则有 I 3 ( Q 3 )=3log2

证明 首先求出

p 3 ( Q 3 )=| { v 1 , v 8 },{ v 2 , v 7 },{ v 3 , v 6 },{ v 4 , v 5 } |=4,

所以 i=1 8 n 3 ( v i )=2 p 3 ( Q 3 )=8 。考虑 i=1 n n 3 ( v i ) log n 3 ( v i )

n 3 ( v 1 )=| S 3 ( v 1 , Q 3 ) |=| { u| d( v 1 ,u )=3 },uV( Q 3 ) |=| { v 8 } |=1,

n 3 ( v 2 )=| S 3 ( v 2 , Q 3 ) |=| { u| d( v 2 ,u )=3 },uV( Q 3 ) |=| { v 7 } |=1,

依次类推,可以得到 n 3 ( v 1 )= n 3 ( v 2 )== n 3 ( v 12 )=1 。所以我们得到

I 3 ( Q 3 )=log( 2 p 3 ( Q 3 ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 p 3 ( Q 3 ) =log( 24 ) 81log1 24 =3log2.

证毕。

定理7 R= P 3 × C 3 为一个 C 4 -纳米管,如图1,则有

I 3 ( R )=log2+log3.

证明 首先求出

p 3 ( R )=| { v 1 , v 8 },{ v 1 , v 9 },{ v 2 , v 7 },{ v 2 , v 9 },{ v 3 , v 7 },{ v 3 , v 8 } |=6,

所以 i=1 9 n 3 ( v i )=2 p 3 ( R )=12 。考虑 i=1 n n 3 ( v i ) log n 3 ( v i )

n 3 ( v 1 )=| S 3 ( v 1 ,R ) |=| { u| d( v 1 ,u )=3 },uV( R ) |=| { v 8 , v 9 } |=2,

n 3 ( v 2 )=| S 3 ( v 2 ,R ) |=| { u| d( v 2 ,u )=3 },uV( R ) |=| { v 7 , v 9 } |=2,

依次类推,可以得到 n 3 ( v 1 )= n 3 ( v 2 )= n 3 ( v 3 )= n 3 ( v 7 )= n 3 ( v 8 )= n 3 ( v 9 )=2 n 3 ( v 4 )= n 3 ( v 5 )= n 3 ( v 6 )=0 。所以我们得到

I 3 ( R )=log( 2 p 3 ( R ) ) i=1 n n 3 ( v i ) log n 3 ( v i ) 2 p 3 ( R ) =log( 26 ) 62log2 26 =log2+log3.

证毕。

5. 总结

本文通过香农熵来研究给定图的距离熵,主要研究树和化学树的距离熵及其相关性质,并且研究了给定图在笛卡尔积、强积和冠积运算下的距离熵。本文的主要贡献是探索一个新的信息泛函,即给定一个顶点到其他顶点的距离为3的顶点个数,研究了它的一些计算公式和相关应用,从而更好地理解这个新的信息论量。本文主要考虑给定图基于距离的图熵及其相关性质,在图的范围上存在局限性,可以进一步考虑图的普遍性。由于图熵的多样性,我们可以进一步探索新的基于距离的图熵,在定义新的图熵的基础上,进一步研究距离熵的基本性质。

参考文献

[1] Chen, Z., Dehmer, M. and Shi, Y. (2014) A Note on Distance-Based Graph Entropies. Entropy, 16, 5416-5427.
https://doi.org/10.3390/e16105416
[2] Shannon, C.E. (1948) A Mathematical Theory of Communication. Bell System Technical Journal, 27, 379-423.
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x
[3] Dehmer, M. and Mowshowitz, A. (2011) A History of Graph Entropy Measures. Information Sciences, 181, 57-78.
https://doi.org/10.1016/j.ins.2010.08.041
[4] Ghorbani, M., Dehmer, M. and Zangi, S. (2018) Graph Operations Based on Using Distance-Based Graph Entropies. Applied Mathematics and Computation, 333, 547-555.
https://doi.org/10.1016/j.amc.2018.04.003
[5] Dong, Y. and Cambie, S. (2022) On the Main Distance-Based Entropies: The Eccentricity-and Wiener-Entropy. arXiv Preprint arXiv:2208.12209
[6] Noureen, S., Bhatti, A.A. and Ali, A. (2021) A Note on the Minimum Wiener Polarity Index of Trees with a Given Number of Vertices and Segments or Branching Vertices. Discrete Dynamics in Nature and Society, 2021, Article ID: 1052927.
https://doi.org/10.1155/2021/1052927
[7] Ali, A., Du, Z. and Ali, M. (2018) A Note on Chemical Trees with Minimum Wiener Polarity Index. Applied Mathematics and Computation, 335, 231-236.
https://doi.org/10.1016/j.amc.2018.04.051
[8] Dehmer, M., Emmert-Streib, F. and Shi, Y. (2014) Interrelations of Graph Distance Measures Based on Topological Indices. PLOS ONE, 9, e94985.
https://doi.org/10.1371/journal.pone.0094985
[9] Deng, H. (2011) On the Extremal Wiener Polarity Index of Chemical Trees. MATCH Communications in Mathematical and in Computer Chemistry, 66, 305-314.
[10] Yue, J., Lei, H. and Shi, Y. (2018) On the Generalized Wiener Polarity Index of Trees with a Given Diameter. Discrete Applied Mathematics, 243, 279-285.
https://doi.org/10.1016/j.dam.2018.02.003
[11] Liu, B., Hou, H. and Huang, Y. (2010) On the Wiener Polarity Index of Trees with Maximum Degree or Given Number of Leaves. Computers & Mathematics with Applications, 60, 2053-2057.
https://doi.org/10.1016/j.camwa.2010.07.045
[12] Deng, H. and Xiao, H. (2010) The Maximum Wiener Polarity Index of Trees with k Pendants. Applied Mathematics Letters, 23, 710-715.
https://doi.org/10.1016/j.aml.2010.02.013
[13] Khalifeh, M.H., Yousefi-Azari, H. and Ashrafi, A.R. (2008) The Hyper-Wiener Index of Graph Operations. Computers & Mathematics with Applications, 56, 1402-1407.
https://doi.org/10.1016/j.camwa.2008.03.003
[14] Yero, I.G. and Rodríguez-Velázquez, J.A. (2011) On the Randić Index of Corona Product Graphs. ISRN Discrete Mathematics, 2011, Article ID: 262183.
https://doi.org/10.5402/2011/262183
[15] Dehmer, M., Varmuza, K., Borgert, S. and Emmert-Streib, F. (2009) On Entropy-Based Molecular Descriptors: Statistical Analysis of Real and Synthetic Chemical Structures. Journal of Chemical Information and Modeling, 49, 1655-1663.
https://doi.org/10.1021/ci900060x
[16] Imrich, W., Klavžar, S. and Hammack, R.H. (2000) Product Graphs: Structure and Recognition. John Wiley & Sons Ltd.
[17] Dobrynin, A.A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Applications. Acta Applicandae Mathematicae, 66, 211-249.
https://doi.org/10.1023/a:1010767517079
[18] Hrinakova, K., et al. (2014) A Congruence Relation for the Wiener Index of Graphs with a Tree-Like Structure. MATCH Communications in Mathematical and in Computer Chemistry, 72, 791-806.
[19] Ma, J., Shi, Y. and Yue, J. (2014) On the Extremal Wiener Polarity Index of Unicyclic Graphs with a Given Diameter. In: Gutman, I., Ed., Topics in Chemical Graph Theory, Mathematical Chemistry Monographs, University of Kragujevac and Faculty of Science Kragujevac, 177-192.
[20] Liu, M. and Liu, B. (2011) On the Wiener Polarity Index. MATCH Communications in Mathematical and in Computer Chemistry, 66, 293-304.
[21] Ma, J., Shi, Y., Wang, Z. and Yue, J. (2016) On Wiener Polarity Index of Bicyclic Networks. Scientific Reports, 6, Article No. 19066.
https://doi.org/10.1038/srep19066