几类半笛卡尔积图的线性荫度

Linear Arboricity of Several Classes of Semi-Cartesian Product of Graphs

摘要: 一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G的边集E(G)可以分解成n个线性森林的最小整数n，用la(G)表示。本文对路和路、路和圈、圈和圈以及路和树的半笛卡尔积结构进行讨论，通过对这几类图中的边进行划分，得到了路和路，路和圈，圈和圈以及路和树的半笛卡尔积的线性荫度的确切值并且证明这几类图满足线性荫度猜想。

Abstract: A linear forest is a forest whose components are paths. The linear arboricity la(G) of a G is the minimum number n of linear forests that is the partition of the edge set E(G) of G. In this paper, we discuss the structure of Semi-Cartesian product path and path, path and cycle, cycle and cycle, and path and tree. By dividing the edges of these kinds of graphs, we show that the exact values of the linear arboricity of Semi-Cartesian products of path and path, path and cycle, cycle and cycle, path and tree and these values match up the linear arboricity conjecture.

1. 引言

一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G可以分解成n个线性森林的最小整数n，用 $la\left(G\right)$ 表示。线性荫度的概念最早是由Harary [1] 于1970年提出的。关于图G的线性荫度，Akiyama，Exoo和Harary [2] 提出了一个猜想：对于任何正则图G，均有 $la\left(G\right)=\lceil \frac{\Delta \left(G\right)+1}{2}\rceil$。他们在文献 [2] 中给出了树、完全图、完全二部图等图类的线性荫度，并且证明了当 $\Delta \left(G\right)=3$ 时此猜想成立。在文献 [3] 中，他们又证明了 $\Delta \left(G\right)=4$ 时此猜想成立。接着，Enomoto和Péroche [4] 证明了当 $\Delta \left(G\right)=5,6,8$ 时，此猜想是成立的。1986年，Guldan [5] 证明了当 $\Delta \left(G\right)=10$ 时此猜想也成立。显然对于任何图G，均有 $la\left(G\right)\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil$，这是因为任何一个顶点在一个线性森林中的度最大是2。而对于任何正则图G，均有 $la\left(G\right)\ge \lceil \frac{\Delta \left(G\right)+1}{2}\rceil$。所以上面的猜想等价于著名的线性荫度猜想：

猜想1：对于任何简单图G，都有 $\lceil \frac{\Delta \left(G\right)}{2}\rceil \le la\left(G\right)\le \lceil \frac{\Delta \left(G\right)+1}{2}\rceil$。

对于平面图而言，此猜想已经被吴建良 [6] [7] 证明是成立的。文献 [8] [9] 中，作者证明了若G是 $\Delta \left(G\right)\ge 21$ 的NIC-平面图或不含4-圈且 $\Delta \left(G\right)\ge 9$ 的IC-平面图，其线性荫度均为 $\lceil \frac{\Delta \left(G\right)}{2}\rceil$。Niu和Zhang [8] 还证明了 $\Delta \left(G\right)\ge 14$ 的NIC-平面图，线性荫度猜想是成立的。陈洪玲 [10] 等人证明了对于两个固定的整数 $i,j\in \left\{5,6,7\right\}$，如果最大度 $\Delta \left(G\right)\ge 7$ 的平面图G中不存在相邻的含弦 $i,j$ -圈，则图G的线性荫度为 $\lceil \frac{\Delta \left(G\right)}{2}\rceil$。近期，李萍 [11] 验证了树和路的笛卡尔积图、直积图、强积图满足线性荫度猜想。这些结果都丰富了此研究领域的发展，但迄今为止，此猜想仍未被完全证明。

本文我们考虑几类特殊图的半笛卡尔积图的线性荫度。半笛卡尔积图是由Metsidik [12] 于2013年提出的一种新定义的乘积图，这是由两个连通的二部图且其中一个图是对称的另一个图是圈保持定向的图做半笛卡尔积构成。两个符合定义的图的半笛卡尔积可以从这两个图的笛卡尔积大约删除 $\left[\frac{\left|E\left(H\right)\right|}{2}\right]\left|E\left(G\right)\right|$ 得到。而将成为21世纪最有前途的碳纳米材料的结构模型等六角系统模型就可看作是两个简单图的半笛卡儿积。所以研究这几类图的线性荫度是极具有意义的。

2. 基本定义以及符号

定义1. 对于两个连通的二部图G和H，且图G和H都是二着色的，其中图G是对称的，图H是圈保持定向的。图 $G=\left(V_1,E_1\right)$ 与 $H=\left(V_2,E_2\right)$ 的半笛卡尔积图 $G\bigsqcup H=\left(V_1\times V_2,E\right)$，其中 $\left(u_1,u_2\right)$ 与 $\left(v_1,v_2\right)$ 相邻，当且仅当 $u_2=v_2$ 且 $u_1{v}_1\in E\left(G\right)$ 或者 $u_1=v_1$ 且 $u_2\to v_2$ 且 $u_1,u_2$ 着色相同。

符号 $u_2\to v_2$ 表示在连通的圈保持定向图H中边 $u_2{v}_2$ 的方向是由顶点 $u_2$ 指向顶点 $v_2$。二部图的顶点集可分割为两个互不相交的子集 $A=\left\{a_1,\cdots ,a_n\right\}$， $B=\left\{b_1,\cdots ,b_n\right\}$，如果两条边 $a_i{b}_j$ 与 $a_j{b}_i$ 同时出现，称这样的二部图为对称的二部图。具体概念参看文献 [12]。

为了方便描述，我们采用如下一些记号。

我们规定图G和图H做半笛卡尔积时，图G的顶点 $u_1$ 与图H的顶点 $v_1$ 着色相同，当图H分别为路 $P_m$ 与圈 $C_m$ 时，其圈保持定向如图1所示。在半笛卡尔积图 $P_m\bigsqcup P_n$ 中， $V\left(P_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$， $V\left(P_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$， $\left(u_i,v_j\right)\in V\left(G\bigsqcup H\right)$ 记作 $v_j^i$。对于固定的 $j\left(j=1,2,\cdots ,n\right)$，用 $P_n^i$ 表示由顶点集 $\left\{v_1^i,v_2^i,\cdots ,v_n^i\right\}$， $1\le i\le m$ 导出的n条路 $P_m$，用 $P\left(2\right)$ 表示顶点集 $\left\{v_1^1,v_2^1,\cdots ,v_n^1,v_2^m,v_3^m,\cdots ,v_{n-1}^m\right\}$ 导出的 $n-1$ 条路 $P_2$，用 $P^{\ast }\left(2\right)$ 表示顶点集 $\left\{v_1^k,v_2^k,\cdots ,v_n^k,v_2^l,v_3^l,\cdots ,v_{n-1}^l\right\}$ ( $k=3,5,7,\cdots ,m-1$ ; $l=2,4,6,\cdots ,m-2$ )导出的 $\frac{\left(n-1\right)\left(m-2\right)}{2}$ 条路 $P_2$。

Figure 1. The cycle preserving orientable of $P_m$ and $C_m$

图1. $P_m$ 与 $C_m$ 的圈保持定向

3. 主要结论

引理1. [2] 树T的线性荫度 $la\left(T\right)=\lceil \frac{\Delta \left(T\right)}{2}\rceil$。

引理2. 路 $P_m$ 和路 $P_n$ 的半笛卡尔积图 $P_m\bigsqcup P_n$， $la\left(P_m\bigsqcup P_n\right)=\{\begin{array}{cc}1,& m=2,n\ge 2;\\ 2,& 其它.\end{array}$

证明：当 $m=2$， $n\ge 2$， $P_m\bigsqcup P_n=P_{2n}$， $la\left(P_m\bigsqcup P_n\right)=1$。

当 $m\ge 4$， $n=2$ 时，我们得到半笛卡尔积图 $P_m\bigsqcup P_n$ 的最大度 $\Delta \left(P_m\bigsqcup P_2\right)=3$。

由图的线性荫度的定义可知，半笛卡尔积图 $P_m\bigsqcup P_2$ 的线性荫度 $la\left(P_m\bigsqcup P_2\right)\ge \lceil \frac{\Delta \left(P_m\bigsqcup P_2\right)}{2}\rceil =\lceil \frac{3}{2}\rceil =2$。

现在，我们说明半笛卡尔积图 $P_m\bigsqcup P_2$ 可以分解成2个线性森林。令 $M_1=\left\{P_n^i\right\}=\left\{v_1^i,v_2^i\right\}$， $M_2=\left\{P\left(2\right)\right\}=\left\{\left(v_1^1{v}_2^1\right)\right\}$， $M_3=\left\{P^{\ast }\left(2\right)\right\}=\left\{v_1^k,v_2^k\right\}$， $k=3,5,7,\cdots ,m-1$，不难看出 $M_1\cup M_2$， $M_3$ 是2个线性森林，又 $E\left(P_m\bigsqcup P_n\right)=\left(M_1\cup M_2\right)\cup M_3$。这说明 $la\left(P_m\bigsqcup P_2\right)\le 2$。因此 $la\left(P_m\bigsqcup P_2\right)=2$ 成立。

当 $m\ge 4$， $n\ge 3$ 时，由半笛卡尔积的定义可得，半笛卡尔积图 $P_m\bigsqcup P_n$ 的最大度 $\Delta \left(P_m\bigsqcup P_n\right)=\Delta \left(P_m\right)+\Delta \left(P_n\right)-1=3$。

同理，半笛卡尔积图 $P_m\bigsqcup P_n$ 的线性荫度 $la\left(P_m\bigsqcup P_n\right)\ge \lceil \frac{\Delta \left(P_m\bigsqcup P_n\right)}{2}\rceil =\lceil \frac{3}{2}\rceil =2$。

现在，我们说明半笛卡尔积图 $P_m\bigsqcup P_n$ 可以分解成2个线性森林。令 $M_4=\left\{P_n^i\right\}$， $M_5=\left\{P\left(2\right)\right\}$， $M_6=\left\{P^{\ast }\left(2\right)\right\}$，不难看出 $M_4\cup M_5$， $M_6$ 是2个线性森林， 又 $E\left(P_m\bigsqcup P_n\right)=\left(M_4\cup M_5\right)\cup M_6$。这说明 $la\left(P_m\bigsqcup P_n\right)\le 2$。因此 $la\left(P_m\bigsqcup P_n\right)=2$ 成立。 $\square$

因为在 $P_m\bigsqcup P_n$ 中增加一些边即可得到 $P_m\bigsqcup C_n$， $C_m\bigsqcup P_n$ 和 $C_m\bigsqcup C_n$，所以在定理3，4中仍采用之前所定义的记号。

定理3. 路 $P_m$ ( $P_n$ )和圈 $C_n$ ( $C_m$ )的半笛卡尔积图 $P_m\bigsqcup C_n$ 和 $C_m\bigsqcup P_n$， $la\left(P_m\bigsqcup C_n\right)=la\left(C_m\bigsqcup P_n\right)=2$。

证明：当 $m=2$ 时， $P_m\bigsqcup C_n=C_{2n}$，显然 $la\left(P_m\bigsqcup C_n\right)=2$。

当 $m\ge 4$ 时，由半笛卡尔积图的定义可得，半笛卡尔积图 $P_m\bigsqcup C_n$ 最大度 $\Delta \left(P_m\bigsqcup C_n\right)=\Delta \left(P_m\right)+\Delta \left(C_n\right)-1=3$。

由图的线性荫度的定义可知，半笛卡尔积图 $P_m\bigsqcup C_n$ 的线性荫度 $la\left(P_m\bigsqcup C_n\right)\ge \lceil \frac{\Delta \left(P_m\bigsqcup C_n\right)}{2}\rceil =2$。

现在，我们说明 $P_m\bigsqcup C_n$ 可以分解成2个线性森林。

令 $M_1=\left\{P_n^i\right\}$， $M_2=\left\{P\left(2\right)\right\}$， $M_3=\left\{P^{\ast }\left(2\right)\right\}$， $M_4=\left\{\left(v_1^m,v_n^m\right):m=2,4,\cdots ,m\right\}$，不难看出 $M_1\cup M_2$， $M_3\cup M_4$ 是2个线性森林，又 $E\left(P_m\bigsqcup C_n\right)=\left(M_1\cup M_2\right)\cup \left(M_3\cup M_4\right)$。这说明当 $m\ge 4$ 时， $la\left(P_m\bigsqcup C_n\right)\le 2$。

当 $n=2$ 时，因为 $\Delta \left(C_m\bigsqcup P_2\right)=3$，那么 $la\left(C_m\bigsqcup P_n\right)\ge \lceil \frac{\Delta \left(C_m\bigsqcup P_2\right)}{2}\rceil =2$。

当 $n\ge 3$ 时，由半笛卡尔积图的定义可得半笛卡尔积图 $C_m\bigsqcup P_n$ 最大度 $\Delta \left(C_m\bigsqcup P_n\right)=3$， $la\left(C_m\bigsqcup P_n\right)\ge \lceil \frac{\Delta \left(C_m\bigsqcup P_n\right)}{2}\rceil =2$。

现在，我们说明 $C_m\bigsqcup P_n$ 可以分解成2个线性森林。

令 $M_5=\left\{P_n^i\right\}$， $M_6=\left\{\left(v_1^1,v_1^m\right),\left(v_2^1,v_2^m\right),\cdots ,\left(v_n^1,v_n^m\right)\right\}$，不难看出 $M_5\cup M_2$， $M_3\cup M_6$ 是2个线性森林，又 $E\left(C_m\bigsqcup P_n\right)=\left(M_5\cup M_2\right)\cup \left(M_3\cup M_6\right)$，这说明 $la\left(C_m\bigsqcup P_n\right)\le 2$。

综上所述，路 $P_m$ ( $P_n$ )和圈 $C_n$ ( $C_m$ )的半笛卡尔积图 $P_m\bigsqcup C_n$ 与 $C_m\bigsqcup P_n$ 的线性荫度 $la\left(P_m\bigsqcup C_n\right)=la\left(C_m\bigsqcup P_n\right)=2$。 $\square$

如图2所示，我们可以用定理2中的分解方法将半笛卡尔积图 $P_6\bigsqcup C_6$ 分解成2个线性森林 $M_1\cup M_2$， $M_3\cup M_4$。

Figure 2. $M_1\cup M_2$ and $M_3\cup M_4$

图2. $M_1\cup M_2$ 与 $M_3\cup M_4$

定理4. 圈 $C_m$ 和圈 $C_n$ 的半笛卡尔积图 $C_m\bigsqcup C_n$， $la\left(C_m\bigsqcup C_n\right)=2$。

证明：由半笛卡尔积图的定义可得，半笛卡尔积图 $C_m\bigsqcup C_n$ 的最大度 $\Delta \left(C_m\bigsqcup C_n\right)=\Delta \left(C_m\right)+\Delta \left(C_n\right)-1=3$。

由图的线性荫度的定义可知，半笛卡尔积图 $C_m\bigsqcup C_n$ 的线性荫度 $la\left(C_m\bigsqcup C_n\right)\ge \lceil \frac{\Delta \left(C_m\bigsqcup C_n\right)}{2}\rceil =2$。

现在，我们说明 $C_m\bigsqcup C_n$ 可以分解成2个线性森林。令 $M_1=\left\{P_n^i\right\}$， $M_2=\left\{P\left(2\right)\right\}$， $M_3=\left\{P^{\ast }\left(2\right)\right\}$， $M_4=\left\{\left(v_1^m,v_n^m\right):m=2,4,\cdots ,m\right\}$， $M_5=\left\{\left(v_1^1,v_1^n\right),\left(v_2^1,v_2^n\right),\cdots ,\left(v_m^1,v_m^n\right)\right\}$，不难看出 $M_1\cup M_2$， $M_3\cup M_4\cup M_5$ 是2个线性森林，又 $E\left(C_m\bigsqcup C_n\right)=\left(M_1\cup M_2\right)\cup \left(M_3\cup M_4\cup M_5\right)$，这说明 $la\left(C_m\bigsqcup C_n\right)\le 2$。

综上所述，路 $C_m$ 和圈 $C_n$ 的半笛卡尔积图 $C_m\bigsqcup C_n$ 的线性荫度 $la\left(C_m\bigsqcup C_n\right)=2$。 $\square$

定理5. 树T和路 $P_m$ 的半笛卡尔积 $T\bigsqcup P_m$ 的线性荫度， $la\left(T\bigsqcup P_m\right)=\lceil \frac{\Delta \left(T\right)-1}{2}\rceil +1$。

证明：当 $m=2$ 时，我们得到半笛卡尔积图 $T\bigsqcup P_m$ 的最大度 $\Delta \left(T\bigsqcup P_2\right)=\Delta \left(T\right)+1$，由图的线性荫度的定义可知，半笛卡尔积图 $T\bigsqcup P_2$ 的线性荫度 $la\left(T\bigsqcup P_m\right)\ge \lceil \frac{\Delta \left(T\bigsqcup P_2\right)}{2}\rceil =\lceil \frac{\Delta \left(T\right)+1}{2}\rceil =\lceil \frac{\Delta \left(T\right)-1}{2}\rceil +1$。

当 $m\ge 3$，由半笛卡尔积图的定义可得，半笛卡尔积图 $T\bigsqcup P_m$ 的最大度 $\Delta \left(T\bigsqcup P_m\right)=\Delta \left(T\right)+\Delta \left(P_m\right)-1=\Delta \left(T\right)+1$。

同理，半笛卡尔积图 $T\bigsqcup P_m$ 的线性荫度 $la\left(P_m\bigsqcup T\right)\ge \lceil \frac{\Delta \left(P_m\bigsqcup T\right)}{2}\rceil =\lceil \frac{\Delta \left(T\right)+1}{2}\rceil =\lceil \frac{\Delta \left(T\right)-1}{2}\rceil +1$。

根据半笛卡尔积图的定义，树T有两种情况：

情况一：树T是路。引理2已经证明。

情况二：树T不是路。

当 $\Delta \left(T\right)\equiv 0\left(\mathrm{mod}\begin{array}{c}2\end{array}\right)$ 时，如果半笛卡尔积图 $T\bigsqcup P_m$ 中的边是树T的边，那么将这些边放入集合X中，待所有的边全部放入集合X中后，我们得到集合X中包含m个树T的连通分支，且这m个连通分支是两两不相交的。此时在 $T\bigsqcup P_m\backslash X$ 中，每个连通分支都是 $P_2$ 且各个连通分支之间两两不相交，因此 $T\bigsqcup P_m\backslash X$ 满足线性森林的定义。则 $la\left(T\bigsqcup P_m\right)\le la\left(X\right)+la\left(T\bigsqcup P_m\backslash X\right)=la\left(T\right)+1=\lceil \frac{\Delta \left(T\right)}{2}\rceil +1=\lceil \frac{\Delta \left(T\right)-1}{2}\rceil +1$。

当 $\Delta \left(T\right)\equiv 1\left(\mathrm{mod}\begin{array}{c}2\end{array}\right)$ 时。我们把树T所分解成的线性森林记作 $L{F}_l$，其中 $l\in \left\{1,2,\cdots ,\lceil \frac{\Delta \left(T\right)}{2}\rceil \right\}$。

如果半笛卡尔积图 $T\bigsqcup P_m$ 中的边是树T中的边，那么将这些边放入集合Y中，待所有的边全部放入集合Y中后，我们得到 $T\bigsqcup P_m\backslash Y$ 中是两两不相交的 $P_2$ 路。

现在将 $T\bigsqcup P_m\backslash Y$ 的边进行划分。由引理1，树T的任意一种满足 $la\left(T\right)$ 的线性森林划分中，每个最大度顶点只有在一个划分中以路为端点的形式出现，其余的划分均是路的内部顶点的形式。令每个树T的线性森林划分中最多只有一个最大度顶点为端点， $L{F}_i$ ( $i\in \left\{1,2,\cdots ,\lceil \frac{\Delta \left(T\right)}{2}\rceil \right\}$ )中是不包含以最大度顶点为路端点的形式的划分， $L{F}_j$ ( $j\in \left\{1,2,\cdots ,\lceil \frac{\Delta \left(T\right)}{2}\rceil \right\}$ )中是包含以最大度顶点为路端点形式的划分，将每个 $L{F}_j$ 中以最大度顶点为路端点的边放入集合M， $L{F}_j$ 中剩下的边放入集合 $L{f}_j$，那么 $E\left(T\right)=L{F}_j\cup L{F}_i=\left(M\cup L{f}_j\right)\cup L{F}_i$ ( $i,j\in 1,2,\cdots ,\lceil \frac{\Delta \left(T\right)}{2}\rceil$ 且 $i\ne j$ )。如果半笛卡尔积图 $T\bigsqcup P_m$ 中的边是 $L{f}_j$ 的边，那么将这些边放入集合 ${A^{\prime }}_j$ ；如果是 $L{F}_i$ 的边，那么将这些边放入集合 $A_i$。如果是M的边，那么将这些边放入集合 $M_1$。N是树T中最大度顶点的集合， $u_s\in N$， $v_t\in P_m$，那么在半笛卡尔积图 $T\bigsqcup P_m$ 中，将顶点 $\left(u_s,v_t\right)$ 放入集合Z中，把顶点集Z的导出路 $P_2$ 的集合记为 $N_1$， $M_1\cup N_1$ 是一个线性森林。

再令顶点 $a\in V\left(T\right)-N$，若 $a\in V\left(L{F}_i\right)$ 或 $a\in V\left(L{F}_j\right)$ 那么在半笛卡尔积图 $T\bigsqcup P_m$ 中，将顶点集 $\left\{\left(a,v_t\right):a\in V\left(L{F}_i\right),v_t\in V\left(P_m\right)\right\}$ 导出的边放入集合 $B_i$ 中，顶点集 $\left\{\left(a,v_t\right):a\in V\left(L{F}_j\right),v_t\in V\left(P_m\right)\right\}$ 导出的边放入集合 ${B^{\prime }}_j$ 中，不难看出 $\left(A_i\cup {B^{\prime }}_j\right)\cup \left({A^{\prime }}_j\cup B_i\right)$ ( $i,j\in 1,2,\cdots ,\lceil \frac{\Delta \left(T\right)}{2}\rceil$ )是 $\lceil \frac{\Delta \left(T\right)}{2}\rceil -1$ 个线性森林，又 $E\left(T\bigsqcup P_m\right)=\left(M_1\cup N_1\right)\cup \left(A_i\cup {B^{\prime }}_j\right)\cup \left({A^{\prime }}_j\cup B_i\right)$，这说明 $la\left(T\bigsqcup P_m\right)\le \lceil \frac{\Delta \left(T\right)}{2}\rceil =\lceil \frac{\Delta \left(T\right)-1}{2}\rceil +1$。

综上所述，树T和路 $P_m$ 的半笛卡尔积图 $T\bigsqcup P_m$ 的线性荫度 $la\left(T\bigsqcup P_m\right)=\lceil \frac{\Delta \left(T\right)-1}{2}\rceil +1$。 $\bigsqcup$

如图3所示，我们用定理5中的分解方法将半笛卡尔积图 $T\bigsqcup P_4$ 分解成3个线性森林 $\left({B^{\prime }}_1\cup {B^{\prime }}_2\cup A_3\right)\cup \left({A^{\prime }}_1\cup {A^{\prime }}_2\cup B_3\right)\cup \left(M_1\cup N_1\right)$。

$L{F}_1=\left\{\left(u_1,u_5\right)\left(u_8,u_{10}\right)\left(u_8,u_{12}\right)\right\}$， $L{f}_1=\left\{\left(u_8,u_{10}\right),\left(u_8,u_{12}\right)\right\}$，

${A^{\prime }}_1=\left\{\left(v_1^8,v_1^{10}\right),\left(v_1^8,v_1^{12}\right),\left(v_2^8,v_2^{10}\right),\left(v_2^8,v_2^{12}\right),\left(v_3^8,v_3^{10}\right),\left(v_3^8,v_3^{12}\right),\left(v_4^8,v_4^{10}\right),\left(v_4^8,v_4^{12}\right)\right\}$，

$L{F}_2=\left\{\left(u_2{u}_5\right),\left(u_3{u}_5\right),\left(u_8{u}_{11}\right)\right\}$， $L{f}_2=\left\{\left(u_2{u}_5\right),\left(u_3{u}_5\right)\right\}$，

${A^{\prime }}_2=\left\{\left(v_1^2,v_1^5\right),\left(v_1^3,v_1^5\right),\left(v_2^2,v_2^5\right),\left(v_2^3,v_2^5\right),\left(v_3^2,v_3^5\right),\left(v_3^3,v_3^5\right),\left(v_4^2,v_4^5\right),\left(v_4^3,v_4^5\right)\right\}$，

$L{F}_3=\left\{\left(u_4{u}_5\right),\left(u_5{u}_6\right),\left(u_6{u}_7\right),\left(u_7{u}_8\right),\left(u_8{u}_9\right)\right\}$，

$\begin{array}{l}{A}_3=\{\left(v_1^4,v_1^5\right),\left(v_1^5,v_1^6\right),\left(v_1^6,v_1^7\right),\left(v_1^7,v_1^8\right),\left(v_1^8,v_1^9\right),\left(v_2^4,v_2^5\right),\left(v_2^5,v_2^6\right),\left(v_2^6,v_2^7\right),\left(v_2^7,v_2^8\right),\left(v_2^8,v_2^9\right),\\ \left(v_3^4,v_3^5\right),\left(v_3^5,v_3^6\right),\left(v_3^6,v_3^7\right),\left(v_3^7,v_3^8\right),\left(v_3^8,v_3^9\right),\left(v_4^4,v_4^5\right),\left(v_4^5,v_4^6\right),\left(v_4^6,v_4^7\right),\left(v_4^7,v_4^8\right),\left(v_4^8,v_4^9\right)\}\end{array}$，

Figure 3. $\left({B^{\prime }}_1\cup {B^{\prime }}_2\cup A_3\right)\cup \left({A^{\prime }}_1\cup {A^{\prime }}_2\cup B_3\right)\cup \left(M_1\cup N_1\right)$

图3. $\left({B^{\prime }}_1\cup {B^{\prime }}_2\cup A_3\right)\cup \left({A^{\prime }}_1\cup {A^{\prime }}_2\cup B_3\right)\cup \left(M_1\cup N_1\right)$

$M=\left\{\left(u_1,u_5\right),\left(u_8,u_{11}\right)\right\}$，

$M_1=\left\{\left(v_1^1,v_1^5\right),\left(v_2^1,v_2^5\right)\left(v_3^1,v_3^5\right)\left(v_4^1,v_4^5\right),\left(v_1^8,v_1^{11}\right),\left(v_2^8,v_2^{11}\right)\left(v_3^8,v_3^{11}\right)\left(v_4^8,v_4^{11}\right)\right\}$，

$N=\left\{u_5,u_8\right\}$， $N_1=\left\{\left(v_1^5,v_2^5\right),\left(v_3^5,v_4^5\right)\left(v_2^8,v_3^8\right)\right\}$，

${B^{\prime }}_1=\left\{\left(v_1^1,v_2^1\right),\left(v_3^1,v_4^1\right),\left(v_2^{10},v_3^{10}\right),\left(v_2^{12},v_3^{12}\right)\right\}$，

${B^{\prime }}_2=\left\{\left(v_2^2,v_3^2\right),\left(v_1^3,v_2^3\right),\left(v_3^3,v_4^3\right),\left(v_1^{11},v_2^{11}\right),\left(v_3^{11},v_4^{11}\right)\right\}$，

$B_3=\left\{\left(v_2^4,v_3^4\right),\left(v_2^6,v_3^6\right),\left(v_1^7,v_2^7\right),\left(v_3^7,v_4^7\right),\left(v_1^9,v_2^9\right),\left(v_3^9,v_4^9\right)\right\}$。

基金项目

资助项目(新疆少数民族科技人才特殊培养计划)；科研项目(项目编号为2022D03002)。