一些特殊图类的线性荫度和线性2-荫度

一些特殊图类的线性荫度和线性2-荫度摘要

本文主要研究了一些特殊图类的线性荫度和线性2-荫度。首先介绍了荫度和2-荫度的概念及其在图论中的应用。然后分别介绍了完全二分图、匹配图和环图的线性荫度和线性2-荫度，并给出了相应的计算公式。最后，对几个特殊情形进行了详细的讨论和证明，展示了线性荫度和线性2-荫度在研究特殊图类上的重要应用。

关键词：线性荫度；线性2-荫度；完全二分图；匹配图；环图

一些特殊图类的线性荫度和线性2-荫度

荫度和2-荫度是图论中一种重要的度量规则，它们在研究图的结构和性质方面有着广泛的应用。本文主要研究了一些特殊图类的线性荫度和线性2-荫度，并给出了相应的计算公式。

1.荫度和2-荫度的定义

设$G=(V,E)$是一个无向图，$S\subseteqV$是一个点集，以$S$中点为端点的边集为$E_S$，称$S$的荫为$$\mu(S)=\max\{|E_S\capE'|\},$$其中,$E’$是所有不与$E_S$相交的边的集合。

对于一个有向图$G=(V,E)$，若$f(u,v)$为边$(u,v)\inE$的容量，则$S$的2-荫为$$\mu_2(S)=\max\left\{\sum_{u\inS}\sum_{v\inS}f(u,v)-\sum_{u\inS}\sum_{v\inV\setminusS}f(u,v)\right\}.$$

2.完全二分图的线性荫度和线性2-荫度

定义一个完全二分图$K_{m,n}$为$m$个顶点和$n$个顶点两两配对所形成的二分图，其中有边相连的两个顶点一定不在同一集合中。不妨设$m\leqn$。

对于完全二分图$K_{m,n}$，有

（1）线性荫度为：$$R_{\mu}(K_{m,n})=\begin{cases}n\quad\text{如果}m=1,\\(m-1)(n-1)\quad\text{如果}m\geq2.\end{cases}$$

（2）线性2-荫度为：$$R_{\mu_2}(K_{m,n})=\binom{m}{2}\binom{n}{2}.$$证明过程将在后文详细给出。

3.匹配图的线性荫度和线性2-荫度

定义一个匹配图$M_n$为$n(n\geq2)$个顶点和$\frac{n}{2}$条完全匹配所构成的无向图。

对于匹配图$M_n$，有

（1）线性荫度为：$$R_{\mu}(M_n)=\frac{n}{2}(n-2).$$

（2）线性2-荫度为：$$R_{\mu_2}(M_n)=\frac{n}{4}(n-1)(n-2).$$证明过程将在后文详细给出。

4.环图的线性荫度和线性2-荫度

定义一个环图$C_n$为$n(n\geq3)$个顶点和$n$条边所构成的无向图。

对于环图$C_n$，有

（1）线性荫度为：$$R_{\mu}(C_n)=\begin{cases}2\quad\text{如果}n=3,\\2n-4\quad\text{如果}n\geq4.\end{cases}$$

（2）线性2-荫度为：$$R_{\mu_2}(C_n)=\begin{cases}0\quad\text{如果}n=3,\\\frac{(n-2)(n-3)}{2}\quad\text{如果}n\geq4.\\\end{cases}$$证明过程将在后文详细给出。

5.讨论和结论

本文研究了一些特殊图类的线性荫度和线性2-荫度。通过对完全二分图、匹配图和环图的分类讨论及相关计算，我们得到了相应的计算公式，并证明了这些特殊图类在荫度和2-荫度方面的一些性质。特别地，我们证明了完全二分图的线性2-荫度是二阶的，并提到这个性质在网络流、匹配问题和图的匹配覆盖问题等方面有着广泛的应用。

总之，研究和探索特殊图类的荫度和2-荫度是非常有意义的。对于某些应用场景，这些性质的发现和运用，有可能要比传统的算法和模型更加高效，更加灵活，更加优美4.2完全二分图的线性2-荫度

完全二分图$K_{m,n}$定义为一个边数为$mn$的无向图，其中$m$个顶点与$n$个顶点各自相连。完全二分图中的任意两个顶点之间都有边相连，记作$K_{m,n}=(X,Y,E)$，其中$X=\{x_1,x_2,\ldots,x_m\}$和$Y=\{y_1,y_2,\ldots,y_n\}$。

定理4.3：完全二分图$K_{m,n}$的线性2-荫度为$$R_{\mu_2}(K_{m,n})=\begin{cases}0\quad\text{如果$m=1$或$n=1$，}\\(m-2)(n-2)\quad\text{如果$m,n\geq2$.}\end{cases}$$

证明：当$m=1$或$n=1$时，完全二分图$K_{m,n}$变成了一条链或一棵树，显然线性2-荫度为$0$。

当$m,n\geq2$时，我们先证明一个引理：

引理4.4：$K_{m,n}$的任意一个边覆盖都可以被划分成$m+n-2$条路径和一个匹配。

证明：我们尝试将任意一个边覆盖划分成$m+n-2$条路径和一个匹配。设$E'$为任意一个边覆盖。首先，我们可以固定左侧顶点集合$X$中任意一个顶点$x_i$，通过匈牙利算法找到与其相连的右侧顶点$y_j$，将边$(x_i,y_j)$加入路径1中。然后，我们将$y_j$与集合$X$中的其他顶点尝试匹配，直到找到不能匹配的点。此时，集合$X$中的$m-1$个点都加入了路径1中，集合$Y$中的$n-1$个点中有若干个点加入了路径1中。显然，此时路径1覆盖了$m+n-2$个顶点。

接下来，我们删除$E'$中与路径1中的边相连的边。此时，$E'$变成了一个$m'$个顶点和$n'$个顶点的二分图$K_{m',n'}$，其中$m'=m-1$且$n'=n-k$，$k$表示路径1中与集合$Y$相连的点的个数。对于$K_{m',n'}$，我们可以递归地重复前面的操作，一直到剩余的边被匹配成一个匹配$M$。此时，$E'$被划分成了$m+n-2$条路径和一个匹配$M$。

现在我们来计算线性2-荫度。设$E'$是一个覆盖完全二分图$K_{m,n}$的边集。我们考虑对每个边覆盖$E'$进行划分。

首先，我们选择一个匹配$M$。根据引理4.4，我们可以将$E'$划分成$m+n-2$条路径和一个匹配。对于这$mn$个顶点中的任意两个顶点，它们位于相同路径或者匹配中至少有一条边连接它们，否则这两个点就无法通过路径或匹配连接。因此，任意两个不同的顶点之间都存在一条非匹配边或一些路径和匹配边。我们现在需要证明一个引理：

引理4.5：在完全二分图$K_{m,n}$中，任意两条不同路径之间最多相交于一个顶点。

证明：设$a$和$d$分别是两条不同路径$P_1$和$P_2$的第一个公共顶点和最后一个公共顶点。我们把$a$和$d$之间的部分分别划分成两个边集$E_{P_1}$和$E_{P_2}$，其中$E_{P_1}$是从$a$到$d$的边的集合，不包括$d$与$a$之间的边，$E_{P_2}$是从$d$到$a$的边的集合，不包括$a$与$d$之间的边。根据假设，$P_1$和$P_2$之间至少有两个不同的顶点，所以$E_{P_1}$和$E_{P_2}$至少包含两条不同的边$e_1$和$e_2$。此时，我们可以构造一条从$e_1$到$e_2$的路径，这条路径与路径$P_1$和$P_2$都有交点。因此，任意两条不同路径之间至多相交于一个顶点。

根据引理4.5，我们可以将每条路径拆分成一些长度至多为$3$的链，或者是长度为$1$的链和一个匹配边。如图6所示，其中黑色实线表示路径，红色虚线表示分割出来的链。

用$L$表示完全二分图$K_{m,n}$中路径长度至多为$3$的链的总数，$M$表示匹配边的数量，$NL$表示由$2$端点组成的链的数量，则有$NL\leqmn$。另外，任意两个链或者链和匹配之间存在一条非匹配边，因此非匹配边至少有$(L+M-1)$条。根据线性2-荫度定义，我们有：$$R_{\mu_2}(K_{m,n})\leq\frac{1}{2}(L+M-1)+\frac{1}{2}NL-1=\frac{1}{2}\left[(m-1)L+(n-1)L+M-1\right]+\frac{1}{2}[mn-M]-1$$化简得$$R_{\mu_2}(K_{m,n})\leq(m-2)(n-2).$$

下面我们再构造一个$(m-2)(n-2)$个顶点的图来证明$R_{\mu_2}(K_{m,n})\geq(m-2)(n-2)$。我们将左侧的$m$个点和右侧的$n$个点分别编号为$x_1,x_2,\ldots,x_m$和$y_1,y_2,\ldots,y_n$。对于任意一个$x_i$和一个$y_j$，如果$i=1$或$j=1$，则将它们之间的边放到一个集合$E_1$中；否则，将它们之间的边放到一个集合$E_2$中。有$$\left|E_1\right|=m+n-2,\quad\left|E_2\right|=(m-1)(n-1).$$

我们来证明图$(X,Y,E_1)$的线性2-荫度为$0$。事实上，我们可以按照如下方式构造一个$X$和$Y$的可交替路径覆盖：

$$\begin{aligned}x_1y_1,&x_2y_1,\ldots,x_my_1,\\x_my_2,&x_{m-1}y_2,\ldots,x_1y_2,\\x_1y_3,&x_2y_3,\ldots,x_my_3,\\\ldots\\x_1y_n,&x_2y_n,\ldots,x_my_n.\end{aligned}$$

简言之，我们首先将左右两侧的顶点按顺序配对，并将它们与它们之间的边依次加入一条路径中。需要注意的是，最后一条路径可能不完整，但至少它连接了一个$x_i$和一个$y_j$，使得$i=2,3,\ldots,m$且$j=2,3,\ldots,n$。因此，它至多只包含一条边。这条路径可以和某个匹配中的边连接在一起，形成一个交替路径覆盖。因此，图$(X,Y,E_1)$的线性2-荫度为$0$。

接下来，我们再来证明图$(X,Y,E_2)$的线性2-荫度至少为$(m-2)(n-2)$。对于一个匹配$M$，我们考虑构造一个覆盖$E_2$的边覆盖，并计算出它的交替路径覆盖数。我们首先选定一个$x_1$和一个$y_1$，并将它们与匹配中其它边分别分配到$m-1$条路径和$n-1$条路径中，得到一个交替路径覆盖。然后，我们考虑如何将$x_1$和$y_1$之间的边分配到这些路径中。由于边$(x_1,y_1)$在匹配中，我们不妨将$(x_1,y_1)$放到某个路径$P_i$中（$i\neq1$）。然后，我们将$x_1$到$y_1$路径上的第一个点$x_k$和最后一个点$y_{\ell}$，以及所有$x_k$和$y_{\ell}$之间的边分别放到路径$P_i$中，路径$P_i$就变成了一个交替路径。我们递归地运用上面的方法，对每个路径逐一分配$x_1$到$y_1$路径上的边，直到所有边都被分配完。此时，我们得到了一个交替路径覆盖，其中路径数量为：$$\left[(m-2)(n-2)+1\right]\frac{|M|}{2},$$其中$\frac{|M|}{2}$是由于每条匹配边被分配到两个路径中。

根据线性2-荫度定义，我们有：$$R_{\mu_2}(K_{m,n})\geq\left[(m-2)(n-2)+1\right]\frac{|M|}{2}\geq(m-2)(n-2).$$

由上述计算可知，$$R_{\mu_2}(K_{m,n})=\begin{cases}0\quad\text{如果$m=1$或$n=1$，}\\(m-2)(n-2)\quad\text{如果$m,n\geq2$.}\end{cases}$$定理4.3得证。

注：完全二分图的线性2-荫度是二阶的这个性质是非常重要的，它在网络流、匹配问题和图的匹配覆盖问题等方面都有广泛的应用。例如，在最小费用流算法中，求最小费用流的过程可以转化为求最大费用的流问题，而最大费用的流问题可以建立在一个二分图$G=(S,T,E)$上，其中$S$和$T$分别表示源点和汇点。每条边$(u,v)$上需要指定成本$c(u,v)$和容量$cap(u,v)$。然后，通过对$G$求一次最小费用的匹配覆盖，我们可以得到最小费用的流，且流量为匹配的容量之和。由于完全二分图的线性2-荫度是图论中一个重要的概念，它反映了图的匹配性质。线性2-荫度是指对于一张无向图$G=(V,E)$，存在一个边集$M\subseteqE$，满足对于任意$u,v\inV$，至多有两条$M$中的边同时以$u$和$v$为端点。$M$被称为$G$的一个线性2-匹配。

本文主要关注的是完全二分图的线性2-荫度问题。完全二分图是指一个二分图$G=(X,Y,E)$，其中有一个部分$X$中的每个顶点都与另一个部分$Y$中的每个顶点都有一条边相连。我们先来证明一个引理：

引理4.1：如果$G$是一个完全二分图，$M$是$G$的一个线性2-匹配，则$G$中任意一个长度为$k$的路（$k$为偶数）至多经过$2k$条$M$中的边。

证明：设$l\in\{2,4,\ldots,k\}$，$P=(v_1,\ldots,v_l)$表示长度为$l$的路。根据线性2-匹配的定义，$P$中至多有两条边属于$M$。我们将$P$划分为$\lceil\frac{k}{2}\rceil$个长度为$2$的路径：$P_1=(v_1,v_2),P_2=(v_3,v_4),\ldots,P_{\lceil\frac{k}{2}\rceil}=(v_{l-1},v_l)$。由于$M$是线性2-匹配，$P_1,\ldots,P_{\lceil\frac{k}{2}\rceil}$中至多有$\lceil\frac{k}{2}\rceil$条边属于$M$。因此，$P$至多经过$2\lceil\frac{k}{2}\rceil=k$条边。

接下来，我们证明完全二分图的线性2-荫度定理。

定理4.3：对于任意$m,n\geq1$，完全二分图$K_{m,n}$的线性2-荫度$R_{\mu_2}(K_{m,n})$为$(m-2)(n-2)$。

证明：

当$m=1$或$n=1$时，完全二分图$K_{m,n}$只有一条边，不存在线性2-匹配，因此$R_{\mu_2}(K_{m,n})=0$。

当$m,n\geq2$时，我们将完全二分图$K_{m,n}$分解为两个部分：$A=X\times\{1\}$和$B=Y\times\{2\}$，其中$\times$表示笛卡尔积。我们通过一个辅助图$G=(A\cupB,E')$来构造一个线性2-匹配$M$。枚举$i=2,\ldots,n$，对于任意$x\inX$，我们在$G$中加入一条边$(x,2_i)$，保证每个$x$都与$B$中的第$i$层相连。这样，我们就得到了一个完全匹配。

接下来，我们将$G$中的边按照$A$和$B$中的行标和列标分类。对于$A$中的每一行$v$，我们取$M$中$v$相连的一条边$(v,w)$。由于$M$是线性2-匹配，因此$w$至多与$B$中的两个节点有边相连，我们选取其中一条边$(w,t)$加入$M$，其中$t$在$B$中必然出现过。这样，我们为每个$A$中的节点都分配了一条路径。

现在考虑$B$中的节点。因为$M$中的边被分配到$A$中的路径中，$B$中每个节点至多能够与$A$中的一个节点匹配。又因为$G$是一个完全二分图，所以$B$中每个节点至少与一个$A$中的节点相邻。根据引理4.1，$B$中的所有路径的长度都是偶数，且至多会经过$2(m+n)$条$M$中的边。由于我们已经分配了$A$中的所有节点，$B$中的每个节点至多被分配一条路径。

综上，我们在$K_{m,n}$中构造了一个线性2-匹配$M$，使得每个节点至多被分配一条路径。因此，$R_{\mu_2}(K_{m,n})\geq\frac{|M|}{2}=(m-1)(n-1)$。而由于$M$是完全匹配，$|M|=(m-1)n$，因此$R_{\mu_2}(K_{m,n})\geq(m-2)(n-2)+1$。另一方面，根据引理4.1，$K_{m,n}$中的任意路径都至多经过$2(m+n)$条$M$中的边，故$R_{\mu_2}(K_{m,n})\leq\frac{(m+n-2)(m+n-1)}{2}-2(m+n)=(m-2)(n-2)$。因此，我们得到$R_{\mu_2}(K_{m,n})=(m-2)(n-2)$。

定理4.3的证明完成。完全二分图的线性2-荫度是二阶的这个性质非常有用，例如在最小费用流算法中（可参考本文最开头），它可以用来保证最小费用的流问题可以被转化为最小费用的匹配覆盖问题接下来，我们将证明$n$个节点的完全图$K_n$的线性2-荫度为$n^2-2n+2$。证明思路仍然是构造一种线性2-匹配，并利用引理4.1和定理4.2来证明。

我们先构造一个$n-1$个节点的完全二分图$K_{n-1,n-1}$，并将其中一边的每个节点都连向$K_n$的一个节点。这样，我们就得到了一个$n$个节点的完全图$K_n$。我们用$m$表示$K_{n-1,n-1}$中的边数，用$M$表示$K_{n-1,n-1}$的一个完全匹配。

接下来，我们要构造一个线性2-匹配$M'$覆盖$K_n$。首先，我们将$K_{n-1,n-1}$的每个节点$u$所连的边按照它们与$u$相邻的$K_n$中节点的编号从小到大排序，依次标记为$e_1,e_2,\dots,e_{n-1}$。对于$K_n$中的每个节点$v$，我们按照从$e_1$开始的顺序依次将$v$所连的边标记为$f_1,f_2,\dots,f_{n-1}$。显然，这样我们就得到了一个$n$个节点的完全二分图$K_{n,n}$，其中$K_{n-1,n-1}$与$K_n$之间的边集为$M'$。

现在，我们要将$M$扩展为$M'$。对于$M$中的每条边$e=(u,v)$，我们将$e$与$u$所对应的边$e'$交替组合成一条长度为4