限制匹配数的k一致超树色熵极值

The Chromatic Entropy of a k-Uniform Hypertrees with Restricted Matching Number

摘要: 图熵被广泛地应用于表征图的系统结构的领域。图熵可以反映出图的不同的结构信息，还能反映出图的不同的复杂性度量。在物理，化学和医学等领域有着重要作用。超图作为普通图的一种推广，对于更加复杂的图结构能够更好的表现出关键信息，比如复杂网络等。自然而言，我们可以考虑将图熵推广到超图上，考虑基于超图的顶点染色的图熵，将超图顶点染色和图熵结合起来，得到更加复杂的色熵问题，为色熵问题在以后的研究中奠定了基础。本文主要研究了在限制最大匹配数的情况下，得到了k一致超树的色熵极值大小和极值图结构，并给出了相应的图。

Abstract: Graph entropy is widely applied in the field of characterizing the system structure of graphs. It can reflect different structural information and various complexity measures. It plays an important role in physics, chemistry, medicine and other fields. As a generalization of ordinary graphs, hypergraphs can better represent key information for more complex graph structures, such as complex networks. Naturally, we can consider extending graph entropy to hypergraphs, and consider the graph entropy based on vertex coloring of hypergraphs, combining hypergraph vertex coloring and graph entropy to obtain more complex chromatic entropy problems, providing a more long-term problem for chromatic entropy problems. This paper mainly studies the extremal values and extremal graph structures of chromatic entropy of k-uniform hypertrees under the condition of fixed maximum matching number, and gives the corresponding graphs.

1. 引言

超图作为普通图的一般推广，在二十世纪六十年代，Berge提出超图的概念，随后越来越多有关超图的研究结果被学者们呈现出来，说明超图理论在图论及应用方面的研究是很普遍的。同时，超图更能表示出复杂结构模型的一般关系。

对于图熵的理论研究而言，研究的内容十分广泛。比如，研究不同图熵之间的内在联系、研究某一类图熵的测量方法、研究某一种图熵的性质以及图熵的极值和所对应的极图等。这些研究对于解决复杂网络以及其它领域的一些问题提供了十分有效的数学工具。目前关于图熵的分类主要分为两大类，第一类是根据概率分布，分为参数图熵和经典图熵；第二类是根据熵函数，分为香农熵、冯诺依曼熵、广义熵。本文研究的基于超图顶点染色的色熵属于经典图熵。

图熵作为一种重要的结构信息度量工具，超图与熵的结合使得普通图的图熵更加一般化，但是由于超图的结构更加复杂，所以目前为止对于超图熵的研究相较于普通图的图熵更少。超图色熵作为图熵的一种，它也是由普通图的色熵推广而来的。Mowshowitz [1]提出基于图顶点的色熵，给出了色熵与色数、顶点的度的关系，研究了图运算下色熵与色数的关系。Cardinal等人[2]证明了即使给出最小染色数，平面图的最小色熵也很难计算。Cardinal和Fiorini等人[3]证明了普通图的最小色熵问题是NP-困难的。研究了最小色熵的界的问题。进一步结合Books定理优化了色数与最大度顶点关系。Fang和Deng等人[4]结合超图染色与图熵进行研究，给出了基于超图顶点染色的色熵的定义，并且刻画了基于超图顶点强染色和弱染色的k一致超图色熵的上下界和极图，通过数据验证了结论，获得了图运算下的色熵不等式。Fu等人[5]根据超图顶点强染色的定义以及色熵的定义，获得了k一致超树的极值和极图结构。并定义了一种超树状大分子结构。

超图的色熵定义是在顶点强染色的基础下进行计算的，对同样染色的顶点进行归类划分，其本质是对顶点进行划分，得到顶点集。色熵定义是根据顶点的划分的色信息熵的一种形式。用来衡量图的拓扑结构本身所蕴含的确定性和有序性，寻找出最优划分来量化图本身的内在秩序。计算出色熵的值越小，表明存在一个划分使得顶点集的分布非常不均匀，意味着图的内在结构性越强。值越大，说明图越接近一个无结构的随机集合。

超图$H=\left(V,E\right)$ 是一个二元集，其中超图H的顶点集用$V\left(H\right)$ 表示，且$V\left(H\right)$ 是一个有限集合，超图H的超边集用$E\left(H\right)$ 表示，且$E\left(H\right)$ 是一个非空集合。如果超图$H=\left(V,E\right)$ 中有n个顶点，m条边，对于任意的一条超边$e_i$ ，$e_i\in E\left(H\right)$ ，都有$\left|e_i\right|=k$ ，$i=1,2,\cdots ,m$ ，那么就称超图H是k-一致超图。超图H中任意一个顶点的度数表示该顶点所在超边的基数，如果某个顶点的度数为1，那么就称它是悬挂点，否则就是非悬挂点。如果超图中的某条超边恰好只包含一个非悬挂点，而该超边中的其余顶点均为悬挂点，那么就称该超边为悬挂边。

超图$H=\left(V,E\right)$ 有n个顶点，m条边，设$k>2$ ，并且k是一个正整数。如果超图H中的所有顶点能用k种颜色进行染色，同时，超边中的每个顶点只能染一种颜色且每条超边中都至少包含两种颜色，那么就称超图H是k-正常染色的。如果超图H的每一条基数大于1的超边中的同一种颜色出现的次数不超过一次，那么就称超图是强染色的。超图中顶点的强染色的色数用$\chi \left(H\right)$ 表示，即至少用$\chi \left(H\right)$ 种颜色就能对超图中所有的顶点进行强染色。如果对超图H中的所有顶点进行染色c，那么就得到超图的顶点集合的一个划分$\left(V_1,V_2,\cdots ,V_K\right)$ ，则称$\left(V_1,V_2,\cdots ,V_K\right)$ 是超图的一个染色分解序列，用符号${\pi }_c\left(H\right)$ 表示，即$\left(\left|V_1\right|,\left|V_2\right|,\cdots ,\left|V_K\right|\right)$ 。为了研究方便，通常会对染色分解序列进行排序，定义为非递增序列或者非递减序列，即$\left|V_1\right|>\left|V_2\right|>\cdots >\left|V_K\right|$ 或者$\left|V_1\right|<\left|V_2\right|<\cdots <\left|V_K\right|$ 。

超图的结构复杂且种类繁多，因此对于超图的染色也有很多种，超图的染色是近年来研究的活跃课题之一。基于超图顶点染色的色熵是由Fang等人[4]提出，文献[6]中的对限制匹配数条件研究边数量，文献[7]中研究了关于图的完美匹配问题。对本文对超图进行参数条件限制，添加了图的参数最大匹配数，得到了基于超图顶点的强染色下的限制最大匹配数的k一致超图的极值与极图。

定义1 [4]设超图$H=\left(V\left(H\right),E\left(H\right)\right)$ 有n个顶点，m条边，且$V\left(H\right)=\left(V_1,V_2,\cdots ,V_K\right)$ 是超图H的任意一个染色分解序列，同时$\chi \left(H\right)=k$ ，则基于超

图H顶点强染色的图熵$I_c\left(H\right)$ 称为超图的色熵，定义如下：

$\begin{array}{c}{I}_c\left(H\right)=\underset{\widehat{V}}{\min }\left\{-{\displaystyle \sum _{i=1}^k\frac{\left|V_i\right|}{n}\log }\frac{\left|V_i\right|}{n}\right\}\\ =\log n-\underset{\widehat{V}}{\max }\left\{\frac{1}{n}{\displaystyle \sum _{i=1}^k\left|V_i\right|\log }\left|V_i\right|\right\}.\end{array}$

假设$f\left(H\right)=\underset{\widehat{V}}{\max }{\displaystyle \sum _{i=1}^k\left|V_i\right|}\log \left|V_i\right|$ ，则$I_c\left(H\right)=\log n-\frac{f\left(H\right)}{n}$ 。

2. 主要结果

本文的主要结果是通过结合图最大匹配数的定义以及分析超树色熵的特点，在限制最大匹配数的情况下得到了超图顶点强染色的色熵极值以及对应的极值图。

Figure 1. A k-uniform hypertree with a superstar

图1. 带有超星的k一致超树

定义2 [8]超图H中两两不相交的边集成为匹配。H中的最大匹配边数记作$\nu \left(H\right)$ ，称为匹配数。

定义3 令$H\left(m,k,p\right)$ 是有m条边的最大匹配数为p的k一致超树。假设所有此类的超树构成的集合用$\mathscr{H}\left(m,k,p\right)$ 表示，即$H\left(m,k,p\right)\in \mathscr{H}\left(m,k,p\right)$ 。

定义4 令$H_s\left(m,k,p\right)\in \mathscr{H}\left(m,k,p\right)$ 。超图$H_s\left(m,k,p\right)$ 由一条超路和一个超星构成，且满足超星连接在超路的最左边或者最右边的其中一个顶点，那么就称超图$H_s\left(m,k,p\right)$ 为超彗星，如图1所示。

定义5 [5]对于任意的$T_{n,k}\in {\mathcal{T}}_{n,k}$ ，其中$T_{n,k}$ 是有n个顶点的线性k-一致超树。有$I_c\left(T_{n,k}\right)\ge \log n-\frac{m\left(k-1\right)\log m}{n}$ ，其中$m=\frac{n-1}{k-1}$ ，等式成立当且仅当$T_{n,k}\cong S_n^k$ 。

定义6 [5]对于任意的$T_{n,k}\in {\mathcal{T}}_{n,k}$ ，有

$I_c\left(T_{n,k}\right)\le \log n-\frac{1}{n}\left[a\lceil \frac{n}{k}\rceil \log \lceil \frac{n}{k}\rceil +\left(k-a\right)\left[\frac{n}{k}\right]\log \left[\frac{n}{k}\right]\right]$ ,

其中$a=n-k\lfloor \frac{n}{k}\rfloor$ ，并且不等式成立当且仅当$T_{n,k}\cong H$ ，其中H是线性k-一致超树满足H具有一条顶点的最大度为2的超路，并且超路拥有尽可能多的悬挂边。

定义7 [9]设${\pi }_c\left(T_{n,k}\right)$ 是线性k一致超树$T_{n,k}$ 的非递减染色分解序列，在线性k一致超树$T_{n,k}$ 中用边移动操作，得到一个新的k一致超树${T^{\prime }}_{n,k}$ ，满足${T^{\prime }}_{n,k}=\left(V\left(T_{n,k}\right),E\left({T^{\prime }}_{n,k}\right)\right)$ ，其中

$E\left({T^{\prime }}_{n,k}\right)=\left(E\left(T_{n,k}\right)\backslash \left\{e_1\right\}\right)\cup \left\{{e^{\prime }}_1\right\},{e^{\prime }}_1=\left(e_1\backslash \left\{v_1\right\}\right)\cup \left\{u\right\}$ .

得到${T^{\prime }}_{n,k}$ 基于强染色$c^{\prime }$ 的一个新的非递减染色分解序列${{\pi }^{\prime }}_c\left({T^{\prime }}_{n,k}\right)$ 。因此，对于任意的$T_{n,k}\in {\mathcal{T}}_{n,k}$ ，有$I_c\left(T_{n,k}\right)>{I^{\prime }}_c\left({T^{\prime }}_{n,k}\right)$ 。

引理1 [9]${\displaystyle {\sum }_{i=1}^n{x}_i}=M$ ，$x_1>x_2>\cdots >x_i>\cdots >x_j>\cdots >x_n>0$ ，其中M属于正整数，并且满足$x_1,x_2,\cdots ,x_i,\cdots ,x_j,\cdots ,x_n$ 是最大值，那么就有

$x_1^{x_1}\cdots x_2^{x_2}\cdots x_i^{x_i}\cdots x_j^{x_j}\cdots x_n^{x_n}$

是最小值。

定理1 对于任意的$H\left(m,k,p\right)\in \mathscr{H}\left(m,k,p\right)$ ，满足$2p>2p-1>k>3$ ，那么超图$H\left(m,k,p\right)$ 的色熵的极大值与极图有以下三种情况：

情况1：若$m-2p+1=1$ ，即就是$m-2p=0$ ，则

$I_c\left(H\right)\le \log n-\frac{1}{n}\left[\left(k-2\right)\left(m-1\right)\log \left(m-1\right)+\lfloor \frac{m+k-1}{2}\rfloor \log \lfloor \frac{m+k-1}{2}\rfloor +\lceil \frac{m+k-1}{2}\rceil \log \lceil \frac{m+k-1}{2}\rceil \right]$ ,

当且仅当${\pi }_c\left(H\left(m,k,p\right)\right)={\pi }_c\left(H_1\right)$ 时不等式等号成立，$H_1$ 是由长度为$2p-1$ 的路(最大匹配数为p)和在超路的中点处连接了一条悬挂边组成的k一致超树，$H_1$ 如图2所示：

Figure 2. The fixed maximum matching number k uniform hypertree H₁

图2. 固定最大匹配数k一致超树H₁

情况2：若$2\le m-2p+1\le p$ ，即就是$1\le m-2p\le p-1$ ，则

$I_c\left(H\right)\le \log n-\frac{1}{n}\left[p\left(m-2\right)\log \left(m-2\right)+r\left(m-1\right)\log \left(m-1\right)+a\log a\right]$ ,

其中$a=m\left(k-r-p-1\right)+2p+r+1$ ，$1\le r\le p-2$ ，当且仅当${\pi }_c\left(H\left(m,k,p\right)\right)={\pi }_c\left(H_2\right)$ 时不等式等号成立，$H_2$ 是由长度为$2p-1$ 的路(最大匹配数为p)上用从两端到中点依次对称的方式悬挂$m-2p+1$ 条边组成的线性k一致超树，$H_2$ 如图3所示：

Figure 3. The fixed maximum matching number k uniform hypertree H₂

图3. 固定最大匹配数k一致超树H₂

情况3：若$\left(\Delta -2\right)+\left(\Delta -3\right)\left(p-1\right)\le m-2p+1\le p\left(\Delta -2\right)$ ，$\Delta =3,4,\cdots ,i$ 。其中$\Delta$ 为k一致超树的最大度，则

$\begin{array}{c}{I}_c\left(H\right)\le \log n-\frac{1}{n}[x\left(m-\Delta +1\right)\log \left(m-\Delta +1\right)+\left(p-x\right)\left(m-\Delta +2\right)\log \left(m-\Delta +2\right)\\ +r\left(m-1\right)\log \left(m-1\right)+a\log a]\end{array}$

其中$a=m\left(k-p-r-1\right)+p\left(\Delta -2\right)+r+x+1$ ，$r\le r\le p-2$ 。在k一致超树中，有x个度为Δ的星，其中$x=1,2,\cdots ,p$ 。当且仅当${\pi }_c\left(H\left(m,k,p\right)\right)={\pi }_c\left(H_3\right)$ 时不等式等号成立，

$H_3$ 是由长度为$2p-1$ 的路(最大匹配数为p)上用从两端到中点依次对称的方式悬挂$m-2p+1$ 条边组成的线性k一致超树，其中在超路的悬挂的顶点的个数不能超过p个顶点。$H_3$ 如图4所示：

Figure 4. The fixed maximum matching number k uniform hypertree H₃

图4. 固定最大匹配数k一致超树H₃

证明 由超图$H\left(m,k,p\right)$ 的结构特点，则$n=mk-m+1$ 。

由超图的色熵$I_c\left(H\right)$ 定义可知$f\left({\pi }_c\left(H\right)\right)={\displaystyle \sum _{i=1}^k\left|V_i\right|\log \left|V_i\right|}=\log {\left|V_1\right|}^{\left|V_1\right|}\cdot {\left|V_2\right|}^{\left|V_2\right|}\cdot \dots \cdot {\left|V_k\right|}^{\left|V_k\right|}$ 。若

${\left|V_1\right|}^{\left|V_1\right|}\cdot {\left|V_2\right|}^{\left|V_2\right|}\cdot \dots \cdot {\left|V_k\right|}^{\left|V_k\right|}$ 是极小值，那么$f\left({\pi }_c\left(H\right)\right)$ 就是极小值，可以得到$I_c\left(H\right)$ 是极大值。因此，由引理1可知，当$\left|V_1\right|,\left|V_2\right|,\cdots ,\left|V_k\right|$ 是极大值的时，则$I_c\left(H\right)$ 也是极大值。分三种情况讨论超图$H\left(m,k,p\right)$ 的色熵极大值$I_c\left(H\left(m,k,p\right)\right)$ 。

情况1：当$m-2p+1=1$

首先，刻画超图$H_1$ 的图结构。由于$m-2p+1=1$ ，在一条长为$2p-1$ 超路中，令u是该路中度为2的中心点，将剩余的一条超边悬挂于u点处即可，则可以的得到超图$H_1$ 。

接下来，对超图$H_1$ 的顶点进行如下操作的染色。假设s是超图中长为$2p-1$ 的超路中度为2的顶点个数，将这$s$ 个顶点依次按照从左至右的顺序进行编号，记作$v_1,v_2,\cdots ,v_s$ 。首先考虑用颜色1给$v_1$ 顶点进行染色，由于$v_1$ 同时存在于两条超边中，则在剩余的$\left(m-2\right)$ 条超边中，可以在每一条超边中选择一个度为1的顶点，也染颜色1，此时我们可以得到$\left|V_1\right|=m-1$ 。再选择最右侧的度为2的$v_s$ 顶点进行染色，给它染颜色2，$v_s$ 也同样同时存在于两条超边中，则在剩余的不邻接$\left(m-2\right)$ 条超边中，在每条超边中选择一个度为1的顶点，对这$\left(m-2\right)$ 个顶点也染颜色2，此时我们可以得到$\left|V_2\right|=m-1$ 。再选择顶点$v_2$ ，很明显顶点$v_2$ 同样也存在于两条超边当中，所以同样在不邻接的$\left(m-2\right)$ 条超边中选择度为1的顶点，对$v_2$ 和这$\left(m-2\right)$ 个顶点染颜色3，此时$\left|V_3\right|=m-1$ 。同理，可以按照以上方法再选择顶点$v_{s-1}$ ，同样可以得到$\left|V_4\right|=m-1$ 。由于在超路中每条超边有且仅有$\left(k-2\right)$ 个1度顶点，因此上述的染色操作只进行到$v_{k-2}$ ，即就是$\left|V_1\right|=\left|V_2\right|=\cdots =\left|V_{k-2}\right|=m-1$ 。此时已经染色的顶点数为$\left(m-1\right)\left(k-2\right)$ 个，由于超树$H\left(m,k,p\right)$ 的顶点数一共有$\left(mk-m+1\right)$ 个，那么还剩下$\left(m+k-1\right)$ 个顶点。对剩余的顶点按照强染色的规则进行染色即可。因此，

${\pi }_c\left(H_1\right)=\left(\left|V_1\right|,\left|V_2\right|,\cdots ,\left|V_{k-2}\right|,\left|V_k\right|\right)=\left(m-1,m-1,\cdots ,\lfloor \frac{m+k-1}{2}\rfloor ,\lceil \frac{m+k-1}{2}\rceil \right)$ ,

最后，证明上述染色方式对$H_1$ 进行染色得到的色分解序列得到的色熵是极大的。由于$2p-1>k$ ，则可以得到$m+k-1\le m+2p-2=2m-2$ 成立。那么就有$\frac{m+k-1}{2}\le m-1$ 。则上述色分解染色序列对于任意的$\left|V_i\right|$ ，$\left|V_j\right|$ ，$i,j=1,2,\cdots ,k$ ，$i\ne j$ ，都有$\left|\left|V_i\right|-\left|V_j\right|\right|\le 1$ ，那么根据引理1可以得知，上述的色分解染色序列的色熵值是极大的。

情况2：$1\le m-2p\le p-1$

首先，刻画超图$H_2$ 的图结构。由于超图$H\left(m,k,p\right)$ 的匹配数为p，所以超图$H\left(m,k,p\right)$ 中的超路的边数有$\left(2p-1\right)$ 条，且这条路中的度为2的顶点从左到右依次记为$v_1,v_2,\cdots ,v_s$ 。再将剩余的$\left(m-2p+1\right)$ 条超边按$v_1,v_s,v_2,v_{s-1},\cdots$ 的顺序连接在这些顶点上，此时这些顶点的度变为3，就可以得到超图H2的结构图。因为限制超图$H\left(m,k,p\right)$ 的最大匹配数为p，所以在情况2下，悬挂边不能超过p。

接下来，对超图$H_2$ 的顶点进行如下操作的染色，选择顶点$v_1$ ，为其染颜色1，则在其余与$v_1$ 顶点不邻接的$\left(m-3\right)$ 条边中选择一个度为1的顶点也染颜色1，一共有$\left(m-2\right)$ 个顶点染颜色1即，$I{V}_{1}I=m-2$ 。接下来，选择顶点$v_s$ ，染颜色2，再在剩余的与$v_s$ 不邻接的$\left(m-3\right)$ 条边中各找一个度为1的顶点对其也染2色，共$\left(m-3\right)$ 个顶点染颜色2，那就可以得到$\left|V_s\right|=m-2$ 。由于有$\left(m-2p+1\right)$ 条悬挂边，将剩余的$\left(m-2p-1\right)$ 个顶点按照$v_1,v_s$ 这两个顶点的染色方式进行染颜色$3,4,\cdots ,\left(m-2p+1\right)$ 。因此可以得到$\left|V_1\right|=\left|V_2\right|=\cdots =\left|V_{m-2p+1}\right|=m-2$ 。因为$p<2p-2$ ，所以在超路中至少存在一个度为2的顶点，那么选取这样的一个顶点和剩下的$\left(m-2\right)$ 条边中的1度顶点一起染同样的颜色，形成一个新的色类，即就是$\left|V_{m-2p+2}\right|=m-1$ 。假设有$r$ 个色类可以满足这些色类的顶点数均为$m-1$ ，即$\left|V_{m-2p+2}\right|=\left|V_{m-2p+3}\right|=\cdots =\left|V_{m-2p+1+r}\right|=m-1$ ，其中$1\le r\le 2p-2-m+2p-1=4p-m-3$ 。当$r=4p-m-3$ 时，就是超路中悬挂边最多的时候。此时剩余的色分类为 $k-\left(m-2p+1\right)-r=k-m+2p-1-r>k+2p-m-1-4p+m+3=k-2p+2$ ，因为$2p-1>k$ ，所以剩余的色类不超过一个。此时剩余的顶点数为$mk-m+1-\left(m-2p+1\right)\left(m-2\right)-r\left(m-1\right)$ ，即就是$\left|V_k\right|=m\left(k-r-1\right)-\left(m-2p+1\right)\left(m-2\right)+r+1=a$ 。

所以，综上所述

$\begin{array}{c}{\pi }_c\left(H_2\right)=\left(\left|V_1\right|,\cdots ,\left|V_{m-d}\right|,\left|V_{m-d+1}\right|,\cdots ,\left|V_{m-d+r}\right|,\left|V_k\right|\right)\\ =\left(m-2,\cdots ,m-2,m-1,\cdots ,m-1,a\right),\end{array}$

其中$a=m\left(k-r-1\right)-\left(m-2p+1\right)\left(m-2\right)+r+1$

情况3：$\left(\Delta -2\right)+\left(\Delta -3\right)\left(p-1\right)\le m-2p+1\le p\left(\Delta -2\right)$ ，其中$\Delta =4,5,\cdots ,i$ ，当$\Delta =3$ 时，与情况2一致。

首先，刻画超图$H_3$ 的图结构。由于超图$H\left(m,k,p\right)$ 的匹配数固定为p，所以在超路中可以悬挂的顶点最多有p个，并且只能悬挂长度为1的超边。当$\Delta >3$ 时，在图$H_2$ 的基础上，将p条边从左至右依次悬挂在p个点上，得到的最大度为4。然后再将p个超边用同样的方法悬挂在p个顶点上，以此类推，将剩余的边都悬挂在p个顶点上，如此我们得到了在超路上有x个度为Δ的星和$p-x$ 个度为$\left(\Delta -1\right)$ 的星，就可以得到$H_3$ 的结构图。

接下来，给超图$H_3$ 的顶点进行如下的染色操作，选择度为Δ的顶点$v_1$ ，为其染颜色1，则在其余与$v_1$ 顶点不邻接的$\left(m-\Delta \right)$ 条边中选择一个度为1的顶点与顶点$v_1$ 一起染颜色1，一共有$\left(m-\Delta +1\right)$ 个颜色为1的顶点即$\left|V_1\right|=\left(m-\Delta +1\right)$ 。用同样的染色方法给度为Δ的顶点染$2,3,\cdots ,x$ ，因此可以得到$\left|V_1\right|=\left|V_2\right|=\cdots =\left|V_x\right|=\left(m-\Delta +1\right)$ 。接着选择度为$\left(\Delta -1\right)$ 的顶点$v_{x+1}$ ，为其染颜色$x+1$ ，则在其余与$v_{x+1}$ 顶点不邻接的$\left(m-\Delta +1\right)$ 条边中选择一个度为1的顶点与顶点$v_{x+1}$ 一起染颜色$x+1$ ，则一共有$\left(m-\Delta +2\right)$ 个颜色为$\left(x+1\right)$ 的顶点即$\left|V_{x+1}\right|=\left(m-\Delta +2\right)$ 。用同样的染色方法给度为$\left(\Delta -1\right)$ 的顶点染$x+1,x+2,\cdots ,p$ ，因此可以得到$\left|V_{x+1}\right|=\left|V_{x+2}\right|=\cdots =\left|V_p\right|=\left(m-\Delta +2\right)$ 。因为$p<2p-2$ ，所以在超路中一定存在一个度数为2的顶点，与剩余的$\left(m-2\right)$ 条不邻接的超边中的1度顶点一起染颜色$p+1$ ，得到$\left|V_{p+1}\right|=\left(m-1\right)$ 。假设有$r$ 个色类可以满足这些色类的顶点数均为$m-1$ ，即$\left|V_{p+1}\right|=\left|V_{p+2}\right|=\cdots =\left|V_{p+r}\right|=m-1$ ，其中$1\le r\le 2p-2-p=p-2$ 。此时剩余的色分类为$k-p-r>k-p-p+2=k-2p+2$ ，因为$2p-1>k$ ，所以剩余的色类不超过一个。此时剩余的顶点数为$mk-m+1-\left[x\left(m-\Delta +1\right)+r\left(m-1\right)+\left(p-x\right)\left(m-\Delta +2\right)\right]$ ，即就是$\left|V_k\right|=m\left(k-p-r-1\right)+p\left(\Delta -2\right)+r+x+1=a$ 。

所以，综上所述：

$\begin{array}{c}{\pi }_c\left(H_3\right)=\left(\left|V_1\right|,\left|V_2\right|,\cdots ,\left|V_x\right|,\left|V_{x+1}\right|,\cdots ,\left|V_p\right|,\left|V_{p+1}\right|,\cdots ,\left|V_{p+r}\right|,\cdots ,\left|V_k\right|\right)\\ =\left(m-\Delta +1,m-\Delta +1,\cdots ,m-\Delta +1,m-\Delta +2,\cdots ,m-\Delta +2,m-1,\cdots ,m-1,\cdots ,a\right).\end{array}$

□

同理可得，当超路的边数大小为$2p$ 时，超树$H\left(m,k,p\right)$ 的色熵极大值和极值图结构的结果与定理1所得的结果是相同的。

情况1：若$m-2p=1$ ，则

$I_c\left(H\right)\le \log n-\frac{1}{n}\left[\left(k-2\right)\left(m-1\right)\log \left(m-1\right)+\lfloor \frac{m+k-1}{2}\rfloor \log \lfloor \frac{m+k-1}{2}\rfloor +\lceil \frac{m+k-1}{2}\rceil \log \lceil \frac{m+k-1}{2}\rceil \right]$

当且仅当${\pi }_c\left(H\left(m,k,p\right)\right)={\pi }_c\left({H^{\prime }}_1\right)$ 时不等式等号成立，${H^{\prime }}_1$ 是有一条长度为$2p$ 的路，其中这条路的最大匹配数为p，并且在超路的中点处连接了一条悬挂边的k一致超树。

情况2：若$2\le m-2p\le p$ ，则

$I_c\left(H\right)\le \log n-\left[p\left(m-2\right)\log \left(m-2\right)+r\left(m-1\right)\log \left(m-1\right)+a\log a\right]$

其中$a=m\left(k-r-p-1\right)+2p+r+1$ ，$1\le r\le p-2$ ，当且当${\pi }_c\left(H\left(m,k,p\right)\right)={\pi }_c\left({H^{\prime }}_2\right)$ 时不等式等号成立，是有一条长度为$2p$ 的路，并且剩余的$m-2p$ 条边从外到内依次对称的连接方式悬挂在超路上的固定最大匹配数的k一致超树。

情况3：若$\left(\Delta -2\right)+\left(\Delta -3\right)\left(p-1\right)\le m-2p\le p\left(\Delta -2\right)$ ，$\Delta =3,4,\cdots ,i$ 。其中Δ为k一致超树的最大度，则

$\begin{array}{c}{I}_c\left(H\right)\le \log n-\frac{1}{n}[x\left(m-\Delta +1\right)\log \left(m-\Delta +1\right)+\left(p-x\right)\left(m-\Delta +2\right)\log \left(m-\Delta +2\right)\\ +r\left(m-1\right)\log \left(m-1\right)+a\log a]\end{array}$

其中$a=m\left(k-p-r-1\right)+p\left(\Delta -2\right)+r+x+1,r\le r\le p-2$ 。

在k一致超树中，有x个度为Δ的星，其中$x=1,2,\cdots ,p$ 。当且仅当${\pi }_c\left(H\left(m,k,p\right)\right)={\pi }_c\left({H^{\prime }}_3\right)$ 时不等式等号成立，${H^{\prime }}_3$ 是有一条长度为$2p$ 的路，并且剩余的$m-2p$ 条边从外到内依次对称的连接方式悬挂在超路上的固定最大匹配数的k一致超树，其中在超路的悬挂的顶点的个数不能超过p个顶点。

定理2 对于任意的$H\left(m,k,p\right)\in m\left(m,k,p\right)$ ，满足$2p>2p-1>k3$ ，有下面的式子成立

$I_c\left(H\right)\ge \log n-\frac{1}{n}\left\{\left(k-2\right)m\log m+p\log p+\left(n-km+2m-p\right)\log \left(n-km+2m-p\right)\right\}$

当且仅当${\pi }_c\left(H\left(m,k,p\right)\right)\in {\pi }_c\left(H_s\left(m,k,p\right)\right)$ 时不等式等号成立，其中超彗星的图结构如图2所示。

证明根据超彗星$H_s\left(m,k,p\right)$ 的图结构和强染色的染色方式对其进行染色，发现对$H_s\left(m,k,p\right)$ 的染色得出的色分解序列是唯一的。

(i) 当超彗星$H_s\left(m,k,p\right)$ 中路的边数为$2p-1$ 时，记为${H^{\prime }}_s\left(m,k,p\right)$ 对于超树中的每条超边有$k-2$ 个度为1的顶点，用颜色$1,2,\cdots ,k-2$ 对这些顶点进行染色。这样每种颜色有m个顶点，即就是 $\left|V_1\right|=\left|V_2\right|=\cdots =\left|V_{k-2}\right|=m$ 。剩下$n-m\left(k-2\right)$ 个顶点中p个顶点染$k-1$ 颜色，剩余顶点染k颜色。$\left|V_{k-1}\right|=p$ ，$\left|V_k\right|=n-m\left(k-2\right)-p$ 。

因此$I_c\left(H^{\prime }\right)=\log n-\frac{1}{n}\left\{\left(k-2\right)m\log m+p\log p+\left(n-km+2m-p\right)\log \left(n-km+2m-p\right)\right\}$

(ii) 若超彗星$H_s\left(m,k,p\right)$ 中路的边数为$2p$ 时，记为${H^{″}}_s\left(m,k,p\right)$ 。用同样的染色方法对其进行染色。将超路中的最外围悬挂边移动到超路中度最大的顶点处，就会得到路的边数为$2p-1$ 的超彗星，根据定义7可以得到，移动边以后超图的色熵值减小。对超树不断进行移动边的操作，最终可以得到星图的色熵是极小的。可以推断出$I_c\left({H^{\prime }}_s\left(m,k,p\right)\right)<I_c\left({H^{″}}_s\left(m,k,p\right)\right)$ 。

那么，当超路的边数为$2p-1$ 时，超彗星$H_s\left(m,k,p\right)$ 的色熵是最小值。 □