崔添翼 § 翼若垂天之云

第9ç«  这一章讲二分图中的匹配。给出了几个能启发思路的转化成二分匹配的模型：有禁止的棋盘上放非攻击车；有禁止的棋盘上放1×2骨牌；m个具有一定资格的人申请n个工作。将问题转化为二分图匹配模型的关键点是构造二分图，使可行解与合法的匹配一一对应，这样最优解一般就对应了最大匹配。 定义二分图的交错路径是这样一种路径：含有奇数条边，其中仅有第1条、第3条、……、最后一条边都没有包含在当前的匹配方案里，仅有路径的两个端点没有被匹配。一个匹配是最大匹配当且仅当不存在交错路径。求最大匹配的方法就是不断寻找交错路径并将使用其中的奇数边重建当前匹配方案的，这就是Hungary算法。书中给出的伪代码垃圾了，本来不用那么麻烦的，更好的代码参见我以前关于Hungary算法的文章 二分图的最小覆盖的意思是这样的：选定一些点，让所有的边都有端点被选择，选的点数尽量少。König定理是这样的：二分图的最大匹配数等于最小覆盖数。这个定理可以帮助解决另一类可以转化为二分图匹配模型（先转化为最小覆盖模型）的问题。 一个和二分匹配有关的问题叫稳定婚姻系统。似乎在OI中用途不太大（主要是不太具扩展性），问题和算法（延迟认可算法）我不描述了。 （第10章暂略） 第11ç«  图就是由顶点和边构成的东西，（无向或有向的）边可以认为是顶点中的一种（可交换或不可交换的）关系。顶点的度就是邻接的边的数量，如果是有向图的话还可以定义入度和出度。 欧拉路就是一条经过了所有边仅一次的（不一定是简单）路径。存在欧拉路的充要条件是有0个或2个度为奇数的顶点，前者的欧拉路的起点与终点是闭合的。欧拉路可以用圈套圈算法来求。不过书中的方法实现起来还是麻烦（需要写链表），有更好的方法。中国邮递员问题，就是求一条从一个点出发经过每一条边再回到起点的最短路径。解决这问题的大概想法就是通过添边把所有奇度顶点变偶。问题的算法书上没写，不过我想大约就是：找出所有奇度顶点求它们两两的最短路，然后求（非二分图的……）最优匹配。如果是有向的反而简单的多，因为这样可以根据负点和正点构造出二分图匹配。 Hamilton路径的定义就是一条经过所有顶点仅一次的路径。这是NP-Complete问题，目前没有多项式算法。 判断图是否是二分图只需要试图给图2涂色，如果涂出矛盾了就不是。 树是一种图，它的定义包括：任两点都有且仅有一条路径的图；不含圈的图；n个顶点n-1条边的连通图。 Shannon开关游戏很有意思。正方必胜策略的有无取决于图是否存在两个不存在重复边的生成树，如果找出了这两个生成树，必胜策略的算法还是不太复杂的。不过这两个生成树怎么找呢？ 求最短距离树，其实就是求单源最短路径，所有的最短路径（可以）是一棵源点为根的树，用Dijkstra算法求。最小权生成数用Kruskal算法或Prim算法求。

第6ç«  加法原理的应用条件是分类后的集合是不相交的，但如果这个条件不满足呢？这就是容斥原理隆重登场的时候了。容斥原理是这样的A_1到A_n是对于需计数的集合分类后的集合，它们之间能有相交，总的元素个数就是|A_1∪A_2∪… ∪A_n| = ∑|A_i| – ∑|A_i∩A_j| + ∑|A_i∩A_j∩A_k| + …+ (-1)^m |A_1∩A_2∩…∩A_n|。它可以这样解释：首先加上所有集合的大小，然后减去每两个的集合并的大小，然后加上每三个集合的并的大小，然后减去每四个集合的并的大小，……，最后加或减所有集合的并的大小。它的证明可以通过计算某一元素对于等式每一项的贡献的方法来得到。 值得注意的是，如果和式中的每一项都需要直接计算的话，那么利用容斥原理的计算的复杂度关于n是指数级的。例如它用来计算一般的多重集的r-组合的个数就是如此。所以多重集的r-组合个数当元素的种数较多时似乎还是后面介绍的生成函数的方法更高效，它是伪多项式的。 错位排列（即元素i不在第i个位置上的排列）问题很有意思，它的特点是公式右边每一个和式里面的每一项是相同的，可以简化推导过程。最后的公式是：Dn = n! (1- 1/1! + 1/2! – … + (-1)^n 1/n!)。它有一个递推关系：D_n=(n-1)(D_(n-2) + D_(n-1)），可以组合推导。然后这个关系可以进一步简化为D_n = n D_(n-1) + (-1)^n，这个关系就不好组合推导了。 对于更一般的带有禁止位置的排列，就用一般的容斥原理就好了。 （墨比乌斯反演暂无） 第7ç«  算术序列就是等差数列，几何序列就是等比数列。顺便说一下，这里用a0（第0项）定义通项公式可比数学课本上用a1定义的公式优美多了。 求解递推关系是一门学问。比如说Fibonacci数的通项公式的样子很容易令第一次看到的人感到困惑。（八卦一下，我初中的时候曾经“证明”过 Fibonacci数不可能存在通项公式。呃……天才少年也有小的时候嘛……）现在的考试中似乎Fibonacci数的直接应用不多了。不过线性递推关系还是要看的。 一般的求解线性齐次递推关系的方法在此略过。 生成函数这个名字看上去有点神秘。但其实它就是将一个数列转化成一个函数的方法，定义函数的i次项的系数为a_i，就是数列a的生成函数了。将数列用这种方法表示出来可以方便处理和计算。比如说常数数列1,1,…的生成函数是1+x+x^2+……，但是利用无穷级数的求和，它同时可以表示成1/(1-x)这个很紧凑的形式，就方便接下来的处理了。 生成函数的首要用途是用来解元素的取法有限制的组合问题。比如说某元素只能取偶数个、某元素至多取b个最少取a个之类。对于每个元素的取法写成一个生成函数，就是如果能取i个x^i的系数就是1，否则为0。把所有元素的生成函数乘起来，得到的函数中x^i的系数就是取i个元素的方法数。 利用生成函数可以求解所有的常系数线性齐次递推关系。但目前还没有看到OI上的应用，所以在这里略过。 可以说，生成函数是一个模型，一个数学概念，就像“关系”“集合”这种数学上定义出来的东西一样。灵活的运用生成函数可以求解很多递推关系，比如Catalan数，还有后面讨论的很多数列。 指数生成函数是另一种生成函数。数列a的指数生成函数中x_i的系数是a_i / i!。常数列1,1,…的指数生成函数是Σx^i/i!=e^x。一般的，几何序列a_i=a^i的指数生成函数经化简是e^(ax)。它是用来解决和排列有关的问题的，典型的就是集合划分（更好理解的表达方式是涂色），例如某集合要被划分成若干个（有序的）集合，满足第一个集合的元素数是偶数，第二个集合不能少于a……这样就可以把每个集合的要求写成一个指数生成函数，然后分别化简以后乘起来就得到了通项公式。 可以看到，不管是常规生成函数还是指数生成函数，之所以用途很大就在于它可以被转化为很简单的形式方便运算（特别是乘法），还表达了原来数列的本质信息。