Hall

Irwin-Hall 分布 对于 \(n\) 个均匀分布于 \([0,1]\) 的连续随机变量 \(X_1,X_2,\dots,X_n\)，其和的随机变量 \(X\) 满足： \[P(X\le x)=\sum _{k=0}^{\lfloor x\rfloor}(-1)^k\binom nk\frac ......

Hall 定理： Hall定理： 设一个二分图，V1<=V2。 则V1能完美匹配的条件是，对于所有点集S属于V1，V1能到达V2的点集S2，满足S2>=S1 ex_Hall定理： 设一个二分图，V1<=V2 则，这个图的最大匹配ans=min(|V1-S1|+|S2|)=|V1|-max(|S1|- ......

引言 网络上有许多Hall定理的证明，但是对于Hall定理的几个推广的介绍却少之又少，因此本文来简单介绍一下 注：为了使这篇文章看起来简单易懂，本文将不会使用图论语言，会图论的朋友们可以自行翻译为图论语言。 背景： 在遥远的地方有一个神奇国家，这个国家有n个男生和m个女生（n m）。每个男生都喜欢着 ......

整理一下一些有关图论的结论。 以下一般图 $G=(V,E)$，二分图左部点集为 $L$，右部点集为 $R$。 ### 一般图中，最小点覆盖+最大独立集=$|V|$ 考虑到最小点覆盖，最大独立集都可以写成整数规划的形式。 最大独立集：$|V|$ 个 $01$ 变量 $x_i$，$\forall_{(u ......

定理：Irwin-Hall 分布 对于 $n$ 个在 $[0,1]$ 内均匀分布的实数随机变量，它们的和不超过一个实数 $z$ 的概率为： $$ F(z)=\sum\limits_{k=0}^{\lfloor z\rfloor} (-1)^k\binom{n}{k}\frac{(z-k)^n}{n! ......