Skip to content

Tag Archives: 组合数学

《组合数学》缩写（六）

Tuesday, May 15, 2007

第12章 有向图就是边是顶点的有序对的图，也就是说每个边都有起始顶点和终止顶点。任意两顶点间有且仅有一条边的有向图叫竞赛图。若任两顶点间都可以沿有向路径互达，图就是强连通的。 无向图的强连通定向就是把每条边指定一个方向，然后保证得到的有向图是强连通的。强连通定向存在当且仅当原图中没有桥。构造出这一强连通定向事实上很简单：按照一遍DFS的访问方向给边定向就可以了（书中的算法一如既往地麻烦）。 核心分配问题是这样的：n个商人，每人有1个商品，每人对所有n个商品按照自己的喜好进行排序。求一个把n个商品分配给n个人的方案，使不存在几个商人的集合，他们把分到的商品再次进行交换后可以使每个人都更满意。算法是：每个商人对自己最喜欢的商品的主人连一个有向边，找一个圈（由于每个点都有出边，所以这肯定是能找到的），按照这个圈进行分配，把已分配的顶点删掉，所有指向这些顶点的边重新计算。 网络就是存在源点s和汇点t的有向图，其中每条边都有一个可以认为是“容量”的权值。网络中的流定义为加在每条边上的一个函数，也就是说给每条边指定一个“流量”。合法的流应该满足：每条边的流量不超过其容量，除源点和汇点外，点的出边的容量和与其入边的流量和相等。流的净流量就是源的出边的流量和或汇的入边的流量和。求一个合法的净流量最大的流就是最大流问题。 网络的割是一组边的集合，满足把这些边从原图中删去后从源点到汇点不再连通。最小割就是边的权值（就是上述“容量”）和最小的割。最大流最小割定理的内容就是：网络中的最大流的值等于最小割的值。 求解最大流问题和最小割问题可以采用残量网络增广路的方法。这在很多很多资料中都有很好的介绍。《组合数学》这书似乎并不是学网络流的好教材。 第13章 χ(G)是图G的色数，就是说给图的每个顶点赋一个颜色使所有边的两个端点的颜色不同，需要的最少颜色数目。它也可以理解成将顶点划分成若干个集合，使每个集合的导出子图都是零图的最少集合数目。求图的色数很困难。 关于图G的色多项式pG(k)，也就是说将图G用k种颜色的方法数。有一个结论：设T是一棵n阶树，则pT(k)=k(k-1)^(n-1)。它的证明也简单：第一个顶点有k种着色方式，以后每添加一个与当前顶点相邻的顶点都k-1种着色方式（因为它仅与一个顶点相邻），根据乘法原理得证。另外，n个顶点的零图的色多项式是k^n。求色多项式的一种方法是：当G不为零图时，设x、y是一对邻接顶点，设G1为原图去掉边x、y的图，G2为原图将x、y合并成一个顶点的图（原来与x或y相邻的顶点均与新顶点相邻），那么就有pG(k) = pG1(k) – pG2(k)，递归求解即可。这个算法的正确性还比较好理解的，不过显然它是指数级的算法。它可以采用非递归的方法实现，就是维护一个图的集合，每次取出一个非零图的元素把它分成两个元素。 平面图就是可以“画”在平面上而且边不交叉的图。（更“数学”的定义似乎书上没有。）它有一些很好的性质：设一个连通的平面图的平面表示有n个顶点点、e条边曲线、r个所围区域，则：n+r-e=2。证明的方法是先对树证明，再往树上加边，保持等式始终成立。一个平面图必存在一个顶点，它的度至多是5，这是欧拉公式的推论。 五色定理是：一个平面图的色数至多是5。这个可以比较简单地证明，主要根据上面的欧拉公式的推论来利用那个特殊的顶点做突破口。它的加强版本四色定理也是成立的。 图的独立集的定义是一个顶点的集合，它的导出子图是零图。图的独立数α(G)就是图中最大的独立集的大小。求图的独立数很难。图的控制集是一个顶点的集合，它满足所有不在集合中的顶点都与集合中的点有边。最小的控制集的大小称为图的独立数dom(G)。图的团就是一个顶点的集合，它的导出子图是完全图。图中的一个团是图的补图的独立集，反之亦然。图的团数ω (G)是最大的团的大小。将图的点集划分成最少的团的数目称为团划分数θ(G)。完美图满足它的任何一个导出子图有χ(G)=ω (G)且α(G)=θ(G)。 图的弦就是连接圈的两个顶点且不属于该圈的一条边。如果每一个长度大于3的圈都有弦，图就被称为弦图。所有的弦图都是完美的。所有的区间图（定义不说了）都是弦图。 以上定理的证明均略，因为第一我也搞不太懂，第二它们在OI中似乎没什么用。 图的顶点连通度κ(G)是最少删去多少个顶点可以使图不再连通，定义κ(K_n)=n-1。边连通度λ(G)是最少删去多少条边可以使图不再连通。再设δ(G)表示图中顶点的最大度，则有显然的不等式κ(G)≤λ(G)≤δ(G)。 顶点连通度κ(G)不小于k的图称为k-连通图，一个图是2-连通图与以下结论等价：没有关节点；任两个顶点a、b都存在一个包含a、b的圈；每三个顶点a、b、c，都存在一条连通a、b且不经过c的路径。这些都很好证明。 关于图的点连通度的Menger定理的内容是这样的：设k是一个正整数，G是一个阶为n≥k+1的图，则G是k-连通的当且仅当对任意两个不同的顶点a和b都存在连接a、b的k条路径使得每对路径只有a和b两个公共点。

Filed in 程序园, 生活志 | Also tagged | Comments (0)

《组合数学》缩写（五）

Sunday, May 13, 2007

第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算法求。

Filed in 程序园 | Also tagged | Comments (0)

《组合数学》缩写（四）

Saturday, May 12, 2007

第8章 本章介绍了很多著名的数列，我认为这是本书最激动人心的一章。 Catalan数：C_n = C(2n,n) / (n+1)；C_n = ΣC_i*C_(n-i)，其中0≤i<n；C_n=C_(n-1)*(4n-2)/(n+1)。它的意义有很多，例如：n+1边形用对角线划分成三角形的方法数；n个+1和n个-1满足所有部分和不小于零的排列数；具有n个节点的二叉树的数量…… 对于数列h_i，定义它的（一阶）差分序列Δh_i=h_(n+1)-h_n。它的p阶差分序列就是p-1阶差分序列的差分序列。如果某个序列是n的p次多项式，它的p+1次差分就全是0，p次差分是常数列。利用这个原理可以在给出前n+1项的前提下求解这种序列。差分运算满足对加法的分配率。 序列差分表由它的第0行确定，也就是原序列，但同时也可以由第0条对角线上的元素确定。换句话说，由差分表的第0条对角线就可以确定原序列。有这样两个公式：原序列为h_i，第0条对角线为c_o,c_1,…,c_p,0,0,0,…则h_n = c_0*C(n,0)+c_1*C(n,1)+…+C(n,p)，Σh_k(k=0..n) = c_0*C(n+1,1)+c_2*(n+1,2)+…+c_p*C(n+1,p+1)。记住这两个公式，差分表（的第0条对角线）就变得非常有用了。 第二类Stirling数：S(p,k) = k*S(p-1,k) + S(p-1,k-1)；S(p,0)=0（p≥1），S(p,p)=1。它的意义是将p个元素的集合划分成k个不可辨别的非空集合的方法数。上面的递推式可以用组合证明：一方面，如果将元素1单独拿出来划分成1个集合，那么方法数是S(p-1,k-1)；另一方面，如果元素1所在的集合不止一个元素，那么可以先将剩下的p-1个元素划分好了以后再选一个集合把1放进去，方法数是k*S(p-1,k)；有加法原理得证。第二类Stirling数有公式：S(p,k) = (Σ(-1)^t * C(k,t) * (k-t)^p) / k!，不过看上去好像意义不大，记住一开始的递推式就好了。 Bell数B_p表示将p个元素的集合划分成一些不可辨别的非空集合的方法数，由第二类Stirling数的定义，显然有：B_p = S(p,0) + S(p,1) + …… + S(p,p)。还有一个递推式：B_p = ΣC(p-1,i)B_i（0<=i<p），可以组合证明。 第一类Stirling数s(p,k)满足的递推关系是：s(p,k) =（p-1)*s(p-1,k) + s(p-1,k-1)；初始条件与S(p,k)一样是s(p,0)=0（p≥1），s(p,p)=1。它表示n个物体排成k个非空的循环排列（就是圆圈）的方法数。 第一类和第二类Stirling数事实上的意义比上面讲到的要丰富，它们是P(n,p)与n^p这两组多项式向量空间的基互相表示的系数。哦……这个不理解没关系的。 将整数n写成一个无序的正整数的和式的方法数就是分拆数p_n。p_n相当于方程n*x_n + … + 2*x_2 + 1*x_1 = n的整数解的个数。书中没有给出递推的或者直接计算的式子，只给出了一个生成函数，实际计算的时候加一维用DP求解就好了。 用n个一般位置上的(k-1)维超平面分割k-维空间所成的区域数是h(n,k)=C(n,0)+C(n,1)+…+C(n,k)。一般的推导较繁。 格路径，就是在平面直角坐标系的整点中从一个点到一个点的最短路径。从(0,0)到(p,q)的格路径数是(p+q,p)，因为一共要走p+q步，选择其中p步向上走。下对角线格路径就是从源点到目标点的对角线的上方（不包括线上的点）不可到达时的格路径数。从(0,0)到(n,n)的格路径数就是Catalan数C_n，根据那个+1、-1部分和很容易证明。一般地，从(0,0)到(p,q)的下对角线格路径条数是R(p,q)=C(p+q,q)*(p-q+1)/(p+1)。如果允许对角步进，计算会有点麻烦，给一个公式好了：从(0,0)到(p,q)经过r个对角步进的格路径数K(p,q:rD)=C(p+q-r,(p-r,q-r,r))（这是多项式系数）；如果下对角线，更加麻烦，R(p,q)=K(p,q)*(q-p+1)/(q-r+1)。 […]

Filed in 程序园 | Also tagged | Comments (3)

《组合数学》缩写（三）

Friday, May 11, 2007

第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……这样就可以把每个集合的要求写成一个指数生成函数，然后分别化简以后乘起来就得到了通项公式。 可以看到，不管是常规生成函数还是指数生成函数，之所以用途很大就在于它可以被转化为很简单的形式方便运算（特别是乘法），还表达了原来数列的本质信息。

Filed in 程序园 | Also tagged | Comments (1)

《组合数学》缩写（二）

Wednesday, May 9, 2007

第4章 本章讲了生成各种排列与组合的算法，最后提了一下偏序和等价关系的相关概念。 书中生成n个元素的所有全排列的算法并不好，原因是不按照字典序生成。其实我们需要的只是生成字典序意义下的“下一个”全排列的算法。设原序列为s[0..n-1]，算法是这样的：找到最大的i使s[i]<s[i+1]（若i不存在则不存在下一个全排列）；再找到最大的j使i<j、s[i]<s[j]，交换s[i]与s[j]；将s[i+1..n-1]的元素逆序。 排列的逆序列就是排列中每个元素逆序数构成的数列，一个元素的逆序数就是在排列中先于它且大于它的元素的个数。当排列中元素的取值一定时，根据逆序列可以构造出原来的排列。 生成集合所有子集（等价于0和1的n元组）的方法是类似于二进制进位的，也就是从01序列的一边开始不断把1改成0直到遇到一个0并把它改成1。还有一种方法是按照n阶反射Gray码的顺序生成这些n元组，不过似乎没什么用。 按照字典序生成前n个正整数的r-组合的算法看上去还是挺有用的，当然只需要研究如何生成“下一个”r-组合即可。舌原序列为s[0..r-1]，算法是：确定最大的k，使得s[k]+1<=n且s[k]+1未在s[0..k-1]中出现；将s[k..n-1]顺次设为s[k]+1、s[k]+1、…、s[k]+r-k+1。 （按照字典序生成r-排列的方法是什么呢？有待研究……） 定义一些关系R的性质：自反（对于所有x，满足xRx）、反自反（对于所有x，不满足xRx）、对称（对于所有x、y，若xRy，则yRx）、反对称（ 对于所有不相同的x、y，若xRy，则yRx不成立；或者说xRy且yRx仅当x=y）、传递（对于所有x、y、z，若xRy且yRz，则xRz）。 满足自反、反对称、传递的关系是偏序；将上面的自反改成反自反就成了严格偏序。对于偏序R，若任意x、y都有xRy或yRx，则R是全序。元素见存在偏序/全序关系的集合以及该关系称为偏序集/全序集。 有序偏序集的线性扩展（即所有元素的一个排列s[0..n-1]，若s[i]≤s[j]，则i<=j）跟拓扑排序是一样的。 满足自反、对称、传递的关系是等价关系。利用元素间的等价关系可以将集合划分成若干等价类；或者说，集合上的等价关系与集合的划分是对应的。 第5章 组合数C(n,k)出现在二项式定理中，所以它们也叫二项式系数。二项式系数有好多重要的性质。 Pascal公式：C(n,k) = C(n-1,k) + C(n-1,k-1)。当需要系统地求出一定范围内所有C(n,k)的值时，这是比较好的递推方法。证明方法是：从n个元素中选k个元素，可以选择元素1，这时只需从剩下n-1个元素中选择k-1个，方法数是C(n-1,k-1)，也可以不选元素1，这时的方法数是C(n-1,k)，根据加法原理可得结论。Pascal三角形是一个很有意思的图形，它的另一种解释是：从顶部开始，只能向下或下右走，到达点(n,k)的路径条数。 二项式定理：(x+y)n = C(n,0) xny0 + C(n,1) xn-1y1 + … + C(n,k)xn-kyk + … + C(n,n)x0yn。它的证明可以通过归纳法（代数方法）也可以通过二项展开式的组合意义得出。 二项式系数还存在另外一些恒等式：k C(n,k) = n C(n-1,k-1)；C(n,0) + C(n,2) + … = C(n,1) + C(n,3) + …；ΣkC(n,k) = n*2n-1（1<=k<=n）；Σ C(n,k)^2 =C(2n,n)（0<=k<=n）；ΣC(r+i,i) = C(r+k+1,k)（0<=i<=k）；ΣC(i,k) […]

Filed in 程序园 | Also tagged | Comments (2)