DOI: 10.12677/aam.2025.142054, PDF, HTML, XML,  被引量    科研立项经费支持
作者: 赖锦城, 何伟骅^*：广东工业大学数学与统计学院，广东 广州
关键词: 完全独立生成树；完全二部图；线图；划分；Completely Independent Spanning Trees； Complete Bipartite Graph； Line Graph； Partition

文章引用：赖锦城, 何伟骅. 完全二部图的线图中的完全独立生成树[J]. 应用数学进展, 2025, 14(2): 81-92. https://doi.org/10.12677/aam.2025.142054

1. 引言

一个网络可以抽象为图 $\text{G}\left(\text{V}\left(\text{G}\right),\text{E}\left(\text{G}\right)\right)$ ，其中 $\text{V}\left(\text{G}\right)$ 表示顶点集， $\text{E}\left(\text{G}\right)$ 表示边集，分别代表服务器和它们之间的连接。本文中考虑的图是无向图且是简单图。

对于图G和树T，如果 $\text{V}\left(\text{T}\right)=\text{V}\left(\text{G}\right)$ ， $\text{E}\left(\text{T}\right)\subset \text{E}\left(\text{G}\right)$ ，且 $\left|\text{E}\left(\text{T}\right)\right|=\left|\text{V}\left(\text{T}\right)\right|-1$ ，则称T为G的一个生成树。在图G中，对于顶点u和v，假设 ${\text{P}}_1$ 和 ${\text{P}}_2$ 是连接顶点u到v的两条路径。如果 ${\text{P}}_1$ 和 ${\text{P}}_2$ 不共享任何边且不共享任何顶点(除了u和v)，则称 ${\text{P}}_1$ 和 ${\text{P}}_2$ 为内部节点不相交的路径。假设在G中有一组生成树 $\left\{{\text{T}}_1,{\text{T}}_2,\cdots ,{\text{T}}_{\text{k}}\right\}$ ，对于图G中任意两个不同顶点u和v，从u到v的路径都是内部节点不相交的路径，则这一组生成树被称为完全独立生成树(简称CISTs)，即在这组树中，任意两棵树的任意一对路径都是内部节点不相交的。

完全独立生成树在设计如计算机网络或通信网络时提供了一个重要的架构选择，用于增强网络的容错性[1]-[3]。例如，如果某一部分的网络出现故障，完全独立生成树确保网络的其它部分仍然能够维持基本的通信功能，从而减少了故障扩散的可能性。此外，完全独立生成树还被运用于IP网络中配置保护路由[4]-[8]。当网络密度足够高时，Moinet [9]等人表示可以找到更多的CIST。因此，在给定的图中构建若干CISTs，在实际的多个领域中提供了实用的解决方案和优化策略。

在给定图中构造两个CISTs已被证明是NP难问题[2]。此外，在文献[2]中，Hasunuma猜测在一个2n个顶点连通图G中存在n个CISTs。然而，Pétefalvi [10]提出了一个反例来反驳这一猜测。Pai等人[11]也提出了反例。因此，研究的重点转向了尽可能多地构造CISTs [12]。Pai等人[13]证明，在 ${\text{K}}_{\text{m},\text{n}}$ 中，当 $\text{m}\ge \text{n}\ge 4$ 时，存在n/2个CISTs。

我们将 $\text{V}\left(\text{G}\right)$ 划分为k个非空子集 $\left({\text{V}}_1,{\text{V}}_2,\cdots ,{\text{V}}_{\text{k}}\right)$ ，如果满足以下两个条件，则称其为CIST-划分[14]：

1) 每个子集 ${\text{V}}_{\text{i}}$ 形成的诱导子图是连通的；

2) 对于任意两个不同的子集 ${\text{V}}_{\text{i}}$ 和 ${\text{V}}_{\text{j}}$ ，我们定义一个二部图 $\text{B}\left({\text{V}}_{\text{i}},{\text{V}}_{\text{j}}\right)$ ，其边集包括所有连接 ${\text{V}}_{\text{i}}$ 中顶点与 ${\text{V}}_{\text{j}}$ 中顶点的边。这个二部图 $\text{B}\left({\text{V}}_{\text{i}},{\text{V}}_{\text{j}}\right)$ 必须满足：每一个连通组件H，有 $\left|\text{E}\left(\text{H}\right)\right|\ge \left|\text{V}\left(\text{H}\right)\right|$ ，这意味着 $\text{B}\left({\text{V}}_{\text{i}},{\text{V}}_{\text{j}}\right)$ 中不存在仅由树构成的连通组件。

Araki证明了k个CISTs的存在实际上等价于CIST划分 $\left({\text{V}}_1,{\text{V}}_2,\cdots ,{\text{V}}_{\text{k}}\right)$ 的存在[14]。

定理1 [14]一个连通图G有k个完全独立生成树，当且仅当存在一个 $\text{V}\left(\text{G}\right)$ 的CIST划分 $\left({\text{V}}_1,{\text{V}}_2,\cdots ,{\text{V}}_{\text{k}}\right)$ 。

给定一个图G，令 $\text{L}\left(\text{G}\right)$ 表示G的线图，其构造过程如下(图1)：

1) 对于图G中的每条边 $\left(\text{x},\text{y}\right)$ ，在 $\text{V}\left(\text{L}\left(\text{G}\right)\right)$ 中添加一个顶点 $\text{x}:\text{y}$ ；

2) 如果G中有两条边 $\left(\text{x},\text{y}\right)$ 和 $\left(\text{y},\text{z}\right)$ 相邻，则在 $\text{L}\left(\text{G}\right)$ 中，顶点 $\text{x}:\text{y}$ 和 $\text{y}:\text{z}$ 通过一条边连接。

近年来，线图在理论研究和实际应用中都被证明是一个良好的网络模型。关于线图的研究涉及图论中的各种基础问题，如边不相交的哈密顿回路[15]、可追溯性[16]、生成树的数量[17]等。此外，线图在

(a) (b)

Figure 1. A graph G and its line graph L(G)

图1. 图G及其线图L(G)

现代网络技术中扮演着重要角色，尤其是在数据中心网络设计中的应用。通过在原始网络的边上部署服务器，例如SWCube [18]和BCDC [19]，线图模型为网络设计提供了一个有效的结构框架，从而支持更高效的数据处理和信息流动。对于线图中完全独立生成树(CISTs)的研究也日益受到关注，例如完全图的线图[20]和环面网络的线图[21]。

在本文中，我们研究了完全二部图的线图中的完全独立生成树(CISTs)，并提出了一种在完全二部图的线图中构造多个CISTs的算法。本文的其余部分组织如下：第二节，我们介绍了在完全二部图的线图中构造CIST划分的算法，并展示了算法的正确性；第三节，我们通过实验应用该算法；第四节，我们给出结论。

2. 完全二部图的线图中的完全独立生成树

根据定理1，在一个连通图G中构造CISTs时，我们只需考虑构造G的CIST划分。由于线图的顶点是由原图的边构成的，因此将线图的顶点划分成CIST划分，实质上就是将原图的边划分。

我们提出了一种算法，称为CIST-P，用于构造 $\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)\left(\text{m}\ge \text{n}\ge 3\right)$ 的CIST划分，并证明该算法是正确的。我们将 ${\text{K}}_{\text{m},\text{n}}$ 的两个部分标记为 ${\text{V}}_{\text{a}}$ 和 ${\text{V}}_{\text{b}}$ 。

算法. CIST-P

输入：完全二部图 ${\text{K}}_{\text{m},\text{n}}$ 。 输出： $\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的CIST划分CP。 步骤1：将 ${\text{V}}_{\text{a}}$ 和 ${\text{V}}_{\text{b}}$ 中前n个顶点之间的边进行划分。初始化 ${\text{V}}_{\text{a}}$ 和 ${\text{V}}_{\text{b}}$ 的顶点为 $\left\{{\text{a}}_1,{\text{a}}_2,\cdots ,{\text{a}}_{\text{m}}\right\}$ 和 $\left\{{\text{b}}_1,{\text{b}}_2,\cdots ,{\text{b}}_{\text{n}}\right\}$ ，分别表示 ${\text{V}}_{\text{a}}$ 和 ${\text{V}}_{\text{b}}$ 的顶点集合。 1: $\text{k}=\lfloor \text{n}/2\rfloor$ 2: for $\text{i}=1$ to k do 3: $\text{EP}\left[\text{i}\right]=\varnothing$ /*采用数组的形式存储第i组划分包含的边*/

4: end for 5: for $\text{i}=1$ to k do 6: $\text{EP}\left[\text{i}\right]=\text{EP}\left[\text{i}\right]\cup \left\{\left({\text{a}}_{\text{i}},{\text{b}}_{\text{i}}\right)\right\}$ 7: for $\text{i}=\text{i}+1$ to $\text{i}+\text{k}$ do 8: $\text{EP}\left[\text{i}\right]=\text{EP}\left[\text{i}\right]\cup \left\{\left({\text{a}}_{\text{i}},{\text{b}}_{\text{j}}\right)\right\}$ 9: end for 10: for $\text{j}\in \left[1,\text{i}-1\right]\cup \left[\text{i}+\text{k}+1,2\text{k}\right]$ do 11: $\text{EP}\left[\text{i}\right]=\text{EP}\left[\text{i}\right]\cup \left\{\left({\text{a}}_{\text{i}+\text{k}},{\text{b}}_{\text{j}}\right)\right\}\cup \left\{\left({\text{a}}_{\text{j}},{\text{b}}_{\text{i}+\text{k}}\right)\right\}$ 12: end for 13: end for 步骤2：当n为奇数时进行调整。 14: if n is odd then 15: $\text{EP}\left[\text{k}+1\right]=\varnothing$ 16: for $\text{i}=1$ to k do 17: $\text{EP}\left[\text{i}\right]=\text{EP}\left[\text{i}\right]-\left\{\left({\text{a}}_{\text{k}+\text{i}},{\text{b}}_{\text{k}+\text{i}}\right)\right\}$ 18: $\text{EP}\left[\text{k}+1\right]=\text{EP}\left[\text{k}+1\right]\cup \left\{\left({\text{a}}_{\text{k}+\text{i}},{\text{b}}_{\text{k}+\text{i}}\right)\right\}$ 19: $\text{EP}\left[\text{i}\right]=\text{EP}\left[\text{i}\right]\cup \left\{\left({\text{a}}_{\text{k}+\text{i}},{\text{b}}_{\text{k}+1}\right)\right\}$ 20: end for 21: for $\text{i}=1$ to 2k do 22: $\text{EP}\left[\text{k}+1\right]=\text{EP}\left[\text{k}+1\right]\cup \left\{\left({\text{a}}_{\text{k}+1},{\text{b}}_{\text{i}}\right)\right\}$ 23: if $\text{i}\in \left[1,\text{k}\right]$ then 24: $\text{EP}\left[\text{k}+1\right]=\text{EP}\left[\text{k}+1\right]\cup \left\{\left({\text{a}}_{\text{i}},{\text{b}}_{\text{k}+1}\right)\right\}$ 25: end if 26: end for 27: end if 步骤3：构造 ${\text{V}}_{\text{a}}$ 中第 $\text{n}+1$ 个顶点到第m个顶点与 ${\text{V}}_{\text{b}}$ 的顶点之间的边划分。 28: for $\text{i}=\text{n}+1$ to m do 29: for $\text{j}=1$ to $\text{len}\left(\text{EP}\right)$ do 30: /* $\text{len}\left(\text{EP}\right)$ 是EP中所有元素的数量，即划分的数量*/ 31: $\text{EP}\left[\text{j}\right]=\text{EP}\left[\text{j}\right]\cup \left\{\left({\text{a}}_{\text{i}},{\text{b}}_{\text{j}}\right)\right\}$ 32: if n is odd then 33: if j is not equal to $\text{len}\left(\text{EP}\right)$ then 34: $\text{EP}\left[\text{j}\right]=\text{EP}\left[\text{j}\right]\cup \left\{\left({\text{a}}_{\text{i}},{\text{b}}_{\text{j}+\text{k}+1}\right)\right\}$ 35: end if 36: else 37: $\text{EP}\left[\text{j}\right]=\text{EP}\left[\text{j}\right]\cup \left\{\left({\text{a}}_{\text{i}},{\text{b}}_{\text{j}+\text{k}}\right)\right\}$ 38: end if 39: end for 40: end for 步骤4：在 $\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)$ 中构造CIST划分 41: $CP=\varnothing$ 42: for each set E in EP do 43: $C=\varnothing$ 44: for each edge $\left(\text{x},\text{y}\right)$ in E do 45: $\text{C}=\text{C}\cup \left\{\text{x}:\text{y}\right\}$

46: end for 47: $\text{CP}=\text{CP}\cup \left\{\text{C}\right\}$ 48: end for END

现在我们证明算法CIST-P输出的CP是 $\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的CIST划分。

定理2 假设EP是在算法CIST-P的第3步中得到的集合，CP是在算法CIST-P的第4步中得到的集合。那么，EP是 $\text{E}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的一个划分，而CP是 $\text{V}\left(\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)\right)$ 的一个划分。此外，CP是 $\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的一个CIST划分。

证明：设 $\text{t}=\lfloor \frac{\text{n}+1}{2}\rfloor$ 。

当n为偶数时， $\text{t}=\frac{\text{n}}{2}$ 。显然，对于 $1\le \text{i}\le \text{t}$ ，有 $\left|\text{EP}\left[\text{i}\right]\right|=2\left(\text{t}+1\right)+2\left(\text{n}-\text{t}-1\right)+2\left(\text{m}-\text{n}\right)=2\text{m}$ ，因此 ${\displaystyle {\sum }_{\text{i}=1}^t\left|\text{EP}\left[\text{i}\right]\right|}=2\text{m}\times \text{t}=\text{mn}$ 。根据完全二部图的定义， ${\text{K}}_{\text{m},\text{n}}$ 有 $\text{mn}$ 条边。因此， ${\displaystyle {\sum }_{\text{i}=1}^t\left|\text{EP}\left[\text{i}\right]\right|}=\left|\text{E}\left({\text{K}}_{\text{m},\text{n}}\right)\right|=\text{mn}$ 。对于任意 $\text{j}\left(1\le \text{j}\le \text{t}\right)$ ，以及 $1\le \text{i}<\text{j}\le \text{t}$ ，有 $\text{EP}\left[\text{i}\right]\cap \text{EP}\left[\text{j}\right]=\varnothing$ 。因此，EP是 $\text{E}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的一个划分。

当n为奇数时， $\text{t}=\frac{\text{n}+1}{2}$ 。显然，对于 $1\le \text{i}\le \text{t}-1$ ，有 $\left|\text{EP}\left[\text{i}\right]\right|=2\text{t}-1+2\left(\text{n}-\text{t}-1\right)+1+2\left(\text{m}-\text{n}\right)=2\text{m}-2$ 。对于 $\text{i}=\text{t}$ ，有 $\left|\text{EP}\left[\text{i}\right]\right|=2\text{n}-1+\left(\text{m}-\text{n}\right)=\text{m}+\text{n}-1$ 。因此， ${\displaystyle {\sum }_{i=1}^t\left|EP\left[i\right]\right|}={\displaystyle {\sum }_{i=1}^{t-1}\left|EP\left[i\right]\right|+\left|EP\left[t\right]\right|}=\left(2m-2\right)\times \left(t-1\right)+m+n-1=mn$ 。因此， ${\displaystyle {\sum }_{\text{i}=1}^t\left|\text{EP}\left[\text{i}\right]\right|}=\left|\text{E}\left({\text{K}}_{\text{m},\text{n}}\right)\right|=\text{mn}$ 。对于任意 $\text{j}\left(1\le \text{j}\le \text{t}\right)$ ，以及 $1\le \text{i}<\text{j}\le \text{t}$ ，有 $\text{EP}\left[\text{i}\right]\cap \text{EP}\left[\text{j}\right]=\varnothing$ 。因此，EP是 $\text{E}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的一个划分。

根据线图的定义，因为 $\text{EP}$ 是 $\text{E}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的一个划分，所以CP是 $\text{V}\left(\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)\right)$ 的一个划分。

设 $\text{t}=\lfloor \frac{\text{n}+1}{2}\rfloor$ ， $V_i=CP\left[i\right]$ 。

情况1. 当n是奇数时，根据算法CIST-P可得：

$V_i=\{\begin{array}{ll}\{a_1:b_{i+k},\cdots ,a_{i-1}:b_{i+k},a_i:b_i,\cdots ,a_i:b_{i+k},\hfill & \hfill \\ a_{i+1}:b_i,\cdots ,a_{i+k}:b_i,a_{i+k}:b_1,\cdots ,a_{i+k}:b_{i-1},\hfill & \hfill \\ a_{i+k}:b_{i+k+1},\cdots ,a_{i+k}:b_{2k+1},a_{i+k+1}:b_{i+k},\cdots ,a_{2k}:b_{i+k},\hfill & \hfill \\ a_{2k+2}:b_i,a_{2k+2}:b_{i+k+1},\cdots ,a_m:b_i,a_m:b_{i+k+1}\}\hfill & for1\le i\le k\hfill \\ \{a_i:b_{2k+1},\cdots ,a_k:b_{2k+1},a_{k+1}:b_{k+1},\hfill & \hfill \\ a_{k+2}:b_{k+2},\cdots ,a_{2k}:b_{2k},a_{2k+1}:b_1,\cdots ,a_{2k+1}:b_{2k+1},\hfill & \hfill \\ a_{2k+2}:b_k,a_{2k+3}:b_k,\cdots ,a_m:b_k\}\hfill & fori=k+1\hfill \end{array}$

首先，我们证明顶点集 ${\text{V}}_{\text{i}}$ 的诱导子图是连通的。对于 $1\le \text{i}\le \text{k}$ ，在 $\text{EP}\left[\text{i}\right]$ 中的边，如 $\left\{\left({\text{a}}_{2\text{k}+2},{\text{b}}_{\text{i}}\right),\left({\text{a}}_{2\text{k}+2},{\text{b}}_{\text{i}+\text{k}+1}\right),\cdots ,\left({\text{a}}_{\text{m}},{\text{b}}_{\text{i}}\right),\left({\text{a}}_{\text{m}},{\text{b}}_{\text{i}+\text{k}+1}\right)\right\}$ ，这些边是连通的，并且与边 $\left({\text{a}}_{\text{i}},{\text{b}}_{\text{i}}\right)$ 一起形成一个连通的子图。 $\text{EP}\left[\text{i}\right]$ 中的其余边都连接到边 $\left({\text{a}}_{\text{i}},{\text{b}}_{\text{i}}\right)$ 、 $\left({\text{a}}_{\text{i}},{\text{b}}_{\text{i}+\text{k}}\right)$ 或 $\left({\text{a}}_{\text{i}+\text{k}},{\text{b}}_{\text{i}}\right)$ 之一。由于这三条边是连通的，根据线图的定义，顶点集 ${\text{V}}_{\text{i}}\left(1\le \text{i}\le \text{k}\right)$ 的诱导子图是连通的。

对于 $\text{i}=\text{k}+1$ ，在 $\text{EP}\left[\text{i}\right]$ 中的边，如 $\left({\text{a}}_{\text{k}+\text{i}},{\text{b}}_{\text{k}+\text{i}}\right)\left(1\le \text{i}\le \text{k}\right)$ 与边 $\left({\text{a}}_{2\text{k}+1},{\text{b}}_{\text{k}+\text{i}}\right)$ 连接。 $\text{EP}\left[\text{i}\right]$ 中的边 $\left({\text{a}}_{2\text{k}+2},{\text{b}}_{\text{k}}\right),\left({\text{a}}_{2\text{k}+3},{\text{b}}_{\text{k}}\right),\cdots ,\left({\text{a}}_{\text{m}},{\text{b}}_{\text{k}}\right)$ 与边 $\left({\text{a}}_{\text{k}},{\text{b}}_{\text{k}}\right)$ 连接。除了边 $\left({\text{a}}_{\text{k}+\text{i}},{\text{b}}_{\text{k}+\text{i}}\right),\left({\text{a}}_{2\text{k}+2},{\text{b}}_{\text{k}}\right),\left({\text{a}}_{2\text{k}+3},{\text{b}}_{\text{k}}\right),\cdots ,\left({\text{a}}_{\text{m}},{\text{b}}_{\text{k}}\right)$ 之外，所有其他边都与边 $\left({\text{a}}_{2\text{k}+1},{\text{b}}_{2\text{k}+1}\right)$ 连接。

因此，顶点集 ${\text{V}}_{\text{i}}$ 的诱导子图是连通的。

(a) $1\le x,y\le k$ (b) $1\le x\le k,y=k$

Figure 2. Connected subgraphs of $B\left(V_x,V_y\right)$

图2. $B\left(V_x,V_y\right)$ 的连通子图

我们用 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 来表示由 ${\text{V}}_{\text{x}}$ 和 ${\text{V}}_{\text{y}}$ 形成的二部图。接下来，我们证明对于每个二部图 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ (其中 $1\le \text{x},\text{y}\le \text{k}+1$ ，且 $\text{x}\ne \text{y}$ )都没有树形组件。我们分以下情况进行讨论：

情况1.1 $1\le \text{x},\text{y}\le \text{k}$ ，不失一般性，假设 $\text{x}<\text{y}$ 。在 ${\text{V}}_{\text{x}}$ 中的所有顶点都与 ${\text{V}}_{\text{y}}$ 中一个顶点子集 ${\text{V}}_{\text{sy}}:\left\{{\text{a}}_{\text{x}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}},{\text{a}}_{\text{y}+\text{k}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}+1}\right\}$ 相邻。在 ${\text{V}}_{\text{y}}$ 中的所有顶点都与 ${\text{V}}_{\text{x}}$ 中一个顶点子集 ${\text{V}}_{\text{sx}}:\left\{{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{y}+\text{k}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{x}}:{\text{b}}_{\text{y}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}+1}\right\}$ 相邻。在 ${\text{V}}_{\text{sx}}$ 中，顶点 ${\text{a}}_{\text{y}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{y}+\text{k}}:{\text{b}}_{\text{x}+\text{k}}$ 与 ${\text{V}}_{\text{sy}}$ 中的顶点 ${\text{a}}_{\text{y}+\text{k}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}}$ 之间存在一个环，形成环 $\left\{{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{y}+\text{k}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{y}+\text{k}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}}\right\}$ 。在 ${\text{V}}_{\text{sx}}$ 中，顶点 ${\text{a}}_{\text{x}}:{\text{b}}_{\text{y}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}}$ 与 ${\text{V}}_{\text{sy}}$ 中的顶点 ${\text{a}}_{\text{x}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}}$ 之间也存在一个环，形成 $\left\{{\text{a}}_{\text{x}}:{\text{b}}_{\text{y}},{\text{a}}_{\text{x}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}},{\text{a}}_{\text{x}}:{\text{b}}_{\text{y}}\right\}$ 。此外， ${\text{V}}_{\text{x}}$ 中的顶点 ${\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}}$ ， ${\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}+1}$ ， ${\text{a}}_{2\text{k}}:{\text{b}}_{\text{x}+\text{k}}$ 与 ${\text{V}}_{\text{y}}$ 中的顶点 ${\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}}$ ， ${\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}+1}$ ， ${\text{a}}_{2\text{k}}:{\text{b}}_{\text{y}+\text{k}}$ 相连接，换句话说，存在一条路径 $\left\{{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}+1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{2\text{k}}:{\text{b}}_{\text{y}+\text{k}},{\text{a}}_{2\text{k}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{y}}:{\text{b}}_{\text{x}+\text{k}+1}\right\}$ 。因此，二部图 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 是连通的，连通分支就是其本身，并且没有树状分支。图2(a)显示了在这种情况下 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 的局部连通图。

情况1.2 $1\le \text{x}\le \text{k}$ ， $\text{ y}=\text{k}+1$ 。在 ${\text{V}}_{\text{x}}$ 中的所有顶点都与 ${\text{V}}_{\text{y}}$ 中一个顶点子集 ${\text{V}}_{\text{sy}}:\left\{{\text{a}}_{\text{x}}:{\text{b}}_{2\text{k}+1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{x}},{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{x}+\text{k}+1}\right\}$ 相邻。设 ${\text{V}}_{{\text{x}}_1}$ 为 ${\text{V}}_{\text{x}}$ 中一个顶点子集， ${\text{V}}_{{\text{x}}_1}=\left\{{\text{a}}_{\text{x}}:{\text{b}}_{\text{x}},\cdots ,{\text{a}}_{\text{x}}:{\text{b}}_{\text{x}+\text{k}}\right\}$ ，并且设 ${\text{V}}_{{\text{x}}_2}$ 为另一个子集， ${\text{V}}_{{\text{x}}_2}=\left\{{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_1,\cdots ,{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}-1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}+\text{k}+1},\cdots ,{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{2\text{k}+1}\right\}$ 。则 ${\text{V}}_{\text{y}}$ 中的任意顶点总能在 ${\text{V}}_{{\text{x}}_1}$ 或 ${\text{V}}_{{\text{x}}_2}$ 找到一个与之相邻的顶点，换句话说， ${\text{V}}_{\text{y}}$ 中的所有顶点都与 ${\text{V}}_{{\text{x}}_1}\cup {\text{V}}_{{\text{x}}_2}$ 中的某个顶点相邻。

由于 ${\text{V}}_{{\text{x}}_1}$ 中的所有顶点都与 ${\text{V}}_{\text{sy}}$ 中的顶点 ${\text{a}}_{\text{x}}:{\text{b}}_{2\text{k}+1}$ 相邻，并且 ${\text{V}}_{{\text{x}}_2}$ 中的所有顶点都与 ${\text{V}}_{\text{sy}}$ 中的顶点 ${\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}+\text{k}}$ 相邻。取 ${\text{V}}_{{\text{x}}_1}$ 中的顶点 ${\text{a}}_{\text{x}}:{\text{b}}_{\text{x}}$ 和 ${\text{V}}_{{\text{x}}_2}$ 中的顶点 ${\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{2\text{k}+1}$ ，设 ${\text{V}}_{\text{sx}}=\left\{{\text{a}}_{\text{x}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{2\text{k}+1}\right\}$ ，因此 ${\text{V}}_{\text{sx}}$ 与 ${\text{V}}_{\text{sy}}$ 中的所有顶点相连，意味着存在一条路径 $\left\{{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{x}+\text{k}+1},{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{x}},{\text{a}}_{\text{x}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{x}}:{\text{b}}_{2\text{k}+1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{2\text{k}+1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}+\text{k}}\right\}$ 。因此，二部图 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 是连通的，其连通分支就是其本身。此外，由于 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 中存在一个环 $\left\{{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{x}},{\text{a}}_{\text{x}}:{\text{b}}_{\text{x}},{\text{a}}_{\text{x}}:{\text{b}}_{2\text{k}+1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{2\text{k}+1},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}+\text{k}},{\text{a}}_{\text{x}+\text{k}}:{\text{b}}_{\text{x}},{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{x}}\right\}$ ，因此 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 中没有树状分支。图2(b)显示了在这种情况下 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)$ 的局部连通图。

情况2. 当n为偶数时，通过算法CIST-P可得

$\begin{array}{l}{\text{V}}_{\text{i}}=\{{\text{a}}_1:{\text{b}}_{\text{i}+\text{k}},\cdots ,{\text{a}}_{\text{i}-1}:{\text{b}}_{\text{i}+\text{k}},{\text{a}}_{\text{i}}:{\text{b}}_{\text{i}},\cdots ,{\text{a}}_{\text{i}}:{\text{b}}_{\text{i}+\text{k}},{\text{a}}_{\text{i}+1}:{\text{b}}_{\text{i}},\cdots ,{\text{a}}_{\text{i}+\text{k}}:{\text{b}}_{\text{i}},{\text{a}}_{\text{i}+\text{k}}:{\text{b}}_1,\cdots ,{\text{a}}_{\text{i}+\text{k}}:{\text{b}}_{\text{i}-1},{\text{a}}_{\text{i}+\text{k}}:{\text{b}}_{\text{i}+\text{k}},{\text{a}}_{\text{i}+\text{k}}:{\text{b}}_{\text{i}+\text{k}+1},\\ \cdots ,{\text{a}}_{\text{i}+\text{k}}:{\text{b}}_{2\text{k}+1},{\text{a}}_{\text{i}+\text{k}+1}:{\text{b}}_{\text{i}+\text{k}},{\text{a}}_{\text{i}+\text{k}+2}:{\text{b}}_{\text{i}+\text{k}},\cdots ,{\text{a}}_{2\text{k}}:{\text{b}}_{\text{i}+\text{k}},{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{i}},{\text{a}}_{2\text{k}+1}:{\text{b}}_{\text{i}+\text{k}},\cdots ,{\text{a}}_{\text{m}}:{\text{b}}_{\text{i}},{\text{a}}_{\text{m}}:{\text{b}}_{\text{i}+\text{k}}\}\end{array}$

此情况与情况1.1相似， ${\text{V}}_{\text{i}}$ 的诱导子图是连通的，并且对于每个二部图 $\text{B}\left({\text{V}}_{\text{x}},{\text{V}}_{\text{y}}\right)\left(1\le \text{x},\text{y}\le \text{k},\text{x}\ne \text{y}\right)$ 不存在树形组件。

总之，通过算法CIST-P得到的CP是 $\text{L}\left({\text{K}}_{\text{m},\text{n}}\right)$ 的CIST划分。证毕。□

3. 实验

在本节中，我们通过实验验证了算法CIST-P。我们将算法CIST-P应用于构建 $\text{L}\left({\text{K}}_{5,5}\right)$ 和 $\text{L}\left({\text{K}}_{7,5}\right)$ 中的CIST。

示例1. 以 $\text{L}\left({\text{K}}_{5,5}\right)$ 为例。首先，我们将 ${\text{K}}_{5,5}$ 的顶点标记为 ${\text{V}}_{\text{a}}=\left\{{\text{a}}_1,{\text{a}}_2,{\text{a}}_3,{\text{a}}_4,{\text{a}}_5\right\}$ 和 ${\text{V}}_{\text{b}}=\left\{{\text{b}}_1,{\text{b}}_2,{\text{b}}_3,{\text{b}}_4,{\text{b}}_5\right\}$ 。对除去与 ${\text{a}}_5$ 和 ${\text{b}}_5$ 关联的边以外的边进行划分，再对与 ${\text{a}}_5$ 和 ${\text{b}}_5$ 关联的边进行划分和调整，如图3所示。图表示前两组划分，图3(b)展示了最后一组边集的划分及划分的调整。算法第三步得到的划分集如下： $\{\left\{{\text{a}}_1:{\text{b}}_1,{\text{a}}_1:{\text{b}}_2,{\text{a}}_2:{\text{b}}_1,{\text{a}}_1:{\text{b}}_3,{\text{a}}_3:{\text{b}}_1,{\text{a}}_3:{\text{b}}_4,{\text{a}}_4:{\text{b}}_3,{\text{a}}_3:{\text{b}}_5\right\},\left\{{\text{a}}_2:{\text{b}}_2,{\text{a}}_2:{\text{b}}_3,{\text{a}}_3:{\text{b}}_2,{\text{a}}_2:{\text{b}}_4,{\text{a}}_4:{\text{b}}_2,{\text{a}}_4:{\text{b}}_1,{\text{a}}_1:{\text{b}}_4,{\text{a}}_4:{\text{b}}_5\right\},$ $\left\{{\text{a}}_3:{\text{b}}_3,{\text{a}}_4:{\text{b}}_4,{\text{a}}_5:{\text{b}}_1,{\text{a}}_1:{\text{b}}_5,{\text{a}}_5:{\text{b}}_2,{\text{a}}_2:{\text{b}}_5,{\text{a}}_5:{\text{b}}_3,{\text{a}}_5:{\text{b}}_4,{\text{a}}_5:{\text{b}}_5\right\}\}$ 。图4展示了 $\text{L}\left({\text{K}}_{5,5}\right)$ 的CIST划分，图5展示了 ${\text{K}}_{5,5}$ 对应的边划分。由此CIST划分，我们得到了 $\text{L}\left({\text{K}}_{5,5}\right)$ 的三个完全独立的生成树，如图6所示。

(a) (b)

Figure 3. The edge-partition of ${\text{K}}_{5,5}$

图3. ${\text{K}}_{5,5}$ 的边划分

(a)

(b) (c)

Figure 4. The CIST-partitions of $\text{L}\left({\text{K}}_{5,5}\right)$

图4. $\text{L}\left({\text{K}}_{5,5}\right)$ 的CIST划分

(a)

(b) (c)

Figure 5. The edge partition of ${\text{K}}_{5,5}$

图5. $\text{L}\left({\text{K}}_{5,5}\right)$ 的边划分

(a) ${\text{T}}_1$

(b) ${\text{T}}_2$ (c) ${\text{T}}_3$

Figure 6. The CISTs in $\text{L}\left({\text{K}}_{5,5}\right)$

图6. $\text{L}\left({\text{K}}_{5,5}\right)$ 的完全独立生成树

(a)

(b) (c)

Figure 7. The edge partition of ${\text{K}}_{7,5}$

图7. $\text{L}\left({\text{K}}_{7,5}\right)$ 的边划分

(a) ${\text{T}}_1$

(b) ${\text{T}}_2$ (c) ${\text{T}}_3$

Figure 8. The CISTs in $\text{L}\left({\text{K}}_{7,5}\right)$

图8. $\text{L}\left({\text{K}}_{7,5}\right)$ 的完全独立生成树

示例2. 以 $\text{L}\left({\text{K}}_{7,5}\right)$ 为例，图7展示了 ${\text{K}}_{7,5}$ 的边划分，基于此CIST划分，最终得到 $\text{L}\left({\text{K}}_{7,5}\right)$ 的三个完全独立的生成树，如图8所示。

4. 结论

在本文中，我们提出了一种算法CIST-P，用于在 $L\left(K_{m,n}\right)\left(m\ge n\ge 3\right)$ 中构造CISTs。我们从理论上证明了该算法的正确性，并通过实验验证了算法的有效性。算法适用于所有完全二部图的线图，但算法是否适用于其他类型的图，尚待研究。

基金项目

广东省自然科学基金面上项目(2021A1515012047)。

NOTES

^*通讯作者。

参考文献

[1]	Hasunuma, T. (2001) Completely Independent Spanning Trees in the Underlying Graph of a Line Digraph. Discrete Mathematics, 234, 149-157. https://doi.org/10.1016/s0012-365x(00)00377-0
[2]	Hasunuma, T. (2002) Completely Independent Spanning Trees in Maximal Planar Graphs. In: Goos, G., Hartmanis, J., Leeuwen, J. and Kučera, L., Eds., Graph-Theoretic Concepts in Computer Science, Springer, 235-245. https://doi.org/10.1007/3-540-36379-3_21
[3]	Lin, W., Li, X.-Y., Chang, J.-M. and Jia, X.H. (2023) Constructing Multiple CISTs on BCube-Based Data Center Networks in the Occurrence of Switch Failures. IEEE Transactions on Computers, 72, 1971-1984. https://doi.org/10.1109/TC.2022.3230288
[4]	Hussain, Z., Al Azemi, F. and Al Bdaiwi, B. (2024) Completely Independent Spanning Trees in Eisenstein-Jacobi Networks. The Journal of Supercomputing, 1-17.
[5]	Li, X., Lin, W., Liu, X., Lin, C., Pai, K. and Chang, J. (2022) Completely Independent Spanning Trees on BCCC Data Center Networks with an Application to Fault-Tolerant Routing. IEEE Transactions on Parallel and Distributed Systems, 33, 1939-1952. https://doi.org/10.1109/tpds.2021.3133595
[6]	Pai, K., Chang, R. and Chang, J. (2020) A Protection Routing with Secure Mechanism in Möbius Cubes. Journal of Parallel and Distributed Computing, 140, 1-12. https://doi.org/10.1016/j.jpdc.2020.02.007
[7]	Pai, K., Chang, R., Wu, R. and Chang, J. (2020) Three Completely Independent Spanning Trees of Crossed Cubes with Application to Secure-Protection Routing. Information Sciences, 541, 516-530. https://doi.org/10.1016/j.ins.2020.05.048
[8]	Tapolcai, J. (2012) Sufficient Conditions for Protection Routing in IP Networks. Optimization Letters, 7, 723-730. https://doi.org/10.1007/s11590-012-0455-y
[9]	Moinet, A., Darties, B., Gastineau, N., Baril, J. and Togni, O. (2017) Completely Independent Spanning Trees for Enhancing the Robustness in Ad-Hoc Networks. 2017 IEEE 13th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Rome, 9-11 October 2017, 63-70. https://doi.org/10.1109/wimob.2017.8115791
[10]	Péterfalvi, F. (2012) Two Counterexamples on Completely Independent Spanning Trees. Discrete Mathematics, 312, 808-810. https://doi.org/10.1016/j.disc.2011.11.015
[11]	Pai, K., Yang, J., Yao, S., Tang, S. and Chang, J. (2014) Completely Independent Spanning Trees on Some Interconnection Networks. IEICE Transactions on Information and Systems, 97, 2514-2517. https://doi.org/10.1587/transinf.2014edl8079
[12]	Cheng, B., Wang, D. and Fan, J. (2017) Constructing Completely Independent Spanning Trees in Crossed Cubes. Discrete Applied Mathematics, 219, 100-109. https://doi.org/10.1016/j.dam.2016.11.019
[13]	Pai, K., Tang, S., Chang, J. and Yang, J. (2013) Completely Independent Spanning Trees on Complete Graphs, Complete Bipartite Graphs and Complete Tripartite Graphs. In: Chang, R.-S., Jain, L.C. and Peng, S.-L., Eds., Smart Innovation, Systems and Technologies, Springer, 107-113. https://doi.org/10.1007/978-3-642-35452-6_13
[14]	Araki, T. (2013) Dirac’s Condition for Completely Independent Spanning Trees. Journal of Graph Theory, 77, 171-179. https://doi.org/10.1002/jgt.21780
[15]	Li, H., He, W., Yang, W. and Bai, Y. (2015) A Note on Edge-Disjoint Hamilton Cycles in Line Graphs. Graphs and Combinatorics, 32, 741-744. https://doi.org/10.1007/s00373-015-1606-6
[16]	Tian, T. and Xiong, L. (2018) Traceability on 2-Connected Line Graphs. Applied Mathematics and Computation, 321, 463-471. https://doi.org/10.1016/j.amc.2017.10.043
[17]	Dong, F. and Yan, W. (2016) Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs. Journal of Graph Theory, 85, 74-93. https://doi.org/10.1002/jgt.22048
[18]	Li, D. and Wu, J. (2015) On Data Center Network Architectures for Interconnecting Dual-Port Servers. IEEE Transactions on Computers, 64, 3210-3222. https://doi.org/10.1109/tc.2015.2389847
[19]	Wang, X., Fan, J., Lin, C., Zhou, J. and Liu, Z. (2018) BCDC: A High-Performance, Server-Centric Data Center Network. Journal of Computer Science and Technology, 33, 400-416. https://doi.org/10.1007/s11390-018-1826-3
[20]	Wang, Y., Cheng, B., Qian, Y. and Wang, D. (2022) Constructing Completely Independent Spanning Trees in a Family of Line-Graph-Based Data Center Networks. IEEE Transactions on Computers, 71, 1194-1203. https://doi.org/10.1109/tc.2021.3077587
[21]	Bian, Q., Cheng, B., Fan, J. and Pan, Z. (2022) Completely Independent Spanning Trees in the Line Graphs of Torus Networks. In: Lai, Y.X., et al., Eds., Algorithms and Architectures for Parallel Processing, Springer International Publishing, 540-553. https://doi.org/10.1007/978-3-030-95391-1_34