0 引言及概念

众所周知,连通图在通信网络、社交网络、交通网络等有着广泛的应用^[1-2]. 例如: 在通信网络中,即所有可能的信息传输线路构成的图中,点代表发射机,连接各点的边代表通信线路,或许网络中发射机的可靠性很高以至于不会瘫痪,但是通信线路可能会受到噪音干扰或其他干扰从而中断连接^[3-5]. 介于这种情况,人们希望网络不会因为删除了某些连接而变得不稳定、不连通 (如通讯中断、交通瘫痪等). 在数学的分支图论中,连通图占据着十分重要的研究地位,因此对连通图的深入研究不仅是数学理论的需要,同时更重要的是为研究实际网络结构提供可靠的理论依据和可行的技术手段. 本文以2-边连通图为例展开讨论,研究2-边连通图的结构并描述2-边连通图的特征.

关于2-边连通图的充分必要条件可以在许多文献中看到. West在他的书^[6]中给出了2-边连通图的6种等价性命题. Bondy和Murty在他们的书^[7]中,给出了关于2-边连通图特征的4个等价性命题. 这些相互等价的命题是从不同的角度来刻画2-边连通图. 本文整理了有关2-边连通图的若干充分必要条件,也为收集到的若干充分必要条件提供较为简单的证明. 更为重要的是,本文对2-边连通图定义了2种新运算,分别是割点均匀剖分运算和反三角形边收缩运算,由此两种运算得到了2个新定理,本文分别给出了它们的证明.

1^[7] 图G的边割E^*是图G的边子集,使得图G-E^*的分支数目大于图G的分支数目. 一个k边割是指包含k条边的边割. 图G的所有k边割中最小的k称为图G的边连通度. 若图G的边连通度大于等于k,则称图G为k-边连通的.

2^[6] 图G的一个耳朵是指图G中内部顶点的度数均为2的极大路. 图G的闭耳是图G中除一个顶点外其他顶点的度均为2的一个圈. 图G的一个耳边分解是满足下面条件的分解${{C}_{0}},{{P}_{1}},\cdots ,{{P}_{k}}:{{C}_{0}}$是一个圈,当$i\ge 1$时,${{P}_{i}}$要么是${{C}_{0}}\cup {{P}_{1}}\cup \cdots \cup {{P}_{i}}$的耳,要么是${{C}_{0}}\cup {{P}_{1}}\cup \cdots \cup {{P}_{i}}$的闭耳,称C₀为这个耳边分解的起始圈.

3^[6] 一条(u,v)-链是一系列圈C₁,C₂,… ,C_k,使得$ u \in V(C_{1})$和$v \in V(C_{k}) $,并且相继的两个圈C_i和${{C}_{i+1}}(1\le i\le k-1)$ 有且只有一个公共顶点,且当$|i-j|\neq1$时,圈C_i与圈C_j不相交 (示例见图 1).

4^[6] 对图G的一个顶点x和一个顶点子集U,一个(x,U)-迹扇是指从x到U的每个顶点的迹构成的集合,且此集合中任意2条迹在图G中无公共边(示例见图 2).

5^[6] 设图G是无割边的连通图,图G的块分解是指图G含有边不交的块$B_{1},B_{2},\cdots ,B_{m}$,使得$E(G)=\bigcup^m_{i=1} E(B_{i})$,并且对$i\neq j$,有$V(B_{i}) \cap V(B_{j})=\emptyset$,或者$V(B_{i}) \cap V(B_{j})=\{x\}$,其中x是图G的割点.

文献[7]给出如下的概念: 没有割点的连通图称为块. 若顶点与边的交错链 $W={{x}_{1}}{{e}_{1}}{{x}_{2}}{{e}_{2}},\cdots ,{{x}_{n-1}}{{e}_{n-1}}{{x}_{n}}$满足边e_i的2个端点是x_i和x_i+1,且有e_i=e_j,称W为途径. 若W中没有重复的边,但有x_i=x_j,且$i\neq 1,j\neq 1$,则称W为迹. 起终点相同且每条边均不重复的W称作闭迹. 图的极小边割称为键. 一条迹W的不是起、终点的顶点叫做W的内部顶点.

顶点均匀剖分运算是指: 对任意度数不小于4的顶点$u \in V(G)$,将顶点u剖分成2个顶点${u}',{u}''$,把u的度大致均匀地分配给顶点u'和顶点u'',使得2个顶点的度要么相等,要么相差一度; 然后,用一条边将顶点u'和顶点u''连在一起.

不难看到,对顶点u实施顶点均匀剖分运算后,顶点u'和顶点u''的度数之和是原来顶点u的度数加2. 图 3给出了顶点均匀剖分运算的一个例子,即对图 3(a)所示的图G的顶点y和顶点w实施均匀剖分运算,得到图 3(b)所示的图H.

1 定理及证明

定理 1 图G是2-边连通图当且仅当对图G中的每一个割点作均匀剖分运算所得新图是2-连通图 (示例见图-3).

证明 必要性 设图G是2-边连通图,图G的所有割点为$u_{1},u_{2},\cdots,u_{k}$,则每个割点在对应的图G的块中的度数至少是2. 对每一个割点作均匀剖分运算,将割点u_i剖分成2个顶点$u_{i}'$和$u_{i}''$,得新图H,使得每对顶点$u_{i}'$和$u_{i}''$构成图H的一个最小顶点割. 这是能够做到的,因割点u_i在块$G_i$中的度数至少是2,使得顶点$u_{i}'$与块$G_i$中的一个顶点相连,顶点$u_{i}''$与块$G_i$的一个顶点相连. 显然,图H为2-连通图. 此外,因图G是2-边连通的简单图,图H的每条边$u_{i}'u_{i}''$不在图H的任何一个三角形中.

充分性 对图G中的每一个割点$u_{i}$,图H有相应的顶点$u_{i}'$和$u_{i}''$,那么作均匀剖分运算的逆运算,即是收缩边$u'_{i}u''_{i}$,将顶点$u_{i}'$和顶点$u_{i}''$重合成原来的顶点$u_{i}$,从而得到图G. 注意到,边$u_{i}'u_{i}''$不在图H的任何一个三角形中,也就是说,收缩它不会产生图的割边. 因此,图G为2-边连通图.

2-连通图一定是2-边连通图,但2-边连通图不一定是2-连通图. 本文对2-边连通图定义了顶点均匀剖分运算,定理1使得非2-连通的连通图可以转化为2-连通图,使得2-连通图的若干性质与2-边连通图的若干性质可以对应起来,方便人们深入研究它们的性质. 下面列出2-边连通图的若干等价命题. 为了不与2-连通图的命题重复,以下总假定讨论的图有割点.

定理 2 设图G是无割边、有割点的连通图. 下面的命题相互等价.

(1)^[7] 图G是2-边连通图.

(2)^[7] 图G有块分解.

(3)^[6] 图G的任意2个顶点至少被2条无公共边的迹所连通.

(4)^[6] 对任意2个顶点$u,v \in V(G)$,图G中存在一条$(u,v)$-链.

(5)^[6] 图G有一条包含任意2个顶点的闭迹.

(6) 将图G中的路uwv换成边uv后得到的图是2-边连通图,其中w是2度顶点.

(7) 在图G添加一个新顶点w,并将顶点w与G中任意一对顶点u,v分别相连得到的图是2-边连通图.

(8)^[6] 对于图G的至少具有2个顶点的子集U和子集U外的一个顶点x,图G有一个(x,U)-迹扇.

(9)^[7] 图G的任意一个顶点和任意一条边都位于同一条闭迹上.

(10) 图G有一条最长闭迹T,使得G的任何一条边要么在T上,要么在一条起终点均在T上的(闭)迹上.

(11)^[6] 图G有一条包含任意2条边的闭迹.

(12)^[7] 对每一对满足顶点个数$|X|\geq 2$和$|Y|\geq 2$的不相交的顶点子集X和Y,图G含有2条边不交的迹,使得每条迹的起点在X中,终点在Y中,且这2条迹的内部顶点均不在X和Y中.

(13)^[8] 对于图G的任意2个顶点u,v和任意的一条边e,图G有包含边e的(u,v)-迹.

(14)^[8] 对于图G的任意3个顶点u,v,w,图G有包含顶点w的(u,v)-迹.

(15)^[6] 图G有耳边分解,并且G的每个圈均是图G的某个耳边分解的起始圈.

(16)^[8] 对于图G的任意3个顶点u,v和w,图G有不包含顶点w的(u,v)-迹.

(17)^[9] 图G的任意2条边都在图G的同一个键中.

证 明 以下用符号$(i)\Rightarrow (j)$表示从命题(i)推证命题(j),$1\leq i,j \leq 17$且$i\neq j$.

(1)⇒(2). 设图G有k个割点,对图G作块化运算: 设x是图G的一个割点,图$G-x$有分支$G_{1},G_{2},\cdots,G_{m}$. 作图$H_{j}$,使得$V({{H}_{j}})=V({{G}_{j}})\cup \{x\},E({{H}_{j}})=E({{G}_{j}})\cup \{xy|y\in V(G),xy\in E(G)\},j=1,2,\cdots ,m$. 得到有m个分支的图$G^{(1)}$,且图$G^{(1)}$的割点数目比图G的割点数目少一. 继续对图$G^{(1)}$作块化运算,直到图$G^{(k)}$没有割点,也就是说,图$G^{(k)}$的每个分支都是块,故图$G^{(k)}$即为图G的块分解图,命题(2)成立.

(2)⇒(3). 由命题(2)知,图G存在块分解. 则图G中每一个顶点至少属于一个块. 且块与块之间以图G的割点相互连接. 对于图G中任意2个顶点u,v,若u,v属于图G的同一个块,则在此块中必然存在两条连接u,v且无公共边的路. 若u,v分别属于图G的不同块$B_{i}$与$B_{j}(i\neq j)$,其中块$B_{i}$和$B_{i+1}$以割点$v_{i}$在图G中连接. 不妨设有块$B_{i},B_{i+1},\cdots ,B_{j}$,使得$B_{s}$与$B_{s+1}$只有唯一的公共顶点$v_{s}$,这个顶点也是图G的割点. 对$s=i,i+1,\cdots ,j$,在$B_{s}$中有2条内部不交的$(v_{s-1},v_{s})$-路$P_{s1}$和$P_{s2}$,这里$u\in V(B_{i})$且$u\ne {{v}_{i}},v\in V({{B}_{j}})$且$v\neq v_{j}$. 则从u到v由$P_{1}=\bigcup ^ j_{s=i} P_{s1},P_{2}=\bigcup ^ j_{s=i} P_{s2}$连通,显然$P_{1}$和$P_{2}$是2条无公共边的迹.

(3)⇒(4). 根据命题(3),对于任意的$u,v \in V(G)$,则u,v至少被2条无公共边的迹$W_{1}$与$W_{2}$所连,分析以下情形. 情形1,$W_{1}$与$W_{2}$之间除了u与v之外再无别的交点,则$W_{1},W_{2}$与端点u,v构成的闭迹W中可找出一个圈C,它是一个(u,v)-链. 情形2,$W_{1}$与$W_{2}$之间除了端点u,v外还有其他n个交点,记其交点为$x_{1},x_{2},\cdots ,x_{n}$(沿$W_{1}$迹从顶点u到顶点v的方向标记). 则u与$x_{1}$之间的$W_{1}$迹与$W_{2}$迹与端点$u,x_{1}$相连构成一个圈$C_{1}$. 同理,交点$x_{1},x_{2}$位于圈$C_{2}$上,以此类推,交点$x_{n}$和顶点v位于圈$C_{n+1}$上. 从而找到一个(u,v)-链,命题(4)得证.

(4)⇒(5). 根据命题(4),对图G中任意2个顶点u,v,图G中存在一条(u,v)-链. 而(u,v)-链也是一条闭迹,又因为顶点u,v的选取是任意的,故图G的任意2个顶点在图G的一个闭迹中.

(5)⇒(6). 设图G有路uwv,其中w是2度顶点. 根据命题(5),G有一条包含顶点u和w(或顶点v和w)的闭迹P,注意w是2度顶点,那么顶点v必在闭迹P中. 在G中将路uwv换成边uv,则很显然u与v仍然被包含在这个闭迹中. 故新得到的图H是2-边连通的. 有时,图H可能不再是简单图,是有重边的伪图.

(6)⇒(7). 给图G添加一个顶点w,将w与任意选择的一对顶点u和v相连得图H. 若H有割边xy,则$H-xy$有2个分支$H'$和$H''$,若有$u,v,w\in V(H')$,在图$H-xy$中用边uv替换路uwv得$H^{*}$. 根据命题(6),$H^{*}$是2-边连通图,这与$H^{*}$有2个分支矛盾,故图H无割边,H是2-边连通图.

(7)⇒(8). 设U是图G的至少有2个顶点的顶点子集,顶点$x\in V(G) \setminus U$. 对U中的任意2个顶点u,v,添加一个新顶点w,并将w与u,v分别连边得到新图H. 由命题(7),图H是2-边连通的,故顶点x和顶点w在同一条闭迹上. 则在图$H-w=G$中,有2条无公共边的(x,u)-迹和(x,v)-迹,由于选取顶点u,v是任意的,从而证得图G有一个(x,U)-迹扇.

(8)⇒(9). 任取图G的一个顶点x和一条边$e=uv$. 令$U=\{u,v\}$. 命题(8)指出,图G有一个(x,U)-迹扇. 根据(x,U)-迹扇的定义,图G有边不交的(x,u)-迹和(x,v)-迹,它们与边$e=uv$构成图G的一条闭迹. 证得命题(9).

(9)⇒(10). 设图G的最长闭迹为T,若边e在最长闭迹上,证毕. 若边e不在最长闭迹T上,则取T上的一个顶点u,由命题(9)可知顶点u与边e位于图G的同一条闭迹W上. 若W与T有一个交点,则边e在一条起终点均在T上的闭迹; 若W与T有$k (k \geq 2)$个交点,边e位于一条起点和终点均在T上的迹.

(10)⇒(11). 情形1: 若2条边$e_{1},e_{2}$均在图G的最长闭迹T上,则命题(11)成立. 情形2: 若边$e_{1}$在最长闭迹T上,而边$e_{2}$不在,根据命题(10),$e_{2}$位于一条起终点均在T上的(闭)迹W,则$T\cup W$是一个包含边$e_{1},e_{2}$闭迹. 情形3: 若边$e_{1}$和边$e_{2}$均不在T上,命题(10)已证$e_{i}$在一个起终点均在T的(闭)迹$W_{i}(i=1,2)$上,从而$T\cup W_{1} \cup W_{2}$是一个包含边$e_{1},e_{2}$的闭迹.

(11)⇒(12). 设图G的2个顶点子集|X|,|Y|有顶点个数$|X|\geq2$和$|Y|\geq2$. 情形1: 如果顶点子集X中的2个顶点$x_{1},y_{1}$也是图G的边$e_{1}$的顶点,即$e_{1}=x_{1}y_{1}$; 顶点子集Y中的2个顶点$x_{2},y_{2}$也是图G的边$e_{2}$的顶点,有$e_{2}=x_{2}y_{2}$. 那么,由命题(11)知,边$e_{1}$和边$e_{2}$同在图G的一条闭迹上,故至少由X到Y至少有2条边不交的迹,如果X和Y之间的每条迹的内部顶点不是全在X和Y时,例如$W=x_{1}e_{1}u_{1}e_{2}u_{2},\cdots,e_{n}u_{n}y_{1}$是X和Y之间的迹. 选择W的子迹$W'$,使得$|V(W')\cap X|=1,|V(W')\cap Y|=1$,命题(12)成立. 情形2: 如果顶点子集X或Y中没有2个顶点是图G的某条边的端点. 那么,给图G添加2条边$e_{X}=x_{1}x_{2}$和$e_{Y}=y_{1}y_{2}$,其中$x_{1},x_{2} \in X$和$y_{1},y_{2} \in Y$,得到新图$H=G+e_{X}+e_{Y}$. 相同于情形1的证明,命题(12)证毕.

(12)⇒(13). 对于图G的任意2个顶点u,v和任意一条边$e=xy$. 令$ X=\{u,v\}$和$Y=\{x,y\} $,根据命题(12),图G有经过X到Y的2条边不交且内部顶点不在X和Y中的(u,x)-迹$W_{1}$和(v,y)-迹$W_{2}$,则$W_{1}+xy+W_{2}$是一条包含边e的(u,v)-迹.

(13)⇒(14). 对图G的任意3个顶点u,v,w,设顶点w是边e的一个端点,由命题(13),知图G中包含边e的(u,v)-迹. 显然,这条迹包含了顶点w,也就是命题(14)得证.

(14)⇒(15). 从图G中的任意一个圈C出发,建立图G的一个耳边分解. 设图$G_{i}$是连续添加第i个耳后得到的图G的子图,若$G_{i}\neq G $,则可以选出$E (G_{i})$的一条边uv,选择顶点$w \in V(G)-V(G_{i})$使得w与u以及v的距离都最小. 根据命题(14),对于任意3个顶点u,v,w,图G有包含顶点w的(u,v)-迹. 此条(u,v)-迹有$G_{i}$中的2个顶点,并且每个顶点恰好位于(u,v)-迹的一端,因为w与u和v的距离都最小,(u,v)-迹就是一条(u,v)-路,也就是一个耳朵. 故可以把(u,v)-路添加到$G_{i}$中得到图G的更大的子图$G_{i+1}$,其中(u,v)-路是子图$G_{i+1}$的耳朵. 如果到某子图$G_{k}$时,有$V(G_{k})=V(G)$,且$E(G)\setminus E(G_{k})\neq \emptyset$,则可给子图$G_{k}$添加$E(G)\setminus E(G_{k})$中的所有边. 在包含完图G的所有边后,此过程结束,即给出图G的一个耳边分解.

(15)⇒(16). 由命题(15)知,图G存在耳边分解$C_{0},P_{1},\cdots,P_{k}$. 任取顶点$u,v \in V(G_{i})$和顶点$w \in V(G)-V(G_{i})$. 在构造耳边分解的过程中,存在图G的一条不经过耳边分解圈$C_0$的且包含顶点w的(u,v)-迹. 对应地,存在一条经过耳边分解圈$C_0$的不包含顶点w的(u,v)-迹.

(16)⇒(17). 任取图G的2条边${{e}_{i}}={{x}_{i}}{{y}_{i}}(i=1,2)$. 根据命题(16),图G有不包含顶点$x_i$的$(y_1,y_2)$-迹${{W}_{i}},i=1,2$. 同理,图G有不包含顶点$y_i$的$(x_1,x_2)$-迹${{T}_{i}},i=1,2$. 则有2个集合$S=V(T_1)\cap V(T_2)\supset \{x_1,x_2\}$和$U=V(W_1)\cap V(W_2)\supset \{y_1,y_2\}$. 显然,顶点子集S不含顶点$y_1,y_2$,顶点子集U不含顶点$x_1,x_2$. 扩充顶点集合S,U为2个更大的不交的连通顶点集$S',U'$,使得$V(G)=S'\cup U'$,以及$y_1,y_2\not\in S'$和$x_1,x_2\not\in U'$,且顶点集$S'$和顶点集$U'$之间的边的数目最少,这些边形成图G的边子集$E^*$. 显然,$E^*$包含边$e_{1}$和边$e_{2}$. 因$G-E^*$不连通,它有2个分支$G',G''$,使得$V(G')=S'$和$V(G'')=U'$. 故$E^*$是图G的一个键.

(17)⇒(1). 根据命题(17),图G的任意2条边都位于图G的同一个键中. 键为图的最小边割,即说明图G的键中最少有2条边. 这说明图G为2-边连通图.

综上论证,本定理得证.

反三角形边收缩运算: 对$e=uv \in E(G)$,若e不在图G的任何一个三角形中,则收缩边e使其2个端点重合为一个顶点$w_{uv}$,所得图记为$G\cdot e = G \cdot uv$. 如图 4所示,收缩图$G_1$中的粗边得到图 $G_2$,继续收缩图 $G_2$ 的粗边得到图$G_3$,如此下去,可将图 $G_1$ 收缩图至图 $G_5,G_5$ 的所有边都包含在某一个三角形中. 如果一个图的每条边都是某个三角形的边,则称这样的图为全边三角形图. 显然,当图G是连通图时,它的全边三角形图是2-边连通图. 完全图和极大平面图都是全边三角形图. 关于极大平面图,有著名平面图四色猜想(1997年被计算机证明,但至今没有数学证明),以及唯一可着色极大平面图猜想.

定理 3 G 是 2-边连通图当且仅当经过一系列反三角形边收缩运算后得到连通图H,使得H是全边三角形图.

证 明 充分性 显然,只要从收缩到最后的全边三角形图H原路返回到图G,且每一个返回步骤产生的图是2-边连通图.

必要性 因为图G是2-边连通图,对G作反三角形边收缩运算时. 因为反三角形边收缩运算不产生割边,边收缩后的图是2-边连通图. 对所有不在三角形中的边进行边收缩运算,直到每条边都包含在某个三角形中时,收缩过程结束. 最终得到的图H是全边三角形图. 显然,H也是2-边连通图.

2 总结

本文给出了若干2-边连通图的等价性命题. 如果对定理2中的等价命题进行两两等价性证明,将要写$C^2_{17}=136$个证明. 为此,我们设计了简单的方案进行定理2的证明. 在本文所有的命题中,将定理2中的迹替换成路,就得到2-连通图的若干等价命题. 除定理2的命题(1)为定义性命题外,其余的均为结构性命题. 命题(12)是在命题(3)的基础上对图G中2条不相交的迹的端点作了更为严格的要求. 命题(5),命题(9)和命题(11)都是从2-边连通图的本质结构出发,探索2-边连通图中顶点与顶点,顶点与边,边与边之间的位置关系. 命题(6)与命题(7)分别是指对2-边连通图的点和边进行代换、添加运算后仍然保持2-边连通性. 命题(8)与命题(15)和命题(17)从迹扇、耳边分解和键的定义出发展开讨论. 命题(13)、命题(14)和命题(16)则从2-边连通图的结构中探索任意2个顶 点之间有无包含某个顶点或某条边的迹.

本文的创新点在于定理1和定理3,以及定理2中的命题(10). 定理1定义了割点均匀剖分运算,定理3定义了反三角形边收缩运算. 根据定理3,每一个2-边连通图是对某个全边三角形图实施一系列顶点剖分的结果,从而给出一种构造2-边连通图的方法. 定理2的命题(10)研究了2-边连通图的最长闭迹与此图的任一条边之间的位置关系. 以上等价命题从多个角度对2-边连通图的特征进行了刻画. 这里要指出,定理2中的等价命题的相互推证会有其他的简单方案,也就是说,本文的证明方案不一定是最简单的. 基于数学的严谨、优美观点,寻找定理2的最简单的证明方案仍然是一项有意义的工作. 我们不能证明，不存在不同于本文列举的其他的2-边连通图的等价命题.