冒泡排序星图中边容错的两个不相交的圈覆盖问题研究

Research on Edge-Fault-Tolerant Two-Disjoint-Cycle-Cover in Bubble-Sort Star Graphs

摘要: $n$ 维冒泡排序星图$B{S}_n$ 是一个($2n-3$ )-正则二部图，具有$n!$ 个顶点。图中存在两个不相交的圈$C_1$ 和$C_2$ ，并且这些圈能够覆盖图中的所有顶点，则被称为图的两个不相交的圈覆盖。如果对于任意边集$F\subseteq E\left(G\right)$ 且$\left|F\right|\le k$ ，在$G-F$ 中存在两个顶点不相交的圈$C_1$ 和$C_2$ ，它们的顶点数加起来正好等于图的顶点数，则被称为$k$ -边容错两个不相交的圈覆盖。本文证明对于$n\ge 4$ 时，冒泡排序星图是存在($2n-5$ )-边容错两个不相交的圈覆盖。

Abstract: The $n$ -dimensional bubble-sort star graph $B{S}_n$ is known to be a ($2n-3$ )-regular bipartite graph with $n!$ vertices. The property where there exist two disjoint cycles $C_1$ and $C_2$ that together cover all the vertices of the graph is called the two disjoint cycle cover of the graph. Let $F$ be an edge set in the bubble-sort star graph with $F\subseteq E\left(G\right)$ , $\left|F\right|\le k$ , there exist two disjoint cycles $C_1$ and $C_2$ in $G-F$ , and their combined vertex count equals the total number of vertices in the graph, this is referred to as the $k$ -edge-fault-tolerant two disjoint cycle cover. This paper proves that for $n\ge 4$ , the bubble-sort star graph is a ($2n-5$ )-edge-fault-tolerant two disjoint cycle cover.

1. 引言

在并行计算和分布式计算网络中，图结构，特别是其中的圈和路径，扮演着至关重要的角色。图中的圈和路径不仅是理论研究中的基础概念，更在实际应用中用于描述和设计高效的通信和数据流结构。网络中的圈结构通常被用作算法设计中的关键组件，尤其是在设计低通信成本和高效率的分布式算法时。因此，图的圈结构，特别是那些具有特定拓扑性质的图，成为了计算机科学、网络设计以及图论研究中的重要研究对象。圈结构的研究在网络设计中尤为重要，它能够有效地解决资源分配、调度优化以及通信路径规划等问题。随着研究的深入，许多学者开始关注如何在特定图类中构建和利用这些圈结构，诸如圈嵌入、圈覆盖、2-因子等问题成为了图论研究的热点。尤其是在二部图、哈密尔顿图以及特殊拓扑结构的图中，研究者们发现了许多令人惊讶的性质，这些性质不仅丰富了图论的理论体系，还为实际网络的设计提供了有力支持。设$G=G\left(V_0\cup V_1,E\right)$ 是一个二部图，其中两个部分集顶点集$V_0$ 和$V_1$ 的大小相等。$G$ 是哈密尔顿可连接的[1]，如果对于任何两个位于不同部分集的顶点$v_0\in V_0$ 和$v_1\in V_1$ ，存在一条哈密尔顿路径。图的两个不相交的圈(Two disjoint cycles)，指的是图中存在两个圈，它们是顶点不相交的，即这两个圈没有共享任何顶点或边。每个圈本身是一个独立的循圈，但这两个圈之间是完全不相交的。图的两条不相交的圈覆盖性(Two disjoint cycle cover)，指的是图中存在两个不相交的圈，并且这些圈能够覆盖图中的所有顶点。具体来说，存在两个顶点不相交的圈$C_1$ 和$C_2$ ，它们的顶点数加起来正好等于图的顶点数。$G$ 被称为k-边容错两条不相交的圈覆盖，如果对于任意边集$F\subseteq E\left(G\right)$ 且$\left|F\right|\le k$ ，在$G - F$ 存在两个顶点不相交的圈$C_1$ 和$C_2$ ，它们的顶点数加起来正好等于图的顶点数。

星图和泡排序图[2] [3]都是具有高度对称性和递归结构的Cayley图，并具有其他有用的拓扑性质。最近，冒泡排序星图$B{S}_n$ ，一种结合了泡排序图和星图特征的混合图，引起了大量研究兴趣。图1展示了$B{S}_2$ 、$B{S}_3$ 和$B{S}_4$ 的结构。冒泡排序星图的精确定义将在下一节给出。

对于冒泡排序星图：Guo等[4]研究了冒泡排序星图的边双圈性，而冒泡排序星图的两条不相交圈覆盖双圈性在[5]中进行了探讨。由换位生成树生成的Cayley图的边容错双圈性在[6]中进行了讨论。此外，还有许多研究涉及其他性质，如额外连通性、条件可诊断性、容错最大局部连接性等(有关更多细节，请参见[7]-[18])。

定理1. 当$n \ge 4$ ，$B{S}_n$ 是$\left(2n-5\right)$ -边容错两个不相交圈覆盖的。

本文组织结构如下：在第二部分，我们给出冒泡排序星图的精确定义以及冒泡排序星图的基本性质；在第三部分我们给出主要结果的证明。

Figure 1. The bubble-sort star graphs $B{S}_2$ , $B{S}_3$ and $B{S}_4$

图1. 冒泡排序星图$B{S}_2$ ，$B{S}_3$ 和$B{S}_4$

2. 预备知识

我们定义冒泡排序星图的顶点集为$V\left(B{S}_n\right)$ ，令$V\left(B{S}_n\right)=P\left(n\right)$ ，此时$P\left(n\right)$ 是1到$n$ 的全排列，因此，冒泡排序星图有$n!$ 个顶点。而冒泡排序星图的边集定义为$E\left(B{S}_n\right)$ ，令 $E\left(B{S}_n\right)=\left\{\left(u,v\right):v=u\circ \left(1,i\right)\text{for}i\in \left\{2,3,\cdots ,n\right\},\text{or}v=u\circ \left(i-1,i\right)\text{for}i\in \left\{3,4,\cdots ,n\right\},u,v\in V\left(B{S}_n\right)\right\}$ 。这里的 $u\circ \left(i,j\right)$ 代表的是让顶点$u$ 的第$i$ 个元素交换到第$j$ 个元素得到新的排列。因此，冒泡排序星图的边是由两个顶点的两种交换方式得到，第一种方式是第1个元素跟第$i$ 个元素交换，第二种方式是第$i-1$ 个元素与第$i$ 个元素交换，很容易得到$B{S}_n$ 是$\left(2n-3\right)$ 正则的。举个例子，如果$B{S}_n$ 的其中一个顶点是53412，按照第一种交换方式可以得到其中一个新的顶点43512，按照第二种交换方式可以得到其中一个新的顶点54312。对于$1\le i\le n$ ，我们还定义$B{S}_n$ 的某个顶点$x$ 的第$i$ 个元素为$x\left[i\right]$ 。举个例子，如果$B{S}_n$ 的其中一个顶点是536412，那么$x\left[1\right]=5$ ，$x\left[2\right]=3$ ，$x\left[3\right]=6$ ，$x\left[4\right]=4$ ，$x\left[5\right]=1$ ，$x\left[6\right]=2$ 。

为了方便起见，我们定义了冒泡排序星图中的两种类型的对边。如果$x\left[n-1\right]=y\left[n-1\right]$ 且$x\left[n\right]=y\left[n\right]$ ，则边$e_1=xy$ 被称为第一类对边。如果$x\left[n-1\right]=u\left[n\right]$ ，$x\left[n\right]=u\left[n-1\right]$ ，$y\left[n-1\right]=v\left[n\right]$ 且$y\left[n\right]=v\left[n-1\right]$ ，则${e^{\prime }}_1=uv$ 被称为$e_1$ 的第一类耦合对边，而边$xu$ 和$yv$ 被称为第一类耦合边。如果$x\left[i\right]=y\left[i+1\right]$ 且$x\left[i+1\right]=y\left[i\right]$ 且$i \ge 2$ ，则边$e_2=xy$ 被称为$e_1$ 的第二类对边。此外，如果$x\left[1\right]=u\left[n\right]$ ，$x\left[n\right]=u\left[1\right]$ ，$y\left[1\right]=v\left[n\right]$ 且$y\left[n\right]=v\left[1\right]$ ，则${e^{\prime }}_2=uv$ 被称为第二类耦合对边，而边$xu$ 和$yv$ 被称为第二类耦合边。

例如，在$B{S}_5$ 中，对于两个顶点$x=42531$ 和$y=45231$ ，它们形成的边$e = xy$ 既是第一类对边，也是第二类对边。其第一类耦合对边为${e^{\prime }}_1=u_1{v}_1$ ，其中$u_1=42531$ ，$v_1=45213$ ，而其第二类耦合对边为${e^{\prime }}_2=u_2{v}_2$ ，其中$u_2=12534$ ，$v_2=15234$ 。第一类耦合边为(42531, 42513)和(45231, 45213)，第二类耦合边为(42531, 12534)和(45231, 15234)。对边、耦合对边和耦合边共同形成一个$C_4$ (长度为4的圈)。此外，在$B{S}_n$ 中，一旦确定了对边，第一类或第二类耦合对边和耦合边是唯一确定的。显然，第一类和第二类对边及其耦合对边都位于子图$B{S}_n\left(i\right)$ 内。同时，所有耦合边充当子图之间的连接边，称为外部边。由第一类对边或耦合对边形成的顶点对总是位于同一子图$B{S}_n\left(i\right)$ 内，而由第二类对边或耦合对边形成的顶点对不一定位于同一子图内。

此外，根据定义，$B{S}_n$ 是一个在对称群上的Cayley图，其生成元集为 $\left\{\left(1,2\right),\left(2,3\right),\cdots ,\left(n-1,n\right),\left(1,3\right),\left(1,4\right),\cdots ,\left(1,n\right)\right\}$ 。Tchuente [19]证明了由换位生成的对称群上的Cayley图在$n\ge 4$ 时是哈密尔顿可连接的。因此，$B{S}_n$ 在$n\ge 4$ 时是哈密尔顿可连接的。

引理2. 对于$B{S}_n$ 中的任意两条第一类对边$e_1$ 和$e_2$ ，在$B{S}_n$ 中存在一个包含$e_1$ 和$e_2$ 的哈密尔顿回路。

证明：Kikuchi [20]证明了泡排序图$B_n$ 存在一个包含边$e_1$ 和$e_2$ 的哈密尔顿回路。由于$B_n$ 是$B{S}_n$ 的一个生成子图，并且任何第一类对边都属于$E\left(B_n\right)$ ，因此结论成立。 □

推论3. 设$S\subseteq \left\{1,2,\cdots ,n\right\}$ ，且$n\ge 4$ ，并且设$e=uv$ 是$B{S}_n\left(i\right)$ 中的一条第一类对边，其中$i\in S$ 。那么，存在一个圈$C$ ，它经过边$e$ 并且包含每个$j\in S$ 的$B{S}_n\left(j\right)$ 中的所有顶点。

证明：设$\left|S\right|=k$ ，并且存在一个任意顺序$p_1{p}_2\cdots p_k$ ，使得$p_1=i$ 。在每个$B{S}_n\left(p_m\right),m=1,2,\cdots ,k$ 中，我们选择两条第一类配对边$e_m$ 和$f_m$ ，使得$e_1=e$ 且$e_m$ 是$f_{m-1}$ 的第一类耦合配对边。根据引理2，在每个$B{S}_n\left(p_m\right),m=1,2,\cdots ,k$ 中存在一个回路$C_m$ ，它包含边$e_m$ 和$f_m$ 。通过用第一类耦合对边替换第一类对边$e_m,m=2,3,\cdots ,k$ 及其第一类耦合对边$f_m,m=1,2,\cdots ,k-1$ ，我们得到一个圈$C$ ，它包含边$e$ 并且包含每个$j\in S$ 的$B{S}_n\left(j\right)$ 中的所有顶点，如图2所示。 □

Figure 2. The Hamiltonian cycle of Corollary 3

图2. 推论3的哈密顿回路

引理4. 设$S\subseteq \left\{1,2,\cdots ,n\right\}$ 且$n\ge 4$ 。$u$ 和$v$ 是位于不同二分集中的两个顶点，分别位于$B{S}_n\left(j_1\right)$ 和$B{S}_n\left(j_2\right)$ 中，其中$j_1,j_2\in S$ 且$j_1\ne j_2$ 。假设在$B{S}_n$ 中存在一个边集$F$ ，满足$\left|F\right|\le 2n-7$ ，并且对于每个$j\in S$ ，$B{S}_n\left(j\right)-F$ 是哈密尔顿可连接的。那么，存在一条从$u$ 到$v$ 的路径，该路径包含所有$B{S}_n\left(j\right)$ 中的顶点，对于所有$j\in S$ 。

证明：设$\left|S\right|=k$ 且$p_1{p}_2\cdots p_k$ 是$S$ 上的一个排列，使得$p_1=j_1$ 且$p_k=j_2$ 。在$B{S}_n\left(i\right)$ 和$B{S}_n\left(j\right)$ 之间的边数为$2\left(n-2\right)!$ ，并且$i,j\in \left\{1,2,\cdots ,n\right\},i\ne j$ ，其中一半的边位于$B{S}_n\left(i\right)$ 的一个部分集和$B{S}_n\left(j\right)$ 的另一个部分集之间。由于对于$n\ge 4$ ，有$\left(n-2\right)!>2n-7\ge \left|F\right|$ ，我们可以找到顶点$u_1,u_2,\cdots ,u_k$ 和$v_1,v_2,\cdots ,v_k$ ，使得$u_1=u$ ，$v_k=v$ ，$u_1,\cdots ,u_k$ 位于同一个部分集，$v_1,\cdots ,v_k$ 位于另一个部分集，$u_j,v_j$ 是$B{S}_n\left(p_j\right)$ 中的顶点，并且对于$j=1,2,\cdots ,k-1$ ，$v_j$ 与$u_{j+1}$ 相邻(见图3)。由于$B{S}_n\left(p_j\right)-F$ 中存在一条从$u_j$ 到$v_j$ 的哈密尔顿路径$P_j$ ，因此可以通过路径$P_1,\cdots ,P_k$ 和边$v_j{u}_{j+1}$ ，对于$j=1,2,\cdots ,k-1$ 来构造所需的路径，见图3。 □

Figure 3. A path starts from u and ends at v

图3. 从u出发，终点为v的路径

3. 主要结果证明

现在，我们通过归纳假设方法证明定理1。当$n=4$ ，我们很容易得出结论。而对于$n\ge 5$ ，我们假设$B{S}_{n-1}$ 满足结论。设$F$ 是一个容错边集，且$\left|F\right|\le 2n-5$ 。然后，我们要证明$B{S}_n$ 在不经过$F$ 中的边依然有两条不相交的圈覆盖性。

Case 1. $\left|F\cap E\left(B{S}_n\left(i\right)\right)\right|\le 2n-7$ 对于任何$i=1,\cdots ,n$ 。当$j=1,2,\cdots ,n$ ，根据归纳假设，每个$B{S}_n\left(j\right)-F$ 都是具有两条不相交的圈覆盖性。任取一个$j_1$ ，设$B{S}_n\left(j_1\right)-F$ 中的两个圈$C_1$ 和$C_2$ ，此时的外部边只有两条，因此，根据推论3，$C_1$ 中必定可以找到一条第一类对边$e_1$ 使得圈${C^{\prime }}_1$ 经过$e_1$ 并且包含每个 $k\in S,S\subseteq \left\{1,2,\cdots ,n\right\}\setminus \left\{j_1\right\}$ 的$B{S}_n\left(k\right)$ 中的所有顶点。因此，${C^{\prime }}_1$ 和$C_2$ 构成了$B{S}_n\left(n\right)$ 中的两个不相交的圈且包含了冒泡排序星图中所有的顶点，如图4所示。

Figure 4. The two cycles of Case 1

图4. Case 1的两个圈

Case 2. $2n-7<\left|F\cap E\left(B{S}_n\left(j\right)\right)\right|\le 2n-5$ ，对于$j \in \left\{1,2,\cdots ,n\right\}$ 。此时，考虑任意的$F_1$ ，其中$F_1\subset F$ 且$\left|F_1\right|=2n-7$ 。根据归纳假设，$B{S}_n\left(j\right)-F_1$ 必定有两个不相交的圈$C_1$ 和$C_2$ 。设$F-F_1$ 由剩余的两条边$e_1=uv$ 和$e_2=xy$ 组成。如果两条边都不在这两个圈上，情况就如Case 1一样，因此我们现在讨论$C_1$ 、$C_2$ 和$e_1$ 和$e_2$ 的2个子情况。

Case 2.1. 当$e_1$ 和$e_2$ 分别在两个不同的圈上，假定$e_1$ 在$C_1$ 上，而$e_2$ 在$C_2$ 上，反之亦然。在$e_1=uv$ 的两个端点$u$ 和$v$ 分别找到与其它$B{S}_{n-1}$ 的邻点$u_1$ 和$v_1$ ，此时根据外部邻点会产生两种情况。

Case 2.1.1. 第一种情况如果$u_1$ 和$v_1$ 是在同一个子图$B{S}_n\left(j_1\right)$ 上，很明显能看出此时的$u_1$ 和$v_1$ 只能是$u$ 和$v$ 的第一类耦合对边。因为冒泡排序星图$B{S}_n$ 是哈密尔顿图，在$B{S}_n\left(j_1\right)$ 上必定能找到包含$u_1$ 和$v_1$ 的圈$C_3$ ，同理，也可找到包含$e_2=xy$ 的两个端点$x$ 和$y$ 的邻点$x_1$ 和$y_1$ 的圈$C_4$ ，$x_1,y_1\in B{S}_n\left(j_2\right)$ 。分别在$C_3$ 和$C_4$ 分别找到圈中其中一条第一类对边$e_3$ 和$e_4$ ，设$S\subset \left\{1,2,\cdots ,n\right\}$ ，找到$S_1\subset S-j-j_1-j_2$ ，然后根据推论3，存在一个圈$C_5$ ，它经过$e_3$ 并且包含每个$k\in S_1$ 的$B{S}_n\left(k\right)$ 中的所有顶点，同理也能找到存在一个圈$C_6$ ，它经过$e_4$ 并且包含每个$k\in S\setminus \left\{S_1,j,j_1,j_2\right\}$ 的$B{S}_n\left(k\right)$ 中的所有顶点。此时的$B{S}_n-F$ 的所有顶点可由两个圈覆盖成，分别是$C_1-e_1+C_3-u_1{v}_1+C_5-e_3$ 和$C_2-e_2+C_4-x_1{y}_1+C_6-e_4$ 。如图5。此时的第一个圈由$B{S}_n\left(a_1\right)\cap B{S}_n\left(a_2\right)\cap \cdots \cap B{S}_n\left(a_m\right)\cap B{S}_n\left(j_1\right),m\in S_1$ 以及$C_1$ 组成，而第二圈由 $B{S}_n\left(b_1\right)\cap B{S}_n\left(b_2\right)\cap \cdots \cap B{S}_n\left(b_l\right)\cap B{S}_n\left(j_2\right),l\in S\setminus \left\{S_1,j,j_1,j_2\right\}$ 以及$C_2$ 组成，两部分的子图以及$B{S}_n\left(j\right)$ 刚好构成$B{S}_n$ 的$n$ 个子图，根据冒泡排序图的性质，因此每个圈的顶点都不会重复，保证了它们是不相交的，下列的证明也是类似，就不再赘述。

Case 2.1.2. 第二种情况如果$u_1$ 和$v_1$ 分别在两个子图$B{S}_n\left(q_1\right)$ 和$B{S}_n\left(q_2\right)$ 上，同理也能找到$x_1$ 和$y_1$ 分别在两个子图$B{S}_n\left(q_3\right)$ 和$B{S}_n\left(q_4\right)$ 上，设$S \subset \left\{1,2,\cdots ,n\right\}$ ，找到$S_1\subset S-j-q_3-q_4$ ，根据引理4，存在一条从$u_1$ 到$v_1$ 的路径$P_1$ ，该路径包含所有$B{S}_n\left(k\right)$ 中的顶点，对于所有的$k\in S_1$ ，同理也在一条从$x_1$ 到$y_1$ 的路径$P_2$ ，该路径包含所有$B{S}_n\left(k\right)$ ，对于所有的$k\in S\setminus \left\{S_1,j,q_1,q_2\right\}$ 。此时的$B{S}_n-F$ 的所有顶点可由两个圈覆盖成，分别是$C_1-e_1+P_1$ 和$C_2-e_2+P_2$ ，如图6。

Case 2.2. 当$e_1$ 和$e_2$ 都在同一个圈上，假定$e_1$ 和$e_2$ 都在$C_1$ 上，反之亦然，此时有两种情况。

Case 2.2.1. 第一种是$e_1$ 和$e_2$ 有同一个交点，也就是$e_1=us,e_2=sy$ 。找到$u$ 和$s$ 的外部邻点$u_1$ 和$s_1$ ，$u_1\in B{S}_n\left(j_1\right)$ ，$s_1\in B{S}_n\left(j_2\right)$ ，根据引理4，能够找到一条从$u_1$ 到$s_1$ 包含$B{S}_n\left(j_1\right),B{S}_n\left(j_2\right)$ 中所有顶点的路径$P_1$ 。接下来找到$s$ 的另一个外部邻点$s_2$ ，此时满足$s_2\in B{S}_n\left(j_3\right),j_3\ne j_2$ ，同时找出$y$ 的外部邻点$y_1,y_1\in B{S}_n\left(j_4\right)$ 。如果这些外部邻点属于同一个子图，则如上面2.1的证明类似，这里不再重复。根据引理4，找到一条从$s_2$ 到$y_1$ 包含所有$B{S}_n\left(k\right)$ 中的顶点，对于所有$k\in S\setminus \left\{j,j_1,j_2\right\}$ 的路径$P_2$ 。此时的$B{S}_n-F$ 的所有顶点可由两个圈覆盖成，分别是$C_1-e_1-e_2+u{u}_1+P_1+s{s}_1+s{s}_2+P_2+y{y}_1$ 和$C_2$ ，如图7。

Figure 5. The two cycles of Case 2.1.1

图5. Case 2.1.1的两个圈

Figure 6. The two cycles of Case 2.1.2

图6. Case 2.1.2的两个圈

Figure 7. The first cycle of Case 2.2.1

图7. Case 2.2.1的第一个圈

Case 2.2.2. 第二种情况是$e_1$ 和$e_2$ 不邻接，设$e_1=uv,e_2=xy$ 。找到$u$ 和$v$ 的外部邻点$u_1$ 和$v_1$ ，$u_1\in B{S}_n\left(j_1\right)$ ，$v_1\in B{S}_n\left(j_2\right)$ ，根据引理4，能够找到一条从$u_1$ 到$v_1$ 包含$B{S}_n\left(j_1\right),B{S}_n\left(j_2\right)$ 中所有顶点的路径$P_1$ 。同时找出$x$ 的外部邻点$x_1,x_1\in B{S}_n\left(j_3\right)$ 和$y$ 的外部邻点$y_1,y_1\in B{S}_n\left(j_4\right)$ 。再根据引理4，找到一条从$x_1$ 到$y_1$ 包含所有$B{S}_n\left(k\right)$ 中的顶点，对于所有$k\in S\setminus \left\{j,j_1,j_2\right\}$ 的路径$P_2$ 。此时的$B{S}_n-F$ 的所有顶点可由两个圈覆盖成，分别是$C_1-e_1-e_2+u{u}_1+P_1+v{v}_1+x{x}_1+P_2+y{y}_1$ 和$C_2$ ，如图8。

Case 3. 对于$n\ge 5$ ，设$F\subseteq E\left(B{S}_n\right)$ ，其中每条边$f\in F$ 是外部边，即$f$ 是第一类耦合边或第二类耦合边。我们知道每个$B{S}_n\left(i\right),i\in \left\{1,2,\cdots ,n\right\}$ 是哈密尔顿可连接的，$B{S}_n$ 是$\left(2n-3\right)$ -正则的，并且$B{S}_n\left(i\right)$ 和$B{S}_n\left(j\right)$ 之间的边数为$2\left(n-2\right)!,i,j\in \left\{1,2,\cdots ,n\right\},i\ne j$ 。由于对于$n\ge 5$ ，有$\left|F\right|=2n-5<2\left(n-2\right)!$ ，因此可以容易地在每个$B{S}_n\left(i\right)$ 中构造哈密尔顿路径，并将这些路径与一些非故障的外部边组合起来，从而得到哈密尔顿回路$C$ 。从这个$C$ 中任意找到两个顶点$u$ 和$v$ ，使它们满足的第一类耦合对边$u_1{v}_1$ 连接的耦合边不在$F$ 中，此时的$B{S}_n-F$ 的所有顶点可由两个圈覆盖成，第一个圈是从$u$ 不经过$v$ 的另一边经过$C$ 中顶点到达$u_1$ 再经过$u{u}_1$ 回到$u$ ，另一个圈则是从$v$ 不经过$u$ 的另一边经过$C$ 中顶点到达$v_1$ 再经过$v{v}_1$ 回到$v$ 。 □

Figure 8. The first cycle of Case 2.2.2

图8. Case 2.2.2的第一个圈

4. 结论

本文详细探讨了$n$ 维冒泡排序星图$B{S}_n$ 在图论中的特殊性质，证明了当$n\ge 4$ ，$B{S}_n$ 是$\left(2n-5\right)$ -边容错的两个不相交圈覆盖性，由于$B{S}_n$ 是$2n-3$ 正则，所以某个点删掉多于$2n-5$ 条边时，必定没有圈结构，因此这一结果不仅是理论上严谨的，而且也是最优的。圈结构的嵌入在互联网络中的应用，特别是在并行处理领域，已经成为当前计算机网络设计中的一个热门研究方向。研究是否其他常见的网络拓扑结构也能实现类似的圈覆盖特性，具有重要的理论和实践意义。

随着对复杂网络结构认识的不断深入，尤其是在分布式计算和大规模并行计算环境下，如何通过图的圈结构来优化网络的连接性和容错性，逐渐成为研究的关键问题。冒泡排序星图作为一种具有高度对称性和递归结构的特殊图，在理论研究和实际应用中展示了巨大的潜力。在未来的研究中，我们将进一步探讨更多常见的网络模型在实现两条不相交圈覆盖全圈性方面的可行性，尤其是那些尚未得到充分研究的网络模型。

NOTES

^*通讯作者。