§6.3 完美对集
°
奇分支和偶分支:奇数个顶点的分支称为奇分支;偶数个顶点的分
支称为偶分支。用
o(G)
表示 G 的奇分支的个数。
定理 6.4(Tutte 定理):图 G 有完美对集当且仅当
o G−S ≤ S ,
对所有
S ⊂ V
成立。
(6.6)
证:显然只要对简单图证明这个定理就行了。
首先假设 G 有完美对集 M。设 S 是 V 的一个真子集,并设
G
1
,G
2
,
⋯,G
n
是
G−S
的奇分支,因为
G
i
是奇分支,所以
G
i
的某一顶点
u
i
一定
在 M 下和 S 的一个顶点
v
i
配对(见图 6.6)。所以,由于
{v
1
,v
2
,⋯,v
n
}
⊆ S
,因而有
o G−S = n = | v
1
,
v
2
,⋯,v
n
| ≤ S
。
反之,假设 G 满足(6.6)式,但没有完美对集,则 G 是没有完美对集
的极大图
G
∗
的生成子图。由于
G−S
是
G
∗
−S
的生成子图,所以
o(G
∗
−S) ≤ o(G−S)
。因而由(6.6)式有
o
G
∗
−S
≤ S ,
对所有
S ⊂ V
G
∗
成立。
(6.7)
特别地,置
S = ∅,o
G
∗
= 0
,因而
υ
G
∗
是偶数。
用 U 表示
G
∗
中度为
υ−1
的顶点集。由于当
U = V
时,
G
∗
显然有完
美对集,因此可以假定
U ≠ V
。我们将证明:
G
∗
−U
是完全图的不相
交的并图。假若不然,
G
∗
−U
的某一分支不是完全图,则在此分支里
存在顶点
x,y
和
z
,使得
xy ∈ E
G
∗
,yz ∈ E
G
∗
和
xz ∉ E(
G
∗
)
。此外,
由 于
y ∉ U
, 在
G
∗
−U
中 存 在 顶 点 w , 使 得
yw ∉ E G
∗
个v只能和个u对应,如果和多个u对应就是完美对集
评论0