基于独立集与匹配数的几乎完全网络熵的度量

A Measure of Almost Complete Network Entropy Based on Independent Sets and Matching

摘要: 为探究边稠密网络的结构复杂性，本文选取基于独立集与匹配数的图熵，在前人探究了完全网络删除至多1条边的基础上，我们延续了他们的工作，研究了完全网络删除至多5条边所得到的几乎完全网络的所有情况，并根据删边数量分类讨论找到了这两类图熵的极值，最后通过数值模拟的方法进行了验证。

Abstract: To explore the structural complexity of edge-dense networks, this paper selects graph entropy based on independent sets and matching numbers. Based on the previous research on deleting at most one edge from a complete network, we continue their work and study all situations of almost complete networks obtained by deleting at most five edges from a complete network. We also discuss and classify them according to the number of deleted edges and find the extreme values of these two types of graph entropy, which are finally verified through numerical simulation.

1. 引言

在当今社会中，复杂网络随处可见。它的复杂性取决于组成该网络的组件之间的相互作用而导致的一系列集体特性的涌现，如何有效度量是目前现代科学的重要挑战之一。Boltzmann [1]最早使用了“信息”的概念，Shannon [2]推广了Boltzmann的熵公式，定义了信息熵。早在20世纪50年代末，Rashevsky [3]和Mowshowitz [4]在研究信息测度的数学性质时就提出了将熵解释为图结构信息内容，后来基于香农熵的经典图熵[2]被用作图复杂度的度量。由于大多数度量都是非常相似的，所以图熵被应用于各个学科上，例如金融分析、交通导航、地质勘探、图像分类等[5]-[9]。因此以图为工具对复杂网络建模，进而研究这个图的拓扑结构复杂性就非常重要。目前有许多度量图和网络复杂性的方法，其中基于信息论及熵的度量应用最广泛[10]。

事实上，图不变量是构建图熵度量的关键因素[11]-[13]。一些图不变量，已经被用来定义图熵测度，例如曹淑娟等人[14]引入的顶点度幂熵I_deg(G)，需要计算图中每个顶点的度；Bonchev等人提出的“基于量级”的信息度量[15]，需要计算距离矩阵的维纳数和特征多项式的最大特征值；基于图的拉普拉斯矩阵的冯·诺依曼熵[16]需要计算矩阵的特征值和特征向量；基于图的闭途径数目的游走熵[17]需要计算邻域矩阵指标的对角线元素和非对角线元素之和；基于信息函数的参数图熵[18]利用局部顶点函数计算每个顶点的概率值来量化结构信息等。据我们所知，Dehmer等人[19] [20]是较早研究图熵问题的人，基于度量性质和其他图不变量定义了各种信息泛函[21]-[24]。因此本文采用的方法是基于Dehmer的信息泛函来研究图熵的测度。

然而，尽管有如此多的熵可以度量网络的结构信息，但还是无法全面系统的表示网络的复杂性，因为不同的熵可能具有完全不同的性质，即还不存在对各种图熵度量上的这些属性的详尽研究。本篇文章使用基于独立集与匹配数的熵来研究完全网络在点保持不变的情况下，删掉至多5条边后得到的所有几乎完全网络，分别对删除相同数量边的所有网络计算两种熵，找到两类熵的极值，总结规律得到结论，最后用数值模拟的方法去验证结果。

2. 预备知识

定义2.1：(Dehmer等[18])设G为图，$f:T\to {ℝ}_{+}$ 是定义在$T=\left\{t_1,t_2,\cdots ,t_k\right\}$ 上的信息泛函，其中T是图G的元素集合，图G的熵定义为：

$\begin{array}{c}{I}_f\left(G\right)=-{\displaystyle \sum _{i=1}^k\frac{f\left(t_i\right)}{{\displaystyle {\sum }_{j=1}^{k}f\left(t_j\right)}}}\log \left(\frac{f\left(t_i\right)}{{\displaystyle {\sum }_{j=1}^{k}f\left(t_j\right)}}\right)\\ =\log \left({\displaystyle {\sum }_{i=1}^{k}f\left(t_i\right)}\right)-\frac{{\displaystyle {\sum }_{i=1}^{k}f\left(t_i\right)}\log \left(f\left(t_i\right)\right)}{{\displaystyle {\sum }_{j=1}^{k}f\left(t_j\right)}}\end{array}$ (1)

其中“log”表示以2为底的对数。

设$G=\left(V,E\right)$ 是简单连通图，我们用n表示顶点的数目，用m表示边的数目。对于图$G=\left(V,E\right)$ ，如果点集合P中的两个顶点在G中不相邻，则称子集$P\subseteq V$ 是独立的，P又叫做G的独立集，用$i_k\left(G\right)$ 表示G中大小为k的独立集的个数，因为空集也被看做是一个独立集，所以$i_0\left(G\right)=1$ 。用$\sigma \left(G\right)$ 表示G中独立集的总个数，可以表达为$\sigma \left(G\right)={\displaystyle {\sum }_{k=0}^n{i}_k\left(G\right)}$ 。而且在数学化学中，它还被称为Merrifield-Simmons指数或$\sigma$ -指数，是拓扑指标中数学性质研究较为详细的指标之一，用于量化分子结构的相关性质。

定义2.2：设G是一个有n个顶点的图。我们用$f:=i_k\left(G\right)$ 定义信息泛函，其中$i_k\left(G\right)$ 表示G中大小为k的独立集的个数，基于G的独立集数或NIS熵，用$I_{nis}\left(G\right)$ 表示，定义为

$\begin{array}{c}{I}_{nis}\left(G\right)=-{\displaystyle \sum _{k=0}^n\frac{i_k\left(G\right)}{\sigma \left(G\right)}}\log \left(\frac{i_k\left(G\right)}{\sigma \left(G\right)}\right)\\ =\log \left(\sigma \left(G\right)\right)-\frac{1}{\sigma \left(G\right)}{\displaystyle \sum _{k=0}^n{i}_k\left(G\right)\cdot \log }\left(i_k\left(G\right)\right)\end{array}$ (2)

设$G=\left(V,E\right)$ 是简单连通图，如果边集合Q中的两条边在G中没有交点，则称子集$Q\subseteq V$ 是匹配的，Q又叫做G的匹配数，用$z_k\left(G\right)$ 表示G中大小为k的匹配的个数，因为空集也被看做是一个匹配数，所以$z_0\left(G\right)=1$ 。用$Z\left(G\right)$ 表示G中独立集的总个数，可以表达为$Z\left(G\right)={\displaystyle {\sum }_{k=0}^n{i}_k\left(G\right)}$ 。在文献[25] [26]中，$Z\left(G\right)$ 称为Hosoya指数或Z-指数，是Merrifield-Simmons指数的边形式，可以作为研究烷烃各种理化性质的指标。

定义2.3：设G是一个有m条边的图。我们用$f:=z_k\left(G\right)$ 定义信息泛函，其中$z_k\left(G\right)$ 表示G中大小为k的匹配的个数，基于G的匹配数或NM熵，用$I_{nm}\left(G\right)$ 表示，定义为

$\begin{array}{c}{I}_{nm}(G)=-{\displaystyle \sum _{k=0}^n\frac{z_k\left(G\right)}{Z\left(G\right)}}\log \left(\frac{z_k\left(G\right)}{Z\left(G\right)}\right)\\ =\log \left(Z\left(G\right)\right)-\frac{1}{Z\left(G\right)}{\displaystyle \sum _{k=0}^n{z}_k\left(G\right)\cdot \log }\left(z_k\left(G\right)\right)\end{array}$ (3)

这两种图熵度量是曹淑娟等人[27]在论文中介绍的。对于完全图和删除一条边得到的几乎完全图，我们有如下引理。

引理2.4：设K_n是n个顶点的完全图，则

$I_{nis}\left(K_n\right)=\log \left(n+1\right)-\frac{n\log n}{n+1}$ (4)

和

$I_{nm}\left(K_n\right)=\log \left(Z\left(K_n\right)\right)-\frac{\left(\begin{array}{c}n\\ 2\end{array}\right)\log \left(\begin{array}{c}n\\ 2\end{array}\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(K_n\right)\right)}\log \left(z_k\left(K_n\right)\right)}{Z\left(K_n\right)}$ (5)

其中$Z\left(K_n\right)=1+{\displaystyle {\sum }_{k=1}^{\lfloor n/2\rfloor }\frac{1}{k!}}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}$ 和$z_k\left(K_n\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}$ 。

引理1.5：(万鹏飞等[28])设G是由K_n删除一条边后得到的图，则

$I_{nis}\left(G\right)=\log \left(n+2\right)-\frac{n\log n}{n+2}$ (6)

和

$I_{nm}\left(G\right)=\log \left(Z\left(G\right)\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-1\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-1\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G\right)\right)}\log \left(z_k\left(G\right)\right)}{Z\left(G\right)}$ (7)

其中$Z\left(G\right)=\frac{n\left(n-1\right)}{2}+{\displaystyle {\sum }_{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G\right)}$ 和$z_k\left(G\right)=\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{2k}-1\right)$ 。

下一章我们将使用这两类图熵对几乎完全网络进行研究，吴廷增等人[29]给出了完全图K_n删除至多5条边的所有可能情况，见图1。

Figure 1. Delete all graphs G_i within five edges of the complete graph K_n, i = 10, 20, …, 525

图1. 完全图K_n删除五条边以内的所有图集G_i，i = 10, 20, …, 525

3. 几乎完全图的NIS和NM熵

在本章中，我们规定对于式子$\frac{1}{\left(k-r\right)!}{\displaystyle {\prod }_{j=1}^{k-r}\left(\begin{array}{c}n-2j+2-2r\\ 2\end{array}\right)}$ 其中$r\in Z$ ，当k取r时上式值为1。

定理3.1：设G是由K_n删除两条边后得到的图，则

(I)

$I_{nis}\left(G_{20}\right)=\log \left(n+3\right)-\frac{n\log n+2}{n+3}$ (8)

和

$I_{nm}\left(G_{20}\right)=\log \left(\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{20}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{20}\right)\right)}\log \left(z_k\left(G_{20}\right)\right)}{\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{20}\right)}}$ (9)

其中$z_k\left(G_{20}\right)=\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{4k}-1\right)$ 。

(II)

$I_{nis}\left(G_{21}\right)=\log \left(n+3\right)-\frac{n\log n+2}{n+3}$ (10)

和

$I_{nm}\left(G_{21}\right)=\log \left(\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{21}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{21}\right)\right)}\log \left(z_k\left(G_{21}\right)\right)}{\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{21}\right)}}$ (11)

其中$z_k\left(G_{21}\right)=\frac{\left(n-4\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k}-\frac{\left(n-2\right)\left(n-3\right)}{k}+1\right)$ 。

证明：无论是情况I还是情况II，由于$i_0\left(G\right)=1$ ，$i_1\left(G\right)=n$ ，$i_2\left(G\right)=2$ ，对于$3\le k\le n$ ，$i_k\left(G\right)=0$ ，我们有$\sigma \left(G\right)=n+3$ 。因此，

$I_{nis}\left(G_{20}\right)=I_{nis}\left(G_{21}\right)=\log \left(n+3\right)-\frac{n\log n+2}{n+3}$

假设G是由K_n删除$e_1,e_2$ 两条边得到的。不难看出对于$1\le k\le \lfloor n/2\rfloor$ ，有$\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}$ 。对于K_n分别包含$e_1,e_2$ 两条边的大小为k > 1的匹配数为$\frac{2}{\left(k-\text{1}\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}$ 。

情况I：当$e_1,e_2$ 两条边有一个公共顶点时，如图1的G₂₀所示，此时删边内部不存在匹配，所以对$2\le k\le \lfloor n/2\rfloor$ ，我们有

$\begin{array}{c}{z}_k\left(G_{20}\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}-\frac{2}{\left(k-1\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}\\ =\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{4k}-1\right)\end{array}$

注意到$z_0\left(G_{20}\right)=1$ ，$z_1\left(G_{20}\right)=\left(\begin{array}{c}2\\ n\end{array}\right)-2$ 这意味着

$Z\left(G_{20}\right)=\frac{\left(n+1\right)\left(n-2\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{4k}-1\right)}$

因此最终的公式为

$I_{nm}\left(G_{20}\right)=\log \left(\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{20}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{20}\right)\right)}\log \left(z_k\left(G_{20}\right)\right)}{\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{20}\right)}}$

情况II：当$e_1,e_2$ 两条边是独立的，如图1的G₂₁所示，此时同时包含这两条边的大小为k > 2的匹配数为$\frac{1}{\left(k-\text{2}\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}$ ，根据容斥原理，对$2\le k\le \lfloor n/2\rfloor$ ，我们有

$\begin{array}{c}{z}_k\left(G_{21}\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}-\frac{2}{\left(k-1\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}+\frac{1}{\left(k-2\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}\\ =\frac{\left(n-4\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k}-\frac{\left(n-2\right)\left(n-3\right)}{k}+1\right)\end{array}$

注意到$z_0\left(G_{21}\right)=1$ ，$z_1\left(G_{21}\right)=\left(\begin{array}{c}2\\ n\end{array}\right)-2$ 这意味着

$Z\left(G_{21}\right)=\frac{\left(n+1\right)\left(n-2\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\frac{\left(n-4\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k}-\frac{\left(n-2\right)\left(n-3\right)}{k}+1\right)}$

因此最终的公式为

$I_{nm}\left(G_{21}\right)=\log \left(\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{21}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-2\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{21}\right)\right)}\log \left(z_k\left(G_{21}\right)\right)}{\frac{\left(n-2\right)\left(n+1\right)}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{21}\right)}}$

定理3.2：设G是由K_n删除三条边后得到的图，则

(I)

$I_{nis}\left(G_{30}\right)=\log \left(n+4\right)-\frac{n\log n+3\log 3}{n+4}$ (12)

和

$I_{nm}\left(G_{30}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{30}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{30}\right)\right)}\log \left(z_k\left(G_{30}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{30}\right)}}$ (13)

其中$z_k\left(G_{30}\right)=\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{2k}-3\right)$ 。

(II)

$I_{nis}\left(G_{31}\right)=\log \left(n+4\right)-\frac{n\log n+3\log 3}{n+4}$ (14)

和

$I_{nm}\left(G_{31}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{31}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{31}\right)\right)}\log \left(z_k\left(G_{31}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{31}\right)}}$ (15)

其中$z_k\left(G_{31}\right)=\frac{\left(n-4\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k\left(k-1\right)}-\frac{3\left(n-2\right)\left(n-3\right)}{2k\left(k-1\right)}+2\right)$ 。

(III)

$I_{nis}\left(G_{32}\right)=\log \left(n+5\right)-\frac{n\log n+3\log 3}{n+5}$ (16)

和

$I_{nm}\left(G_{32}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{32}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{32}\right)\right)}\log \left(z_k\left(G_{32}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{32}\right)}}$ (17)

其中$z_k\left(G_{32}\right)=\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{2k}-3\right)$ 。

(IV)

$I_{nis}\left(G_{33}\right)=\log \left(n+4\right)-\frac{n\log n+3\log 3}{n+4}$ (18)

和

$I_{nm}\left(G_{33}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{33}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{33}\right)\right)}\log \left(z_k\left(G_{33}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{33}\right)}}$ (19)

其中$z_k\left(G_{33}\right)=\frac{\left(n-4\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k\left(k-1\right)}-\frac{3\left(n-2\right)\left(n-3\right)}{2k\left(k-1\right)}+1\right)$ 。

(V)

$I_{nis}\left(G_{34}\right)=\log \left(n+4\right)-\frac{n\log n+3\log 3}{n+4}$ (20)

和

$\begin{array}{l}{I}_{nm}\left(G_{34}\right)=\log \left(\frac{n^6-15n^5+73n^4-9n^3-914n^2+2304n-1152}{48}+{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }{z}_k\left(G_{34}\right)}\right)\\ -\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+z_2\left(G_{34}\right)\log \left(z_2\left(G_{34}\right)\right)+z_3\left(G_{34}\right)\log \left(z_3\left(G_{34}\right)\right)+{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }\left(z_k\left(G_{34}\right)\right)}\log \left(z_k\left(G_{34}\right)\right)}{\frac{n^6-15n^5+73n^4-9n^3-914n^2+2304n-1152}{48}+{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }{z}_k\left(G_{34}\right)}}\end{array}$ (21)

其中$z_2\left(G_{34}\right)=\frac{n^4-6n^3-n^2+54n-48}{8}$ ，$z_3\left(G_{34}\right)=\frac{n^6-15n^5+67n^4+27n^3-932n^2+2004n-768}{48}$ ，$\begin{array}{c}{z}_k\left(G_{34}\right)=\frac{\left(n-6\right)!}{2^{k-3}\left(k-3\right)!\left(n-2k\right)!}(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{8k\left(k-1\right)\left(k-2\right)}\\ -\frac{3\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{4\left(k-1\right)\left(k-2\right)}+\frac{3\left(n-4\right)\left(n-5\right)}{2\left(k-2\right)}-1)\end{array}$ 。

证明：删除三条边一共有5种情况，在所有情况中除了G₃₂以外，都有$i_0\left(G\right)=1$ ，$i_1\left(G\right)=n$ ，$i_2\left(G\right)=3$ ，对于$3\le k\le n$ ，$i_k\left(G\right)=0$ ，我们有$\sigma \left(G\right)=n+4$ 。因此，

$I_{nis}\left(G_{30}\right)=I_{nis}\left(G_{31}\right)=I_{nis}\left(G_{33}\right)=I_{nis}\left(G_{34}\right)=\log \left(n+4\right)-\frac{n\log n+3\log 3}{n+4}$

对于G₃₂，由于其存在3-独立且$i_3\left(G\right)=1$ ，而对于$4\le k\le n$ ，$i_k\left(G\right)=0$ ，所以$\sigma \left(G\right)=n+5$ 。

$I_{nis}\left(G_{32}\right)=\log \left(n+5\right)-\frac{n\log n+3\log 3}{n+5}$

假设G是由K_n删除$e_1,e_2,e_3$ 三条边得到的。显而易见对于$1\le k\le \lfloor n/2\rfloor$ ，有$\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}$ 。对于K_n分别包含$e_1,e_2,e_3$ 三条边的大小为k > 1的匹配数为$\frac{2}{\left(k-\text{1}\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}$ 。

情况I：当删除的是星图S₃时，如图1的G₃₀所示，此时删边内部不存在匹配，因此对2 ≤ k ≤ ⌊n/2⌋，有

$\begin{array}{c}{z}_k\left(G_{30}\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}-\frac{3}{\left(k-1\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}\\ =\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{2k}-3\right)\end{array}$

注意到$z_0\left(G_{30}\right)=1$ ，$z_1\left(G_{30}\right)=\left(\begin{array}{c}2\\ n\end{array}\right)-3$ 这意味着

$Z\left(G_{30}\right)=\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\frac{\left(n-2\right)!}{2^{k-1}\left(k-1\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)}{2k}-3\right)}$

因此最终的公式为

$I_{nm}\left(G_{30}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{30}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{30}\right)\right)}\log \left(z_k\left(G_{30}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{30}\right)}}$

情况II：当删除的有一个公共顶点的两条边和一条独立边时，如图1的G₃₁所示，此时同时包含这两条边的大小为k > 2的匹配数为$\frac{2}{\left(k-\text{2}\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}$ ，根据容斥原理，对$2\le k\le \lfloor n/2\rfloor$ ，我们有

$\begin{array}{c}{z}_k\left(G_{31}\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}-\frac{3}{\left(k-1\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}+\frac{2}{\left(k-2\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}\\ =\frac{\left(n-4\right)!}{2^{k-2}\left(k-2\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k\left(k-1\right)}-\frac{3\left(n-2\right)\left(n-3\right)}{2\left(k-1\right)}+2\right)\end{array}$

注意到$z_0\left(G_{31}\right)=1$ ，$z_1\left(G_{31}\right)=\left(\begin{array}{c}2\\ n\end{array}\right)-3$ ，这意味着

$Z\left(G_{31}\right)=\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\frac{\left(n-4\right)!}{2^{k-2}\left(k-2\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k\left(k-1\right)}-\frac{3\left(n-2\right)\left(n-3\right)}{2\left(k-1\right)}+2\right)}$

因此最终的公式为

$I_{nm}\left(G_{31}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{31}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{31}\right)\right)}\log \left(z_k\left(G_{31}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{31}\right)}}$

情况III：当删除的是长为3的圈时，如图1的G₃₂所示，此时其删边内部也不存在匹配，结果与情况I的一致，所以这里不再赘述。

情况IV：当删除的是路时，如图1的G₃₃所示，此时同时包含这两条边的大小为k > 2的匹配数为$\frac{1}{\left(k-\text{2}\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}$ ，所以对$2\le k\le \lfloor n/2\rfloor$ ，我们有

$\begin{array}{c}{z}_k\left(G_{33}\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}-\frac{3}{\left(k-1\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}+\frac{1}{\left(k-2\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}\\ =\frac{\left(n-4\right)!}{2^{k-2}\left(k-2\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k\left(k-1\right)}-\frac{3\left(n-2\right)\left(n-3\right)}{2\left(k-1\right)}+1\right)\end{array}$

注意到$z_0\left(G_{33}\right)=1$ ，$z_1\left(G_{33}\right)=\left(\begin{array}{c}2\\ n\end{array}\right)-3$ ，这意味着

$Z\left(G_{33}\right)=\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\frac{\left(n-4\right)!}{2^{k-2}\left(k-2\right)!\left(n-2k\right)!}\left(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{4k\left(k-1\right)}-\frac{3\left(n-2\right)\left(n-3\right)}{2\left(k-1\right)}+1\right)}$

因此最终的公式为

$I_{nm}\left(G_{33}\right)=\log \left(\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{33}\right)}\right)-\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }\left(z_k\left(G_{33}\right)\right)}\log \left(z_k\left(G_{33}\right)\right)}{\frac{n^2-n-4}{2}+{\displaystyle \sum _{k=2}^{\lfloor n/2\rfloor }{z}_k\left(G_{33}\right)}}$

情况V：当删除的是三条独立边时，如图1的G₃₄所示，这种情况比前面所有的都要复杂得多，此时同时包含任意两条边的大小为k > 2的匹配数为$\frac{3}{\left(k-\text{2}\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}$ ，同时包含三条边的大小为k > 3的匹配数为$\frac{1}{\left(k-\text{3}\right)!}{\displaystyle {\prod }_{j=1}^{k-3}\left(\begin{array}{c}n-2j-4\\ 2\end{array}\right)}$ ，根据容斥原理，对$4\le k\le \lfloor n/2\rfloor$ ，我们有

$\begin{array}{c}{z}_k\left(G_{34}\right)=\frac{1}{k!}{\displaystyle {\prod }_{j=1}^k\left(\begin{array}{c}n-2j+2\\ 2\end{array}\right)}-\frac{3}{\left(k-1\right)!}{\displaystyle {\prod }_{j=1}^{k-1}\left(\begin{array}{c}n-2j\\ 2\end{array}\right)}\\ +\frac{3}{\left(k-2\right)!}{\displaystyle {\prod }_{j=1}^{k-2}\left(\begin{array}{c}n-2j-2\\ 2\end{array}\right)}-\frac{1}{\left(k-3\right)!}{\displaystyle {\prod }_{j=1}^{k-3}\left(\begin{array}{c}n-2j-4\\ 2\end{array}\right)}\\ =\frac{\left(n-6\right)!}{2^{k-3}\left(k-3\right)!\left(n-2k\right)!}(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{8k\left(k-1\right)\left(k-2\right)}\\ -\frac{3\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{4\left(k-1\right)\left(k-2\right)}+\frac{3\left(n-4\right)\left(n-5\right)}{2\left(k-2\right)}-1)\end{array}$

注意到$z_0\left(G_{34}\right)=1$ ，$z_1\left(G_{34}\right)=\left(\begin{array}{c}2\\ n\end{array}\right)-3$ ，同时对于2-匹配和3-匹配，我们有

$z_2\left(G_{34}\right)=\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{8}-\frac{3\left(n-2\right)\left(n-3\right)}{2}+3=\frac{n^4-6n^3-n^2+54n-48}{8}$

$\begin{array}{c}{z}_3\left(G_{34}\right)=\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{48}-\frac{3\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{8}+\frac{3\left(n-4\right)\left(n-5\right)}{2}-2\\ =\frac{n^6-15n^5+67n^4+27n^3-932n^2+2004n-768}{48}\end{array}$

这意味着

$\begin{array}{c}Z\left(G_{34}\right)=\frac{n^6-15n^5+73n^4-9n^3-914n^2+2304n-1152}{48}\\ +{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }\frac{\left(n-6\right)!}{2^{k-3}\left(k-3\right)!\left(n-2k\right)!}(\frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{8k\left(k-1\right)\left(k-2\right)}}\\ -\frac{3\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)}{4\left(k-1\right)\left(k-2\right)}+\frac{3\left(n-4\right)\left(n-5\right)}{2\left(k-2\right)}-1)\end{array}$

因此最终的公式为

$\begin{array}{l}{I}_{nm}\left(G_{34}\right)=\log \left(\frac{n^6-15n^5+73n^4-9n^3-914n^2+2304n-1152}{48}+{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }{z}_k\left(G_{34}\right)}\right)\\ -\frac{\left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)\log \left(\left(\begin{array}{c}n\\ 2\end{array}\right)-3\right)+z_2\left(G_{34}\right)\log \left(z_2\left(G_{34}\right)\right)+z_3\left(G_{34}\right)\log \left(z_3\left(G_{34}\right)\right)+{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }\left(z_k\left(G_{34}\right)\right)}\log \left(z_k\left(G_{34}\right)\right)}{\frac{n^6-15n^5+73n^4-9n^3-914n^2+2304n-1152}{48}+{\displaystyle \sum _{k=4}^{\lfloor n/2\rfloor }{z}_k\left(G_{34}\right)}}\end{array}$

对于删除四条边的几乎完全图，一共有11种情况，而删除五条边的几乎完全图情况更复杂，有26种。由于证明过程与前面类似，所以这里不再重复证明。通过将删除至多五条边的几乎完全图所有情况的两类熵经过计算后，根据删边的数量分布情况考虑，我们发现当删去长为3的圈时，I_nis的值是最大的，而且删去的长为3的圈数量越多，I_nis的值越大；而对于I_nm的值，当删去的都是独立边时，值是最大的，而当删去的是一个星图时，值是最小的。接下来我将通过数值模拟进一步对发现的规律进行验证。

4. 数值模型

为了保证结果的普遍性，这里我们分别取30个顶点和31个顶点进行模拟，计算结果如表1所示。从表中我们可以看到这两类熵无论奇数顶点还是偶数顶点，在删相同数量边的情况下，它们均有一些共同特征，例如有一些图的熵值是相同的，那是因为它们删边内部都拥有相同的匹配数，这个结果也暗示了它们的复杂度是一样的。另外我们还发现，对于由完全图删除两条边后得到的几乎完全图，显而易见得$I_{nis}\left(G_{20}\right)=I_{nis}\left(G_{21}\right)$ 且$I_{nm}\left(G_{20}\right)<I_{nm}\left(G_{21}\right)$ ；对于由完全图删除三条边后得到的几乎完全图，G₃₂的I_nm值是最大的，其他情况都一样，G₃₀和G₃₂的I_nm值相同，都是最小的，G₃₄的I_nm值最大；对于由完全图删除四条边后得到的几乎完全图，G₄₅和G₄₆的I_nis值相等，都是最大的，其他情况都一样，而G₄₀的I_nm值最小，G₄₉的I_nm值最大；对于由完全图删除五条边后得到的几乎完全图，G₅₁₆的I_nis值是最大的，G₅₉、G₅₁₀、G₅₁₂、G₅₁₃、G₅₁₄、G₅₁₆和G₅₁₈次之，其他情况都一样，而G₅₄的I_nm值最小，G₅₂₁的I_nm值最大。从结果来看，与上一节中得到的结论是一致的。

Table 1. NIS entropy and NM entropy of a complete graph with at most 5 edges deleted

表1. 完全图删至多5条边的NIS熵和NM熵

顶点数	G	Inis	Inm	G	Inis	Inm
30	G20	0.523	58.989	G54	0.758	58.851
	G21	0.523	58.990	G55	0.758	58.858
	G30	0.618	58.944	G56	0.758	58.857
	G31	0.618	58.947	G57	0.758	58.860
	G32	0.788	58.944	G58	0.758	58.861
	G33	0.618	58.946	G59	0.917	58.854
	G34	0.618	58.949	G510	0.917	58.855
	G40	0.695	58.898	G511	0.758	58.861
	G41	0.695	58.903	G512	0.917	58.857
	G42	0.695	58.904	G513	0.917	58.860
	G43	0.695	58.905	G514	0.917	58.861
	G44	0.695	58.901	G515	0.758	58.857
	G45	0.859	58.903	G516	1.016	58.854
	G46	0.859	58.900	G517	0.758	58.861
	G47	0.695	58.903	G518	0.917	58.858
	G48	0.695	58.904	G519	0.758	57.860
	G49	0.695	58.907	G520	0.758	58.858
	G410	0.695	58.901	G521	0.758	58.865
	G50	0.758	58.860	G522	0.758	58.860
	G51	0.758	58.862	G523	0.758	58.858
	G52	0.758	58.864	G524	0.758	58.855
	G53	0.758	57.860	G525	0.758	58.857
31	G20	0.512	61.587	G54	0.745	61.453
	G21	0.512	61.588	G55	0.745	61.460
	G30	0.605	61.543	G56	0.745	61.459
	G31	0.605	61.546	G57	0.745	61.461
	G32	0.772	61.543	G58	0.745	61.463
	G33	0.605	61.545	G59	0.901	61.456
	G34	0.605	61.547	G510	0.901	61.457
	G40	0.682	61.499	G511	0.745	61.463
	G41	0.682	61.503	G512	0.901	61.459
	G42	0.682	61.504	G513	0.901	61.461
	G43	0.682	61.506	G514	0.901	61.463
	G44	0.682	61.502	G515	0.745	61.459
	G45	0.842	61.503	G516	0.998	61.456
	G46	0.842	61.500	G517	0.745	61.463
	G47	0.682	61.503	G518	0.901	61.460
	G48	0.682	61.504	G519	0.745	60.461
	G49	0.682	61.507	G520	0.745	61.460
	G410	0.682	61.502	G521	0.745	61.466
	G50	0.745	61.461	G522	0.745	61.461
	G51	0.745	61.464	G523	0.745	61.460
	G52	0.745	61.465	G524	0.745	61.457
	G53	0.745	61.461	G525	0.745	61.459

5. 讨论

本研究通过系统计算完全图删除至多五条边形成的各类几乎完全网络在独立集熵和匹配数熵上的取值，揭示了删边拓扑结构对这两种熵的显著影响。数值结果清晰地表明，当删除的边构成一个长为3的圈C₃时，I_nis值达到最大；而当删除的边彼此独立时，I_nm值达到最大。相反，删除星形结构S_k会导致I_nm值最小。这些现象的根本原因在于不同删边模式对图中独立集数量分布$i_k\left(G\right)$ 和匹配数数量分布$z_k\left(G\right)$ 产生的迥异影响，其内在机理源于图论中独立集与匹配集的组合性质。

I_nis度量的是图中顶点构成独立集的不确定性，其值依赖于不同大小独立集的数量分布$i_k\left(G\right)$ 。在完全图K_n中，由于所有顶点两两相连，任何大小大于1的独立集都不可能存在。删除边会“解放”顶点间原有的强制性邻接关系，从而产生新的独立集。关键之处在于，删除边所形成的结构决定了哪些新的、更大规模的独立集能够出现。删除一个三角形C₃具有独特的影响是因为它移除了三个顶点之间所有的两两连接，在原始的K_n中，这三个顶点构成的集合不可能是一个大小为3的独立集。因此删除这三条边后，三个顶点变得彼此独立，不再有边相连，从而新增了一个大小为3的独立集，而在删除其他三条边构型如星、路或部分独立边时，通常是不存在大小为3的独立集的。这个新增的高阶独立集显著增加了独立集总数$\sigma \left(G\right)$ ，并改变了$i_k\left(G\right)$ 的分布，使得概率质量向更高的k值分散。根据香农熵的定义，这种分布的分散化会使不确定性增加，从而直接导致I_nis值的增大。删除的三角形数量越多，这种新增高阶独立集的效果叠加，导致$\sigma \left(G\right)$ 进一步增大且分布更分散，因此I_nis值更大。相比之下，删除星形结构S_k仅移除了中心顶点与若干叶子顶点之间的边。虽然这允许中心顶点和叶子顶点之间形成新的大小为2的独立集，但它通常不会产生大小为3或更大的新独立集，因为叶子顶点之间原本就没有边(在K_n中是相连的，但星形删除不涉及这些边)。因此，它对独立集总数$\sigma \left(G\right)$ 的增加以及$i_k\left(G\right)$ 分布分散化的贡献相对较小。

I_nm度量的是图中边构成匹配的不确定性，其值依赖于不同大小匹配的数量分布$z_k\left(G\right)$ 。在完全图K_n中，匹配数分布相对均匀且丰富。删除边会减少图中边的总数，从而减少可能的匹配数量。然而，删边模式的不同决定了$z_k\left(G\right)$ 下降的幅度和模式。删除彼此独立的边的影响最为特殊，虽然移除了这些边本身，但图中剩余的边集仍然非常稠密。更重要的是，移除这些独立边并不破坏其他边之间形成匹配的能力。那些没有被删除的、与这些独立边不相邻的边，仍然可以自由地组合进各种大小的匹配中。在计算包含特定边的匹配时，删除独立边意味着在扣除包含这些被删边的匹配，由于这些被删边之间没有交集，因此需要扣除的项相对较少且互斥性强。这导致对于大小大于1的匹配数$z_k\left(G\right)$ 的下降相对较少，匹配数的分布$z_k\left(G\right)$ 在多个k值上仍然保持较高的数值，分布相对分散，从而导致较高的I_nm。相反，删除一个星形结构S_k具有更强的抑制作用。星形的本质是所有边共享一个公共顶点，在完全图中，包含星形中任意两条边的匹配都是不可能的。因此，在计算K_n的匹配数时，包含星形中两条或更多边的k-匹配($k\ge 2$ 2)原本就不存在。删除星形边后，在计算新的$z_k\left(G\right)$ 时，我们只需要考虑那些包含最多一条被删星边的匹配即可，这相当于在容斥原理的计算中，高阶交集项(同时包含多条被删边)天然为零。其结果就是，删除星形结构主要影响的是低阶匹配，而对于$k\ge 2$ 的$z_k\left(G\right)$ 的影响，相比于删除相同数量的独立边，其下降幅度更大，或者说恢复得更少。这导致匹配数分布$z_k\left(G\right)$ 更加集中于较小的k值，分布的集中化会使得不确定性降低，从而导致I_nm值最小。路P_n或部分相交边的删除情况介于独立边和星形之间，其影响取决于边之间共享顶点的程度，共享顶点越多，对$z_k\left(G\right)$ 的抑制作用越强，熵值相应越低。

综上所述，独立集熵对能产生新的、高阶独立集的删边结构(如C₃)敏感，因为这增加了独立集大小分布的不确定性；而匹配数熵则对删边结构是否破坏边之间自由组合形成较大匹配的能力敏感。删除独立边最大程度地保留了这种组合自由度，因为边之间冲突少，维持了匹配数分布的分散性；而删除共享顶点的边(如星形)则显著限制了边的组合可能性，因为边之间冲突强，导致匹配数分布集中于低阶，从而降低了熵值。这种内在的组合机理深刻揭示了图结构(特别是顶点与边的连接/冲突模式)如何通过影响基本图不变量的数量分布，最终决定了基于信息泛函的图熵度量值。

6. 总结

本文系统研究了完全图K_n分别删除至多5条边后形成的各类几乎完全网络的复杂性度量问题，重点聚焦于基于独立集数的图熵I_nis和基于匹配数的图熵I_nm。通过枚举所有可能的删边构型并精确计算其熵值，我们不仅确定了在删除相同数量边的情况下这两类熵的极值点，更重要的是，深入揭示了导致这些极值现象产生的内在组合机理，并用数值模拟结果有力地验证了这些理论发现和机理分析。我们的核心发现表明，网络的熵值强烈依赖于被删除边集所形成的拓扑结构。对于匹配熵，当删星图时，熵值是最小的；而当删独立边时，熵值是最大的。因为在任何n阶的非空图中，大小为0和1的独立集和匹配集的个数都是确定的，星图只有0-匹配和1-匹配，即在完全图中不存在同时包含星图两条边的k > 2的匹配数，所以我们在计算时只需考虑在完全图中包含星图一条边的k > 1的匹配数即可，熵值自然也会比较小；相反地，独立边的匹配数最多可以计算到它的边数大小，所以根据容斥原理它的匹配数要比其他同构图形要多，熵值自然也会大一些。独立熵也是如此，之所以删除长为3的圈熵值最大是因为C₃可以看成是顶点数为3的完全图，而完全图的独立集是最多的，熵值也会比较大。因此熵值高的图总是有更多大小大于1的独立集和匹配集。

一个完整的网络是由无数的节点和边构成的。I_nis用于度量节点独立的不确定性，但是对于有相同节点数但边数不相同的网络来说，I_nis值可能是相同的，导致无法确定网络的结构信息；而I_nm用于度量边匹配的不确定性，刚好可以对I_nis进行互补，在I_nis值相同的情况下，比较I_nm值来确定网络的结构特征。例如G₃₀和G₃₁的I_nis值就是一样的，此时我们就无法判断网络的结构，而G₃₁的I_nm值要比G₃₀的要大，所以我们就可以判断出G₃₁的网络结构更复杂。但这些结论是否还适合现有的其它图熵我们还不得而知，所以未来可以加入其他图熵进行比较，看是否能得到相同或者相似的结论，用更一般的规律来刻画网络熵的极值图形将是一个很有趣的事情。

基金项目

青海民族大学研究生创新项目《一些复杂网络熵的计算研究》。项目编号：07M2024016。