定理9.2.3:
设非突破点在匹配算法中发生，令X un
由Y
的所有被标记的顶点组成，则下列两个结论成立：
（1） S ＝X un ∪Y lab
是二分图G 的最小覆盖； （2） ∣M ∣＝∣S ∣，且M 是G 的最大匹配。
证明：
（1）反证法（首先证明S 是个覆盖）：假设存在一条边e=(x,y)，它的两个顶点都不属于S ，那么，un x X X ∈-,lab y Y Y ∈-。 当
e M ∈时，x 不会有*标记，因为un x X X ∈-，那么x 只能有（y ）标记，这与
lab y Y Y ∈-矛盾。
当
e M ∉时，x 会有*标记，并且y 会得到一个标记（x ）标记，这与lab y Y Y ∈-矛
盾。
(1) 欲证∣S ∣≦∣M ∣。
任取lab y Y ∈，由于没有出现突破点，y 必与M 中一条边相关联，设为{x,y}，且必制作糖果盒
有
un x X ∉，由算法（v ）步，x 必有标记（y ）。说明lab
Y 中任一顶点都有一条且是唯
一一条M 中的边与之关联，且对应的X 中的点也被标记。 任取
'un x X ∈，x ’未被标记，由算法第一步知，x ’必与
M 中一条边相关联，设为
（x ’,y ’），那么，
'lab y Y ∉，因为已证，lab Y 中任一顶点都有一条且是唯一一条M
中的边与之关联，且另一个X 中的点un x X ∉。因此，un X 中每一个顶点都与M 中唯
一一条边关联，并且，与
lab Y 中任一顶点不会共享M 中的边。即：
|S|＝|X un |∪|Y lab |≦∣M ∣.
又由引理：∣M ∣≦|S|，因此只能∣M ∣＝|S|，M 是最大匹配，S 是最小覆盖。
定理9.2.5
p ≥1阶正则的二分图G ＝（X ，△，Y ）总有完美匹配。
证明：设|Y|＝|X|＝n ，令S 是G 的任一覆盖，那么G 的任一条边至少与S 中的一个顶点关联。由于G
是p 阶正则的，那么S 的每一个顶点与p 条边关联，因此G 的总边数是p|S|，即pn ≦p|S|，即n ≦|S|。这说明最小覆盖至少包含n 个顶点（最多也只能包含n 个顶点），因此，总有完美匹配。
引理9.3.1 (SDR 存在的必要条件) 为使集合序列A=(A 1, A 2, …,A n )有SDR ，必须满足下列条件： （MC ：成婚条件）：对每一个k=1,2,…,n，以及从{1,2,…,n}选出的k 个互异指标i 1, i 2, …,i k , 都有：
∣A i 1 ∪A i 2∪…∪A i k ∣≥k.
证明：（反证法）
假设存在某个k ，及其对应的互异指标i 1, i 2, …,i k ，使得：∣A i 1 ∪A i 2∪…∪A i k ∣<k 。由鸽巢原理，必存在一个元素代表两个或两个以上的子集，与A 是SDR 矛盾。
对于成婚条件的解释：n 位男士，m 位女士，
n m ≥，每位男士满意的女士构成集合：A 1
,
A 2, …,A n ，女士不满意，则可以从集合删除自己，成婚条件就是每位男士都能成婚的条件，也是SDR 存在的必要条件，那么它是SDR 存在的充分条件吗？
SDR 问题的二分图表示：
构造二分图G ＝（X ，△，Y ），令Y ＝{ y 1, y 2, …,y m }，Y 的子集序列A ＝（A 1, A 2, …,A n ），取X 等于子集序列A 的下标集合，即X ＝{1,2,…,n}。边集合△＝{i
j
j
A y y i ∈|),(}，
那么，集合序列A 有SDR ，当且仅当，ρ（G ）＝n 。
定理9.3.2:
集合序列A=(A 1, A 2, …,A n )有SDR ，当且仅当成婚条件成立。 证明：（1）必要性（⇒）：已证。 （2）充分性（⇐
）
：
目标是证明上述构建的二分图G ，ρ（G ）＝n ，即c （G ）＝n 。 反证法：假设G 存在一个覆盖S ，且|S|<n ，令
2
1
S
S S =，其中：
X S S =1
，
,2
Y S S =那么，有n S S <+||||2
1
。
因为S 是覆盖，所以不存在连接1
S X -中的顶点与2
S
Y -中的顶点的边。
令
数据存储安全检测
||||1
1
S n S X k -=-=，并设},...,,{2
1
1
k
i i i S X =-，那么，
k
i i i A
A A ,...,,2
1
都是
2
S
的子集（因为
1
S X -中的顶点与2
S
Y -中的顶点的没有边
的连接）。
即：
k
S n S S A A A S
A A A k
i i i k
i i i =-<≤⊆|||||
||...| (1)
纱线蒸纱机
2
2
2
1
2
2
1
那么，
k A A A k
i i i <|...|2
1
，
与成婚条件矛盾。
因此，ρ（G ）＝n ，即c （G ）＝n 。 定
理
1
：
第
二
类
Stirling
数
)
,
(k n S 递推关系
)1)(1,(),(),1(n k k n S k n kS k n S ≤≤-+=+。
证明
),1(k n S +是集合},,,,{1
2
1
+=n n
这些k 分划可以分成两类：
第（1）类：
}{1
+n a 是A 的k 分划中的一块，这时，只需对集合}{1
+-n a A 进行k –
1分划，再加上}{1
+n a 这一块，就构成了A 的k 分划，因此，这类分划有)1,(-k n S 。
第（2）类：
}{1
+n a 不是A 的k 分划中单独的一块，此时，先构造}{1
+-n a A 的k 分划，共有),(k n S 种方法，然后，对于}{1
+-n a A 的每个k 分划，将1
+n a 加
氧化锡到该k 分划的k 个块中的某一块，从而构成A 的k 分划，因此，由乘法原则，集合A 的此类
k
分
划
共
有
),(k n kS 个。由加
法原则，
),()1,(),1(k n kS k n S k n S +-=+。
定理给出了构造所有k 分划的方法。（第二类Stirling 数三角形）
例（补充）3个红球，2个黄球，3个蓝球，每次从中取出4个排成一旬，求排列方案数。 解 {3.R,2.Y,3.B}的n 排列数为h n ，由定理 h n 的指数生成函数 !
88
560!77350!66
350!55170!4470!3328!229!1318地温空调
7217725672355121741235331422931!33!22!11!22!11!33!22!11)(x x x x x x x x x
x x x x x x x x x x x x x x x x e G ⋅
+⋅+⋅
+⋅+⋅+⋅+⋅+⋅+=++++++++=⎪⎪
⎭⎫ ⎝⎛+++⎪⎪⎭⎫ ⎝⎛++⎪⎪⎭⎫ ⎝⎛+++=
故知，从所给n 球取出4个的排列方案有70种。 推论6.3.2
D n 满足如下递推关系: (1) D n =(n-1)( D n-2 ＋ D n-1 )
(n=3,4,…)
(2) D n =nD n-1 + (-1)n (n=2,3,…) 证明：
（1）组合分析法 D 1=0，D 2=1，不妨设
3≥n ，考虑{1,2,…,n}的D n
个错位排列。
D n 个错位排列可以按照2，3，、、、，n 在第一个位置划分成（n-1）个部分，显然，每个部分的错位排列个数是一样多的，设为n
d
，那么，D n ＝（n-1）
n
d
。
以第一个位置为2为例，计算
n
d
：
第一个位置为2的错位排列形如：
n
i i i (23)
2，要求n i i i n
≠≠≠,...,3,23
2
分两种情况：
12
=i ，设形如n
i
i (213)
，
n i i i n
≠≠≠,...,4,34
3
的错位排列数为n
d '，n
d '＝
D n-2
12
≠i ，设形如n
i i i (23)
2，n i i i n
≠≠≠,...,3,13
2
的错位排列数为n
d ''，n
d ''＝
D n-1
D n ＝（n-1）
n
d
=（n-1）(
n
d '+n
d '')
(2)对公式（1）换一种写法
))1((2
1
1
------=-n n n n
D n D nD D
递归展开))2(()1(3
2
2
磨砂杯
1
-------=--n n n n D n D D n D
、、、
n
n n n n n n n n n n
D D D n D D n D D n D nD D )
1()
1()
2()1(...
)
)3(()1()
)
2(()1()
)1((2
1
2
2
4
3
3
3
2
2
2
1
1
-=-=--==---=---=---=----------
即：D n =nD n-1 + (-1)n
5.3 一些有用的恒等式 (1)
k
⎪⎭⎫ ⎝⎛k n =n ⎪⎭
⎫ ⎝⎛1-k 1-n
证明：（直接验证）
⎪⎭
⎫ ⎝⎛k n ＝ ⎪
⎭
⎫ ⎝⎛--=---=-11)!()!1()!1()!(!!k n k n k n k n k n k n k n
(2)
⎪⎭⎫ ⎝⎛0n +⎪⎭⎫ ⎝⎛1n +…+⎪⎭
⎫ ⎝⎛n n =2n
证明：二项式定理，令x=y=1。
(3)
⎪⎭⎫ ⎝⎛0n -⎪⎭⎫ ⎝⎛1n +⎪⎭⎫ ⎝⎛2n +…+(-1)k
⎪⎭⎫ ⎝⎛k n +…+(-1)n
⎪⎭
⎫ ⎝⎛n n =0 证明：上式，令x=1，y=－1。
⎪⎭⎫ ⎝⎛0n －⎪⎭⎫ ⎝⎛1n +…+（－1）n
⎪⎭
⎫ ⎝⎛n n =0
⎪⎭⎫ ⎝⎛0n +⎪⎭⎫ ⎝⎛2n +…+ ⎪⎭
⎫ ⎝⎛k n +…=2n-1
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议