图论 中，惠特尼定理 （英語：Whitney's theorem ），又称为惠特尼连通性定理 （Whitney's theorem on connectivity ）[1] 哈斯勒·惠特尼 于1932年[2] 2连通图 等价性质的定理，该定理提供了关于2连通图的不同点对之间的连通性质刻画，描述了2连通图的特殊性质[3]
惠特尼定理概述图 定理陈述
编辑
定理证明
编辑
因为任意两点之间均存在路径，于是
G
{\displaystyle G}
进一步，对于任意两点之间有至少存在两条内部不相交路径，所以考虑删除
G
{\displaystyle G}
G
{\displaystyle G}
G
{\displaystyle G}
G
{\displaystyle G}
u
,
v
∈
V
(
G
)
{\displaystyle u,v\in V(G)}
u
,
v
{\displaystyle u,v}
下面通过对
u
,
v
{\displaystyle u,v}
距离
d
(
u
,
v
)
{\displaystyle d(u,v)}
数学归纳法 证明：
对于
d
(
u
,
v
)
=
1
{\displaystyle d(u,v)=1}
u
v
{\displaystyle uv}
G
{\displaystyle G}
κ
(
G
)
≥
2
{\displaystyle \kappa (G)\geq 2}
惠特尼不等式 ，
λ
(
G
)
≥
κ
(
G
)
{\displaystyle \lambda (G)\geq \kappa (G)}
λ
(
G
)
≥
2
{\displaystyle \lambda (G)\geq 2}
G
{\displaystyle G}
G
{\displaystyle G}
G
−
u
v
{\displaystyle G-uv}
u
,
v
{\displaystyle u,v}
G
−
u
v
{\displaystyle G-uv}
u
,
v
{\displaystyle u,v}
G
{\displaystyle G}
u
,
v
{\displaystyle u,v}
假设对于
d
(
u
,
v
)
=
k
−
1
{\displaystyle d(u,v)=k-1}
G
{\displaystyle G}
u
,
v
{\displaystyle u,v}
d
(
u
,
v
)
=
k
{\displaystyle d(u,v)=k}
由于
u
,
v
{\displaystyle u,v}
k
{\displaystyle k}
G
{\displaystyle G}
u
,
v
{\displaystyle u,v}
P
{\displaystyle P}
P
{\displaystyle P}
k
{\displaystyle k}
P
{\displaystyle P}
v
{\displaystyle v}
w
{\displaystyle w}
w
{\displaystyle w}
d
(
u
,
w
)
=
k
−
1
{\displaystyle d(u,w)=k-1}
w
{\displaystyle w}
P
{\displaystyle P}
u
{\displaystyle u}
w
{\displaystyle w}
k
−
1
{\displaystyle k-1}
k
−
1
{\displaystyle k-1}
u
{\displaystyle u}
v
{\displaystyle v}
k
{\displaystyle k}
d
(
u
,
v
)
=
k
{\displaystyle d(u,v)=k}
u
,
w
{\displaystyle u,w}
u
,
w
{\displaystyle u,w}
P
,
P
′
{\displaystyle P,P'}
P
∪
P
′
{\displaystyle P\cup P'}
充分性的归纳证明 如果
v
∈
P
∪
P
′
{\displaystyle v\in P\cup P'}
v
{\displaystyle v}
u
{\displaystyle u}
v
{\displaystyle v}
u
{\displaystyle u}
v
{\displaystyle v}
如果
v
∉
P
∪
P
′
{\displaystyle v\notin P\cup P'}
G
{\displaystyle G}
G
−
w
{\displaystyle G-w}
u
,
v
{\displaystyle u,v}
u
,
v
{\displaystyle u,v}
Q
{\displaystyle Q}
Q
{\displaystyle Q}
P
{\displaystyle P}
P
′
{\displaystyle P'}
u
{\displaystyle u}
Q
{\displaystyle Q}
P
∪
w
v
{\displaystyle P\cup wv}
u
,
v
{\displaystyle u,v}
z
{\displaystyle z}
Q
{\displaystyle Q}
P
∪
P
′
{\displaystyle P\cup P'}
P
,
P
′
{\displaystyle P,P'}
z
{\displaystyle z}
P
{\displaystyle P}
(
u
⇝
z
)
⏟
P
∪
(
z
⇝
v
)
⏟
Q
{\displaystyle \underbrace {(u\rightsquigarrow z)} _{P}\cup \underbrace {(z\rightsquigarrow v)} _{Q}}
(
u
⇝
w
)
⏟
P
′
∪
w
v
{\displaystyle \underbrace {(u\rightsquigarrow w)} _{P'}\cup wv}
u
,
v
{\displaystyle u,v}
于是无论如何，当
d
(
u
,
v
)
=
k
{\displaystyle d(u,v)=k}
u
,
v
{\displaystyle u,v}
于是根据数学归纳法，当
G
{\displaystyle G}
u
,
v
∈
V
(
G
)
{\displaystyle u,v\in V(G)}
u
,
v
{\displaystyle u,v}
根据惠特尼定理的结论，可以得到关于2连通图的等价描述的推论：
图
G
{\displaystyle G}
割点 （即图
G
{\displaystyle G}
对于图
G
{\displaystyle G}
u
,
v
{\displaystyle u,v}
G
{\displaystyle G}
u
,
v
{\displaystyle u,v}
对于图
G
{\displaystyle G}
u
,
v
{\displaystyle u,v}
G
{\displaystyle G}
C
{\displaystyle C}
u
,
v
{\displaystyle u,v}
C
{\displaystyle C}
图
G
{\displaystyle G}
G
{\displaystyle G}
e
1
,
e
2
{\displaystyle e_{1},e_{2}}
G
{\displaystyle G}
C
{\displaystyle C}
e
1
,
e
2
{\displaystyle e_{1},e_{2}}
C
{\displaystyle C}
[4] 推论证明
编辑
描述1
⇔
{\displaystyle \Leftrightarrow }
描述2
⇔
{\displaystyle \Leftrightarrow }
描述4
⇔
{\displaystyle \Leftrightarrow }
u
,
v
∈
V
(
G
)
{\displaystyle u,v\in V(G)}
δ
(
G
)
≥
1
{\displaystyle \delta (G)\geq 1}
u
,
v
{\displaystyle u,v}
∃
u
x
,
v
y
∈
E
(
G
)
{\displaystyle \exists ux,vy\in E(G)}
u
x
,
v
y
{\displaystyle ux,vy}
若
u
x
∩
v
y
=
∅
{\displaystyle ux\cap vy=\varnothing }
u
x
,
v
y
{\displaystyle ux,vy}
u
x
,
v
y
{\displaystyle ux,vy}
u
,
v
{\displaystyle u,v}
若
u
x
∩
v
y
=
z
{\displaystyle ux\cap vy=z}
u
x
,
v
y
{\displaystyle ux,vy}
z
{\displaystyle z}
u
x
,
v
y
{\displaystyle ux,vy}
u
x
,
v
y
{\displaystyle ux,vy}
u
,
v
{\displaystyle u,v}
若
u
x
∩
v
y
=
u
v
{\displaystyle ux\cap vy=uv}
u
x
,
v
y
{\displaystyle ux,vy}
u
v
{\displaystyle uv}
u
v
{\displaystyle uv}
u
,
v
{\displaystyle u,v}
描述123
⇔
{\displaystyle \Leftrightarrow }
G
{\displaystyle G}
δ
(
G
)
≥
1
{\displaystyle \delta (G)\geq 1}
G
{\displaystyle G}
u
v
,
x
y
{\displaystyle uv,xy}
向
G
{\displaystyle G}
w
,
z
{\displaystyle w,z}
令
G
′
=
G
∪
{
w
,
z
}
∪
{
u
w
,
v
w
,
x
z
,
y
z
}
{\displaystyle G'=G\cup \{w,z\}\cup \{uw,vw,xz,yz\}}
G
′
{\displaystyle G'}
G
′
{\displaystyle G'}
G
{\displaystyle G}
G
′
{\displaystyle G'}
割集
S
{\displaystyle S}
{
w
,
z
}
{\displaystyle \{w,z\}}
S
−
{
w
,
z
}
{\displaystyle S-\{w,z\}}
G
{\displaystyle G}
G
{\displaystyle G}
|
S
|
≥
2
+
1
=
3
{\displaystyle |S|\geq 2+1=3}
|
S
|
≥
2
+
2
=
4
{\displaystyle |S|\geq 2+2=4}
{
u
,
v
,
x
,
y
}
{\displaystyle \{u,v,x,y\}}
|
S
|
≥
2
{\displaystyle |S|\geq 2}
S
{\displaystyle S}
G
{\displaystyle G}
|
S
|
≥
2
{\displaystyle |S|\geq 2}
G
′
{\displaystyle G'}
G
′
{\displaystyle G'}
k
{\displaystyle k}
expansion lemma ），它也在证明门格尔定理 中发挥了作用。[5]
那么根据描述3，对于
G
′
{\displaystyle G'}
C
{\displaystyle C}
w
,
z
{\displaystyle w,z}
C
{\displaystyle C}
w
,
z
{\displaystyle w,z}
u
w
,
v
w
,
x
z
,
y
z
{\displaystyle uw,vw,xz,yz}
C
{\displaystyle C}
C
{\displaystyle C}
G
{\displaystyle G}
u
w
v
{\displaystyle uwv}
u
v
{\displaystyle uv}
x
z
y
{\displaystyle xzy}
x
y
{\displaystyle xy}
u
v
,
x
y
{\displaystyle uv,xy}
影响及意义
编辑
惠特尼定理提供了对于2连通性的更具体的性质刻画，从而提供了另一种对于2连通性的具体证明方向。
参考文献
编辑
