定理 设二部图G=<V1,V2,E>中, 如果存在t≥1, 使得V1Φ每个顶点至少关联 t 条边, 而V2中每个顶点至多关联t条边则G中存在V1到V2的完备匹配.

Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为 t 條件. 满足 t 条件的二部图一定满足相异性条件.

 ? X中的每个结点都有匹配。

其中N(S)为图G中所有与W相连的结点的集合

这个定理给出了判断一个二汾图中是否存在完备匹配的充要条件，即任意U部的子集的元素的个数要不大于其相连的V部的元素的个数

Hall定理还有个推论：

对于二分图（U+V, E）最大匹配数为

其中N(S)是S的邻点

解释：设最小匹配不了的点个数设为p，那么最大匹配的个数就是|U| - p p等于max (|S| ? N(S))，其中S是U部的任意子集 N(S) 是和S相连嘚V部的点的个数。

题意：有N个人1 ~ M号座位，第i个人想坐的座位是 [1,Li] 或 [Ri,M]问最少有多少人的意愿得不到满足。

二分图 G = {X+Y, E}X中的所有结点满足：若其编号为i，则只与Y中编号小于等于Li或编号大于等于Ri的结点连边给出 |X|, |Y| 和所有的Li, Ri，求G的最大匹配M（ 输出|X|?M，即最多有多少人能有座位坐 )

根據Hall定理的推论此题中，已知 |X|要求G的最大匹配|M|，只要求 max(|S|?|N(S)|)对于任意的人的子集S（），N(S) 必然可以表示成［1lb］U［ub，M］也即

所以这样可鉯简单的用O(n ^ 2)的算法解决，用线段树可以优化到O(nlogn).

//我还没写这题的代码

屈婉玲《离散数学》课件

自己研究一个东西然后写博客好累我还是先看书补基础吧。。