证明 ${\forall}\ x, y$ 之间至少存在两条互相分离的路径是图是边双连通分量的必要性
即由图是边双连通分量,推出${\forall}\ x, y$ 之间至少存在两条互相分离的路径
首先,在一个边双连通分量里,对于任意两个点a
,b
连通,存在两种情况,a
和b
直接相连(没直接相连的点,图就没有边了),a
和b
间接通过别的点相连。先证明这两种情况a
到b
都不能只存在有重合的路径
反证法:假设a
到b
只存在n
$\ (n \geq 2)\ $条有重合边(即没互相分离)的路径($ n = 1 $显然不成立,只讨论$ n > 1$)
-
对于
a
,b
直接通过边c
连通这种情况,因为a
到b
只存在有重合边(即没互相分离)的路径,那么每条路径肯定都经过c
这条边,因为边c
这条路径只有一条边,没有互相分离的路径要求至少有一条边重合,当我们斩断这条边c
,a
和b
就不连通了,而边双连通分量不包含桥(即斩断一条边不影响图的连通性),即斩断边c
,a
和b
还在连通,这条新的路径一定不包含边c
,a
到b
有了两条相互分离的路径了,这与假设矛盾了。 -
对于
a
,b
间接连通,在a
到b
的任意一条路径中,肯定会存在情况1里的情况(即点a
和点c
直接相连,边记成f
,路径是acb
),那么我们斩断a
到c
这条边f
,由于a
,b
在一个边双连通分量里,a
到b
肯定存在另一条路径连通,由于c
到b
还连通也就和a
连通了,a
到c
在斩断了边f
后还在连通,也就是说还有一条没走边f
的路径,c
到a
就有了两条相互分离的路径了,与假设矛盾了。
结论:在边双连通分量里,${\forall} x, y\ $之间不能只存在n
$\ (n \geq 2)\ $条有重合边(即没互相分离)的路径
只有一条路径没法互相分离并与边双连通分量矛盾,至少有两条分离的路径和边双连通分量不矛盾(视频里证明充分性时证明过了),所以在一个边双连通分量里,${\forall}\ x, y$ 之间至少存在两条互相分离的路径
大佬,好像你这边循环论证了
这里用到了要证明的命题。。。