图的两类燃烧问题研究

Research on Two Types of Burning Problems of Graphs

摘要: 图的燃烧理论涉及无向图和有向图，燃烧数刻画了无向图的抗毁性。燃烧连通度将燃烧数和连通度结合，刻画出有向图抗毁的能力，基于此，通过研究证明出$n$ 阶定向完全图的燃烧连通度的界，并在燃烧数和燃烧连通度的基础上，引入充分燃烧数的定义，用于衡量有向图充分燃烧的过程，以及刻画有向图燃烧后产生的结果。并根据此定义，计算出星图、双星图以及完全二部图$K_{2,n}$ 的充分燃烧数。

Abstract: The burning theory of graphs involves undirected graphs and directed graphs. The burning number characterizes the invulnerability of undirected graphs. The burning connectivity combines the burning number and the connectivity, depicting the invulnerability of directed graphs. Based on this, research has proven the bounds of the burning connectivity of n-order directed complete graphs. Moreover, on the basis of the burning number and the burning connectivity, the definition of the sufficient burning number is introduced, which is used to measure the process of sufficient burning of directed graphs and to characterize the results generated after the directed graphs are burned. According to this definition, the sufficient burning numbers of star graphs, double-star graphs, and complete bipartite graphs $K_{2,n}$ are calculated.

1. 引言

图燃烧是图论当前热门的研究课题之一，涉及在图的顶点或边上进行特定的“燃烧”操作，通常用于模拟传播现象，比如火灾、疾病或信息传播[1]-[3]等。燃烧数越小，表明传染或者扩散越快。2016年，Botano [4]等人通过对消防员[1]-[3]等问题的研究提出了图燃烧的模型，引入图的燃烧数的概念，描述信息在网络上传播的速度。他们证明阶数为$n$ 的路和圈的燃烧数$b\left(P_n\right)=b\left(C_n\right)=\lceil \sqrt{n}\rceil$ ，进而对阶数为$n$ 的连通图$G$ ，提出燃烧数$b\left(G\right)\le \lceil \sqrt{n}\rceil$ 的猜想。关于此猜想，很多学者利用一些特殊图对其进行了验证。文献[5]-[8]分别研究并证明了蜘蛛图、毛毛虫图、广义毛毛虫图以及叶子足够多的树都满足燃烧数$b\left(G\right)\le \lceil \sqrt{n}\rceil$ 的猜想。2020年，Janssen [9]引入有向图的图燃烧问题，并研究一些图相应的燃烧数的界以及求解该边界的复杂度。2023年，夏龙苗[10]等人在燃烧数的基础上，将连通度与燃烧数相结合，提出了有向图的燃烧连通度的定义，并证明出定向图的燃烧连通度的界，进而分析定向图的燃烧连通度的算法与复杂性，设计出一种一般定向图的燃烧连通度算法。薛睿滢[11]等人通过连通度对网络抗毁性的度量作用，从图燃烧的角度将该参数推广，提出图的限制性燃烧连通度概念。通过分析限制性燃烧连通度与图结构的关系，阐明该参数在刻画网络抗毁性方面的优势。充分燃烧数反映有向图“燃烧”的过程和状态，同时刻画出有向图“燃烧”后产生的结果。

2. 基础知识

设$G$ 是一个简单无向图，图$G$ 的顶点集和边集分别记为$V_G$ 和$E_G$ ，图的阶指图$G$ 的顶点数，$v\left(G\right)=\left|V\left(G\right)\right|$ ；图$G$ 的边数记为$\epsilon \left(G\right)=\left|E\left(G\right)\right|$ 。顶点$v$ 的度定义为$d\left(v\right)=$ 顶点$v$ 所关联的边的数目，度数为1的顶点称为悬挂点，度数为0的顶点称为孤立点。设$D$ 是一个简单有向图，顶点$v_1$ 的出度：$d_D^{+}=$ 顶点$v_1$ 的出弧的数目。顶点$v_2$ 的入度：$d_D^{-}=$ 顶点$v_2$ 的入弧的数目。有向图$D$ 的最大出度${\Delta }^{+}\left(D\right)=\max \left\{d_D^{+}\left(v\right)|v\in V\left(D\right)\right\}$ ，最大入度${\Delta }^{-}\left(D\right)=\max \left\{d_D^{-}\left(v\right)|v\in V\left(D\right)\right\}$ 。对$D$ 中的弧$a=\left(v_1,v_2\right)$ ，称顶点$v_1$ 为$v_2$ 的内邻点，顶点$v_2$ 为$v_1$ 的外邻点，记$N_D^{-}\left(v\right)=\left\{u:\left(u,v\right)\in A\right\}$ 为$v$ 在$D$ 中的内邻集，$N_D^{+}\left(u\right)=\left\{v:\left(u,v\right)\in A\right\}$ 为$u$ 在$D$ 中的外邻集。完全图是指每一对不同顶点都相邻的无向简单图，记作$K_n$ 。星图通常用$S_n$ 表示，其中$n$ 是图的顶点数$\left(n\ge 2\right)$ ，它由一个中心顶点和$n-1$ 个与中心顶点相连的悬挂点组成，所有的边都连接中心顶点和悬挂顶点，悬挂顶点之间没有边相连。双星图是由两个星图通过一条边连接它们的中心顶点形成的图，记作$DS\left(m,n\right)$ 。完全二部图是指若图$G$ 的顶点集$V$ 可划分为两个非空子集$X$ 和$Y$ ，且任意$X$ 中的顶点和任意$Y$ 中的顶点都有唯一的一条边相连，若$\left|X\right|=m$ 、$\left|Y\right|=n$ ，则完全二部图记作$K_{m,n}$ 。在有向图$D$ 中，定义$D_i^{-}\left(v\right)=\left\{v\in \overrightarrow{D}:d_D^{-}\left(v\right)=i\right\}$ 、$D_i^{+}\left(v\right)=\left\{v\in \overrightarrow{D}:d_D^{+}\left(v\right)=i\right\}$ 。其他未定义的概念参见文献[12] [13]。

3. 定向完全图$K_n\left(n\ge 2\right)$ 的平均燃烧连通度${\kappa }_a\left({\overrightarrow{K}}_n\right)$ 的计算

定义1 [10]：设$D=\left(V,A\right)$ 是有向图，燃烧图$D$ 按如下规则：第1步选择一个点作为火源，记为$x_1$ ，且燃烧过程中不再增加新火源；若在第$t$ 步被燃烧的顶点集为$X_t$ ，则在第$t+1$ 步仅$N_D^{+}\left(X_t\right)$ 中的点全部被燃烧。设经过$k$ 步燃烧之后的剩余子图为$D_k$ ，且$D_k$ 的基础图为$G_k$ ，所有火源中，称使得$G_k$ 不连通或为$\varnothing$ 的最小$k$ 值为$D$ 的燃烧连通度，记为${\kappa }_b\left(D\right)$ ，与之对应的火源记为最佳火源。若存在某个正数$k$ ，$G_k$ 连通且$N_D^{+}\left(X_k\right)=\varnothing$ ，则定义${\kappa }_b\left(D\right)=+\infty$ ；若$D$ 的基础图不连通，则定义${\kappa }_b\left(D\right)=0$ 。

定义2：设$G=\left(V,E\right)$ 是一个无向图，将每条边确定一个方向得到的图记为$\overrightarrow{G}=\left(V,A\right)$ ，称为$G$ 的定向图。图$G$ 的定向图的个数记为$k$ ，定向图的燃烧连通度记为${\kappa }_b\left(\overrightarrow{G}\right)$ 。每种定向图的燃烧连通度之和记为$\sum {\kappa }_b\left(\overrightarrow{G}\right)$ 。称$\frac{1}{k}\times \sum {\kappa }_b\left(\overrightarrow{G}\right)$ 为图$G$ 所有定向图的平均燃烧连通度，记为${\kappa }_a\left(\overrightarrow{G}\right)$ 。若$G$ 的定向图中存在某个$\overrightarrow{G}$ 使${\kappa }_b\left(\overrightarrow{G}\right)=+\infty$ ，则定义${\kappa }_a\left(\overrightarrow{G}\right)=+\infty$ 。若$G$ 不连通，则定义${\kappa }_a\left(\overrightarrow{G}\right)=0$ 。

定理1 [10]：圈图$C_n$ 的定向图${\overrightarrow{C}}_n\left(n\ge 3\right)$ 的最大出度${\Delta }^{+}\left({\overrightarrow{C}}_n\right)=1$ 时，其燃烧连通度${\kappa }_b\left({\overrightarrow{C}}_n\right)=n$ ，在圈图$C_n$ 的定向图${\overrightarrow{C}}_n\left(n\ge 3\right)$ 中，若存在$\left|D_0^{-}\left(v\right)\right|\ge 2$ ，则燃烧连通度${\kappa }_b\left({\overrightarrow{C}}_n\right)=+\infty$ 。

结论1：圈图$C_n$ 的定向图${\overrightarrow{C}}_n\left(n\ge 2\right)$ 至多具有$\{\begin{array}{l}\frac{n}{2},n�偶�\\ \lfloor \frac{n}{2}\rfloor ,n�奇�\end{array}$ 个入度为0的顶点。

证明：根据圈图$C_n$ 的结构性质，${\displaystyle \sum _{i=1}^n{d}^{+}\left(v_i\right)}={\displaystyle \sum _{i=1}^n{d}^{-}\left(v_i\right)}=n$ 。当$n$ 为偶数时，假设在圈图${\overrightarrow{C}}_n$ 中，$\left|D_0^{-}\right|\ge \frac{n}{2}+1$ ，由于${\displaystyle \sum _{i=1}^n{d}^{-}(v)}=0\times \left|D_0^{-}\right|+1\times \left|D_1^{-}\right|+2\times \left|D_2^{-}\right|\le 2\times \left|D_1^{-}\right|+2\times \left|D_2^{-}\right|=2(n-|D_0^{-}|)\le 2(n-(\frac{n}{2}+1))=n-2<n$ ，矛盾。

同理可证，当$n$ 为奇数时结论成立。 □

结论2：在圈图${\overrightarrow{C}}_n\left(n\ge 3\right)$ 中，$\left|D_0^{+}\right|=\left|D_2^{+}\right|=\left|D_0^{-}\right|=\left|D_2^{-}\right|$ 。

证明：首先显然$\left|D_0^{+}\right|=\left|D_2^{-}\right|$ ，$\left|D_0^{-}\right|=\left|D_2^{+}\right|$ 。下证$\left|D_0^{+}\right|=\left|D_2^{+}\right|$ 。设$\left|D_0^{+}\right|=r$ 、$\left|D_1^{+}\right|=s$ 、$\left|D_2^{+}\right|=t$ 。因${\displaystyle \sum _{i=1}^n{d}^{+}\left(v_i\right)}=n$ ，顶点数为$n$ ，故有$\{\begin{array}{l}0\times r+1\times s+2\times t=n\\ r+s+t=n\end{array}\Rightarrow s+2t=r+s+t\Rightarrow r=t$ 。故结论成立。 □

引理1 [10]：对任意连通图$G$ 的定向图$\overrightarrow{G}$ ，都有${\kappa }_b\left(\overrightarrow{G}\right)\ge 1$ 。

定理2：设${\overrightarrow{K}}_n\left(n\ge 2\right)$ 为完全图$K_n$ 的某个定向图，则$1\le {\kappa }_b\left({\overrightarrow{K}}_n\right)\le 3$ 。

证明：由引理1可知，${\kappa }_b\left({\overrightarrow{K}}_n\right)\ge 1$ 成立。假设$n$ 为奇数，由完全图的定义，${\overrightarrow{K}}_n$ 具有$\frac{n\left(n-1\right)}{2}$ 条定向边，故${\displaystyle \sum _{i=1}^n{d}^{+}\left(x_i\right)}={\displaystyle \sum _{i=1}^n{d}^{-}\left(x_i\right)}=\frac{n\left(n-1\right)}{2}$ ，平均每个顶点的出度为$\frac{\frac{n\left(n-1\right)}{2}}{n}=\frac{n-1}{2}$ 。则一定存在$d^{+}\left(x\right)\ge \frac{n-1}{2}$ 的顶点$x$ ，选择其为火源，假设$d^{+}\left(x\right)$ 为$k\left(\frac{n-1}{2}\le k\le n-1\right)$ ，下一步将燃烧$k$ 个顶点，剩余的出度为$\frac{n\left(n-1\right)}{2}-k$ 。任意两个顶点中，只能有一条定向边，故已经燃烧的$k$ 个顶点中，至多有$\frac{k\left(k-1\right)}{2}$ 个出度，同理，剩下$n-k-1$ 个未被燃烧的顶点中，至多有$\frac{\left(n-k-2\right)\left(n-k-1\right)}{2}$ 个出度，$n-k-1$ 个未被燃烧的顶点与火源中至多有$n-k-1$ 个出度，故由$\frac{1}{n-1}\times \left[\left(\frac{n\left(n-1\right)}{2}-k\right)-\frac{k\left(k-1\right)}{2}-\frac{\left(n-k-2\right)\left(n-k-1\right)}{2}-\left(n-k-1\right)\right]\ge n-k-1$ 且$\frac{n-1}{2}\le k\le n-1$ 。可得$\left(n-2k\right)\left(n-1\right)-n\le 0$ 。表明已经燃烧的$k$ 个顶点与未被燃烧的$n-k-1$ 个顶点中，平均出度大于或等于剩下未被燃烧的顶点数$n-k-1$ 。又由$k\ge n-k-1$ 。所以在已经燃烧的$k$ 个顶点中，存在平均出度大于或等于$n-k-1$ 的顶点$y$ ，在下一步的燃烧中，将燃烧$N_d^{+}\left(y\right)$ ，此时$N_d^{+}\left(y\right)$ 包含剩下未被燃烧的$n-k-1$ 个顶点。当$k=n-1$ 时，${\kappa }_b\left({\overrightarrow{K}}_n\right)=2$ 。当$\frac{n-1}{2}\le k<n-1$ 时，${\kappa }_b\left({\overrightarrow{K}}_n\right)=3$ 。故${\kappa }_b\left({\overrightarrow{K}}_n\right)\le 3$ 。

同理可得，当$n$ 为偶数时结论成立。 □

定理3：$K_n\left(n\ge 2\right)$ 的所有定向图的平均燃烧连通度${\kappa }_a\left({\overrightarrow{K}}_n\right)$ 为$3-n\times 2^{1-n}$ 。

证明：根据完全图的定义，$n$ 阶完全图具有$\frac{n\left(n-1\right)}{2}$ 条边，故其有$2^{\frac{n\left(n-1\right)}{2}}$ 种定向图。因为定向图燃烧连通度为2的情况具有图1所示的结构，且由定理2得$K_n\left(n\ge 2\right)$ 的所有定向图的燃烧连通度只能为2或3。

Figure 1. The structure of a complete graph of order n with a burning connectivity of 2

图1. 燃烧连通度为2的n阶完全图结构

图1中的定向边(实线) $v_1{v}_2,v_1{v}_3,\cdots ,v_1{v}_n$ 共有$n-1$ 条，非定向边(虚线)有$\frac{n\left(n-1\right)}{2}-\left(n-1\right)$ 条，出度为$n-1$ 的顶点可以为$v_1,v_2,\cdots ,v_n$ 中的任意一个。所以燃烧连通度为2的情况共有$n\times 2^{\frac{n\left(n-1\right)}{2}-\left(n-1\right)}$ 种，则燃烧连通度为3的情况有$2^{\frac{n\left(n-1\right)}{2}}-n\times 2^{\frac{n\left(n-1\right)}{2}-\left(n-1\right)}$ 种，故$K_n\left(n\ge 2\right)$ 的所有定向图的平均燃烧连通度${\kappa }_a\left({\overrightarrow{K}}_n\right)$ 为$\frac{1}{2^{\frac{n\left(n-1\right)}{2}}}\times \left[2n\times 2^{\frac{n\left(n-1\right)}{2}-\left(n-1\right)}+3\times \left(2^{\frac{n\left(n-1\right)}{2}}-2^{\frac{n\left(n-1\right)}{2}-\left(n-1\right)}\times n\right)\right]=3-n\times 2^{1-n}$ 。通过此公式可得，${\kappa }_a\left({\overrightarrow{K}}_n\right)\left(n\ge 2\right)$ 的任意阶的平均燃烧连通度的精确值。 □

4. 充分燃烧数的定义及几类图充分燃烧数的计算

上节介绍了燃烧连通度的定义，如果在燃烧过程中基础图$G$ 出现不连通的情况则停止燃烧，并计算燃烧连通度。但事实上，“燃烧”过程非常迅速，从第$k$ 步到第$k+1$ 步经历的时间可能极其短，例如火灾的蔓延、电脑病毒的传播、电路的破坏等，这些情况需要关注“燃烧”的过程，也需要对燃烧后的结果进行刻画。因此，我们定义一个新的参数：充分燃烧数，燃烧规则如下：基于燃烧连通度的规则，在经历第$k$ 步燃烧后，可能会出现剩余子图$D_k$ 的基础图$G_k$ 不连通，但$N_D^{+}\left(X_t\right)\ne \varnothing$ ，这表明燃烧不够充分，在此种情况下，应继续接下来的燃烧，直至燃烧不能继续，即$G_k=\varnothing$ 或者$G_k$ 不连通且$N_D^{+}\left(X_t\right)=\varnothing$ ，因$G_k$ 不连通且$N_D^{+}\left(X_t\right)=\varnothing$ ，停止燃烧的情况会产生一些孤立点，孤立点的个数反映燃烧的情况，孤立点越少，表明燃烧越充分。称所有火源中使得孤立点剩余数量最少的最小$k$ 为$D$ 的充分燃烧数，记为${\kappa }_s\left(D\right)$ ，与之对应的火源记为最佳火源。最佳火源的选取通常不唯一，在选择火源时，应结合图的结构，优先选取能“燃烧”更多顶点的火源。若存在某个正数$k$ ，$G_k$ 连通且$N_D^{+}\left(X_k\right)=\varnothing$ ，则定义${\kappa }_s\left(D\right)=+\infty$ ；若$D$ 的基础图不连通，则定义${\kappa }_s\left(D\right)=0$ 。若燃烧结束仅剩一个孤立点，此时$G_k$ 连通且$N_D^{+}\left(X_k\right)=\varnothing$ ，故此时${\kappa }_s\left(D\right)=+\infty$ 。此情况为研究证明时需考虑的特殊情况。

定理4：设${\overrightarrow{S}}_{1,n-1}$ 是星图$S_{1,n-1}\left(n\ge 4\right)$ 的定向图，设中心点为$x$ ，其余点为$y_1,y_2,\cdots ,y_{n-1}$ 。则

${\kappa }_s\left({\overrightarrow{S}}_{1,n-1}\right)=\{\begin{array}{l}2,d^{+}\left(x\right)=0;\\ 3,0<d^{+}\left(x\right)\le n-1且d^{+}\left(x\right)\ne n-3\\ +\infty ,d^{+}\left(x\right)=n-3,\end{array}$

证明：按照中心点$x$ 的出度分情况讨论。

情形1：$d^{+}\left(x\right)=0$ 。选取$x$ 以外的任意点为火源，有${\kappa }_s\left({\overrightarrow{S}}_{1,n-1}\right)=2$ 。且燃烧结束剩余的孤立点个数为$n-2$ 。

情形2：$0<d^{+}\left(x\right)\le n-1$ 且$d^{+}\left(x\right)\ne n-3$ 。选取$N^{-}\left(x\right)$ 中的任意一点为火源。下一次将燃烧$x$ ，接着将燃烧$N^{+}\left(x\right)$ 。故${\kappa }_s\left({\overrightarrow{S}}_{1,n-1}\right)=3$ 。燃烧结束剩余孤立点个数为$n-2-d^{+}\left(x\right)$ 。

情形3：$d^{+}\left(x\right)=n-3$ 。为燃烧更多的顶点，应选取$N^{-}\left(x\right)$ 两个顶点中任意一个为火源。下一次将燃烧$x$ ，接着将燃烧$N^{+}\left(x\right)$ 。此时图中只存在$N^{-}\left(x\right)$ 中除火源外的另外一个顶点，故连通，但$N^{+}\left(X_3\right)=\varnothing$ 。故有${\kappa }_s\left({\overrightarrow{S}}_{1,n-1}\right)=+\infty$ 。 □

定理5：设$\overrightarrow{DS}\left(m,n\right)$ 是双星图$DS\left(m,n\right)$ 的定向图，其中$m>n>3$ 。两个中心点分别为$x_1$ 、$y_1$ 且$N^{+}\left(x_1\right)=y_1$ 。其余顶点分别为$x_2,x_3,\cdots ,x_m$ 、$y_2,y_3,\cdots ,y_n$ 。则

${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=\{\begin{array}{l}2,d^{+}\left(x_1\right)=m且d^{+}\left(y_1\right)=0;\\ 3,d^{+}\left(x_1\right)=m且0<d^{+}\left(y_1\right)\le n-2;d^{+}\left(x_1\right)=m且d^{+}\left(x_1\right)=1;\\ 1\le d^{+}\left(x_1\right)<m且d^{+}\left(y_1\right)=0;\\ 4,1\le d^{+}\left(x_1\right)<m且0<d^{+}\left(y_1\right)\le n-2;1\le d^{+}\left(x_1\right)<m-2且0<d^{+}\left(y_1\right)\le n-1;\\ d^{+}\left(x_1\right)=m且0<d^{+}\left(y_1\right)\le n-1;\\ +\infty ,d^{+}\left(x_1\right)=m且d^{+}\left(y_1\right)=n-2;d^{+}\left(x_1\right)=m-2且d^{+}\left(y_1\right)=n-1,\end{array}$

证明：按照两个中心点$x_1$ 、$y_1$ 的出度分情况讨论。

情形1：$d^{+}\left(x_1\right)=m$ 且$d^{+}\left(y_1\right)=0$ 。$x_1$ 为最佳火源，接下来将燃烧$y_1$ 与$x_2,x_3,\cdots ,x_m$ 。此时燃烧不能继续，故${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=2$ 。且燃烧结束剩余的孤立点个数为$n-1$ 。

情形2：$d^{+}\left(x_1\right)=m$ 且$0<d^{+}\left(y_1\right)\le n-1$ 。

情形2.1：$d^{+}\left(x_1\right)=m$ 且$0<d^{+}\left(y_1\right)<n-2$ ；$d^{+}\left(x_1\right)=m$ 且$d^{+}\left(y_1\right)=n-1$ 。此时$x_1$ 为最佳火源，下一次将燃烧$y_1$ 与$x_2,x_3,\cdots ,x_m$ ，接着将燃烧$N^{+}\left(y_1\right)$ ，故${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=3$ 。且燃烧结束剩余的孤立点个数为$n-1-d^{+}\left(y_1\right)$ 。

情形2.2：$d^{+}\left(x_1\right)=m$ 且$d^{+}\left(y_1\right)=n-2$ 。$x_1$ 为最佳火源，下一次将燃烧$y_1,x_2,x_3,\cdots ,x_m$ ，接着将燃烧$N^{+}\left(y_1\right)$ 。此时燃烧不能继续，图中仅剩一个孤立点，故连通，且$N^{+}\left(X_3\right)=\varnothing$ 。所以${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=+\infty$ 。

情形3：$1\le d^{+}\left(x_1\right)<m$ 且$d^{+}\left(y_1\right)=0$ 。此时$N^{-}\left(x_1\right)$ 中任意一点为最佳火源，接下来将燃烧$x_1$ ，接着将燃烧$y_1$ 与$N^{+}\left(x_1\right)$ ，此时燃烧不能继续，故${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=3$ 。且燃烧结束剩余的孤立点个数为$m+n-d^{+}\left(x_1\right)-2$ 。

情形4：$1\le d^{+}\left(x_1\right)<m$ 且$0<d^{+}\left(y_1\right)\le n-1$ 。

情形4.1：$d^{+}\left(x_1\right)=m-2$ 且$d^{+}\left(y_1\right)=n-1$ 。为燃烧更多的顶点，应选取$N^{-}\left(x_1\right)$ 两个顶点中任意一个为火源。下一次将燃烧$x_1$ ，继续将燃烧$N^{+}\left(x_1\right)$ ，其中包括$y_1$ ，接着将燃烧$N^{+}\left(y_1\right)$ 。此时图中只存在$N^{-}\left(x\right)$ 中除火源外的另外一个顶点，故连通，且$N^{+}\left(X_4\right)=\varnothing$ 。所以${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=+\infty$ 。

情形4.2：$1\le d^{+}\left(x_1\right)<m$ 且$0<d^{+}\left(y_1\right)\le n-2$ ；$1\le d^{+}\left(x_1\right)<m-2$ 且$0<d^{+}\left(y_1\right)\le n-1$ ；$d^{+}\left(x_1\right)=m-1$ 且$0<d^{+}\left(y_1\right)\le n-1$ 。此时$N^{-}\left(x_1\right)$ 中任意一点为最佳火源，接下来将燃烧$x_1$ ，继续将燃烧$y_1$ 与$N^{+}\left(x_1\right)$ ，接着将燃烧$N^{+}\left(y_1\right)$ ，此时燃烧不能继续，故${\kappa }_s\left(\overrightarrow{DS}\left(m,n\right)\right)=4$ 。且燃烧结束剩余的孤立点个数为$m+n-d^{+}\left(x_1\right)-d^{+}\left(y_1\right)-2$ 。 □

定理6：设${\overrightarrow{K}}_{2,1}$ 是完全二部图$K_{2,1}$ 的定向图，其分部为$X$ 、$Y$ ，且$\left|X\right|=2$ 、$\left|Y\right|=1$ ，设$X=\left\{x_1,x_2\right\}$ 、$Y=\left\{y_1\right\}$ 。则

${\kappa }_s\left({\overrightarrow{K}}_{2,1}\right)=\{\begin{array}{l}2,{\Delta }^{+}\left(y_1\right)=2;\\ 3,{\Delta }^{+}\left(y_1\right)=1;\\ +\infty ,{\Delta }^{+}\left(y_1\right)=0,\end{array}$

证明：按照$K_{2,1}$ 中的${\Delta }^{+}\left(y_1\right)$ 分情形讨论。

情形1：${\Delta }^{+}\left(y_1\right)=2$ 。此时$y_1$ 为最佳火源，有${\kappa }_s\left({\overrightarrow{K}}_{2,1}\right)=2$ 。

情形2：${\Delta }^{+}\left(y_1\right)=1$ 。此时$K_{2,1}$ 的定向图为长度为3的有向路，选择该路的起点为火源。则${\kappa }_s\left({\overrightarrow{K}}_{2,1}\right)=3$ 。

情形3：${\Delta }^{+}\left(y_1\right)=0$ 。此时${\Delta }^{-}\left(y_1\right)=2$ 。为燃烧更多的顶点，应选取$X$ 中任意一点为火源，下一步将燃烧$y_1$ ，此时图中仅剩一个孤立点，故连通，且$N^{+}\left(X_2\right)=\varnothing$ ，故${\kappa }_s\left({\overrightarrow{K}}_{2,1}\right)=+\infty$ 。 □

定理7：设${\overrightarrow{K}}_{2,n}\left(n\ge 2\right)$ 是完全二部图$K_{2,n}$ 的定向图，其分部为$X$ 、$Y$ ，且$\left|X\right|=2$ 、$\left|Y\right|=n$ ，设$X=\left\{x_1,x_2\right\}$ 、$Y=\left\{y_1,y_2,\cdots ,y_n\right\}$ 。定义集合$A=\left\{y_i|{\Delta }^{+}\left(y_i\right)=2\right\},i=1,2,\cdots ,n$ 、$B=\left\{y_i|{\Delta }^{+}\left(y_i\right)=1\right\},i=1,2,\cdots ,n$ 、$C=\left\{y_i|{\Delta }^{+}\left(y_i\right)=0\right\},i=1,2,\cdots ,n$ ，则

${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=\{\begin{array}{l}3,\left|A\right|=1;\left|A\right|\ge 3;\left|B\right|=1;2\le \left|B\right|\le n,且d^{+}\left(x_1\right)=n或d^{+}\left(x_2\right)=n;\\ 4,2\le \left|B\right|\le n且d^{+}\left(x_1\right)和d^{+}\left(x_2\right)不�0;\\ +\infty ,\left|A\right|=3,\left|C\right|=n,\end{array}$

证明：按照$K_{2,n}$ 中的${\Delta }^{+}\left(y_i\right)$ 以及其个数分情形讨论。

情形1：$A\ne \varnothing$ 。

情形1.1：$\left|A\right|\ge 3$ 。此时选取$A$ 中任意一点为火源，下一次将燃烧$x_1$ 、$x_2$ 。接着将燃烧$Y/A$ 中所有顶点，所以${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=3$ ，且未被充分燃烧的顶点数为$\left|A\right|-1$ 。

情形1.2：$\left|A\right|=2$ 。此时应选取$A$ 中任意一点为火源，燃烧原理同情形1.1，但$N^{+}\left(X_3\right)=\varnothing$ 。所以${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=+\infty$ 。

情形1.3：$\left|A\right|=1$ 。此时选取唯一出度为2的顶点作为火源，假设为$y_1$ ，则$N_d^{+}\left(y_1\right)=\left\{x_1,x_2\right\}$ 。由于$\left|A\right|=1$ ，有$N_d^{+}\left(x_1\right)\cup N_d^{+}\left(x_2\right)=\left\{y_2,y_3,\cdots ,y_n\right\}$ 。故${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=3$ 。

情形2：$B\ne \varnothing$ 。

情形2.1：$\left|B\right|=n$ 。

情形2.1.1：$d^{+}\left(x_1\right)$ 或$d^{+}\left(x_2\right)=n$ 。此时选取出度为$n$ 的顶点作为火源，假设为$x_1$ ，下一步将燃烧$Y$ 中所有顶点。由于$N_D^{+}\left(y_i\right)=x_1,\left(i=1,2,\cdots ,n\right)$ ，故下一步将燃烧$x_2$ 。所以${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=3$ 。

情形2.1.2：$d^{+}\left(x_1\right)$ 和$d^{+}\left(x_2\right)\ne n$ 。假设$n>d^{+}\left(x_1\right)=k\ge d^{+}\left(x_2\right)$ 。此时选取$x_1$ 为火源，下一步将燃烧$Y$ 中$k$ 个顶点，假设为$\left\{y_1,y_2,\cdots ,y_k\right\}$ ，由$\left|B\right|=n$ ，有$N_D^{+}\left(v_i\right)=x_2,\left(i=1,2,\cdots ,k\right)$ ，所以下一步将燃烧$x_2$ 。剩余的$n-k$ 个顶点$\left\{y_{k+1},y_{k+2},\cdots ,y_n\right\}$ 中，有$N_D^{+}\left(x_2\right)=y_i,\left(i=k+1,k+2,\cdots ,n\right)$ ，则下一步$x_2$ 将燃烧剩余的所有顶点。故${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=4$ 。

情形2.2：$2\le \left|B\right|<n$ 。

情形2.2.1：$d^{+}\left(x_1\right)$ 或$d^{+}\left(x_2\right)=n$ 。此时燃烧规则同情形2.1.1。故${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=3$ 。

情形2.2.2：$d^{+}\left(x_1\right)$ 和$d^{+}\left(x_2\right)\ne n$ 。假设$n>d^{+}\left(x_1\right)=k\ge d^{+}\left(x_2\right)$ ，$\left|B\right|=r,2\le r<n$ 。因为${\displaystyle \sum _{i=1}^n\left(d^{+}\left(y_i\right)+d^{-}\left(y_i\right)\right)}=2n$ ，$d^{+}\left(x_1\right)+d^{+}\left(x_2\right)={\displaystyle \sum _{i=1}^n{d}^{-}\left(y_i\right)}$ ，故$d^{+}\left(x_1\right)+d^{+}\left(x_2\right)=2n-r$ 。$d^{+}\left(x_2\right)=2n-r-d^{+}\left(x_1\right)=2n-r-k$ 。又因为$d^{+}\left(x_1\right)=k\ge d^{+}\left(x_2\right)$ ，故$k\ge 2n-r-k$ ，即$k\ge n-\frac{r}{2}$ 。此时选择$d^{+}\left(x_1\right)$ 为火源，则下一步将燃烧$Y$ 中的$k$ 个顶点，$k$ 至少为$n-\lfloor \frac{r}{2}\rfloor$ ，假设燃烧的顶点集为$\left\{y_1,y_2,\cdots ,y_k\right\}$ ，$Y$ 中剩余$n-k$ 个顶点未被燃烧，由假设$\left|B\right|=r,2\le r<n$ 可得，$Y/\left|B\right|=n-r$ ，由于$n-\frac{r}{2}-\left(n-r\right)=\{\begin{array}{l}\lceil \frac{r}{2}\rceil ,r�奇�\\ \frac{r}{2},r�偶�\end{array}$ ，且$2\le r<n$ ，故$\lceil \frac{r}{2}\rceil \ge 1$ 与$\frac{r}{2}\ge 1$ ，即在燃烧的至少$n-\lfloor \frac{r}{2}\rfloor$ 个顶点中，至少存在1个最大出度为1的顶点被燃烧，那么这些顶点在下一步一定会燃烧$x_2$ ，接下一步$x_2$ 将燃烧$\left\{y_{k+1},y_{k+2},\cdots ,y_n\right\}$ 。故${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=4$ 。

情形2.3：$\left|B\right|=1$ 。此时$d^{+}\left(x_1\right)=n$ 或$d^{+}\left(x_2\right)=n$ 。选取该顶点为火源，燃烧规则同情形2.1.1，故${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=3$ 。

情形3：$\left|C\right|=n$ 。选择$X$ 中任意一点为火源，接下来将燃烧$Y$ 中所有顶点。此时图中只剩下$X$ 中除火源外的一个顶点，故连通，且$N^{+}\left(X_2\right)=\varnothing$ 。所以${\kappa }_s\left({\overrightarrow{K}}_{2,n}\right)=+\infty$ 。 □

5. 结论

本文根据燃烧连通度的定义，给出$n\left(n\ge 2\right)$ 阶定向完全图的燃烧连通度的界，并推导出所有定向图的平均燃烧连通度${\kappa }_a\left({\overrightarrow{K}}_n\right)$ 的计算公式。定义一个新的参数——充分燃烧数，用于衡量燃烧状态及刻画燃烧结果，通过新的燃烧规则对图的燃烧理论进行不同维度的研究。总的来看，图的燃烧理论具有多种不同的研究方法，以上两种方法在不同的方向上研究了图的燃烧理论。在接下来的研究中，可以考虑计算$n$ 部图、完全$n$ 部图的充分燃烧数，探索多个部集之间的“燃烧关系”，进一步拓展燃烧理论研究框架。

基金项目

重庆市自然科学基金创新发展联合基金(市教委)项目(编号：CSTB2022NSCQ-LZX0003)。