工程数学教材.pdf

《工程数学教材.pdf》由会员分享，可在线阅读，更多相关《工程数学教材.pdf（102页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、（注意：本文件的显示、打印需要公式编辑器的支持。）工 程 数 学山东大学软件学院2012年01月、乙 X 刖 S先修课程要求：高等数学、离散数学、数据结构课程内容与学时分配:1.运筹学共1 4学时线性规划6学时整数规划2学时动态规划4学时网络分析2学时2.组合数学共1 2学时排列组合2学时鸽巢原理及应用 2学时容 斥 原 理 及 其 应 用2学时母函数方法 2学时递推关系 2学时P o l y a计数定理 2学时参考文献：1 .刁在筠等，运筹学，高等教育出版社，2 0 0 12 .叶 惠 民，工程数学，东南大学出版社，2 0 0 33 .邹述超，概率论与数理统计，高等教育出版社，2 0 0 3

2、4 .R i ch ar d A.B r u al di,I n t r o du ct o r y Co m bi n at o r i cs,P r i n t i ceH al l,I n c.,1 9995 .卢开澄，组合数学，清华大学出版社，1 9996 .曹汝成，组合数学，华南理工大学出版社，2 0 0 07 .朱大铭，算法设计与分析，高教出版社。目 录第一篇 运筹学.1第一章 线性规划.1 1 线性规划问题及数学模型.12 图解法.7 3 单纯形法解L P问题.9 4 对偶线性规划.14第二章 整数规划.18 1 整数线性规划问题.18 2 整数线性规划问题解法.20第三章 动态

3、规划.221 最优化原理.22 2 用最优化原理解非线性规划问题.23 3 动态规划算法设计.26第四章 网络分析.331 图及网络.332 网络上的优化问题.34第二 篇 组 合 数 学.46第五章 排列组合.46 1 和、积的原则.46 2 排列.473 重复排列.49 4 组合.54 5 组合等式及意义.57 6 排列与组合的生成.57第六章 容斥原理与鸽巢原理.601 容斥原理.60 2 鸽巢原理.65 3 有重复元素的圆排列问题.70第七章 母函数与递推关系.75 1 用母函数解递推关系.75 2 用母函数解整数拆分问题.80 3 用指数型母函数解错排问题.83第八章 Polya计数

4、定理.861 Burnside 弓|理.862 Polya 定理.93V .刖 s本文只是部分运筹学与组合数学的摘要汇编，在缺少讲解的情况下，可能需要读者查阅其他教材或文献以了解详细内容。第一篇运筹学第一章线性规划 1 线性规划问题及数学模型生产及生活中有一大批问题的数学模型可以用相对简单的线性方程组表示出来。由下面的两个例子，理解这类问题的相似结构，进而总结线性规划问题的一般模型，给出常用解法。例 1设要从甲地调出物资2000吨，从乙地调出物资1100吨,分别供给A 地 1700吨、B 地供0 0 吨、C 地 200吨、D 地 100吨。已知不同地点间每吨运费如下表所示，运费与运量成正比，求

5、解运费最省的供给方案。运销产ABCD甲2125715乙51513715解:设甲、乙运往A、B、C、D 的物资量分别为孙，的2,砧,为4,必,X 22,尤23,尤24吨，则由题意，我们需要去求211+25尤1 2+7X13+15X4+51%21+5 1尤22+37123+15124的最小值。显然X|,XX13,X14,X21,X22,X23,X24不能任意取值，我们还有“甲地调出物资2000吨”、“供给A 地 1700吨”等条件限制。总结需求及条件限制，得到下面的完整数学模型：min/=21xn+25x12+7xl3+15x14+51X21+5 lx22+37X23+15X24S.t.+X2+苞

6、3 +X4=2000,x2l+x22+x23+x24=1 100,0,/=l,2J=l,2,3,4该模型的现实含意为：在X|+X|2+X|3+X|4=2000等条件下，求/=21X11+25X|2+7X13+15X14+51X21+51X22+37123+15X24的最小值。（这里先做出数学模型，以后再考虑求襁方法）例 2某工厂用3 种原料PI,P2,P3生产3 种产品Qi，Q2,Q30已知单位产品需要的原料数、单位产品的利润、原料总量等条件如下表所示，制定出总利润最大的生产计划。单 位 产 品 产料 kgA?i原 米QiQ2Q3原料可用量（kg/日）Pi2301500P2024800P332

7、52000单位产品利润（千元）354解：设三种产品的生产量分别为用,切,1 3时可以得到最大利润3闪+5检+4工3,则由题意，我们可以得到完整的模型为max z=3+5x2+4x3s.t.2 x+3X2 1500,2X2+4X3 800,3须 +2X2+5X3 0,7=1,2,3总结这两个例子，可以看到其共同点：都是在对未知量做出线性约束的前提下，求未知量线性组合的最值。我们将最大、最小值统一为最小值，假设线性约束有等式、有不等式，未知量有些必须非负、有些不受限制，可以得到下面的一般线性规划模型:线 性 规 划（LP）问题的一般形式min z-qX+c2x2 H-F cnxns.t.+ai2x

8、2+ainxn=b,i=I,-,p/+aj2x2 H-F ainxn 2如 i=p +匕任意,/=4 +1,-，、J（等式不都在前面怎么办？非负变量不都在前面怎么办？调一调。）L P模型中的术语：目标函数（指标函数、指标）：z=C1X+。2+q,x”价值系数：eg,价值向量：c =q,C 2,cj决策变量：xi,x2,-,xn,决策向量：x xx,x2,-,xn上述记法可以使指标写成：z=J x+ai 2x2+ai nxn=耳，i =1,，p约束：a,1%,+ai 2x2+ai nxn bt,i=p +1,XjX j 任意,/=4 +l,约束矩阵：a a2 an4/x a2 a22 a2nA

9、=(4.)*=:：Jm 0 m2 _ jnxn右端向量：b=bi,b2,-,bm 非负约束：Xj 0,j =1,2,(?自由变量：Xj,j q +.,n可行解、可行点：即满足约束的点，也就是满足约束的一组未知量的取值，该组值不一定能使得指标达到最小值。可行域D：可行解集合最优解：使得指标最小的可行解(不一定唯一，甚至不一定存在)。利用上面的一些记法，在某些条件下，可以得到LP模型的特殊形式，至少在形式上显得简炼一些，实际上今后的许多分析是基于这些简炼形式的。LP问题的规范形式,般形式中p=0,时，称为规范形式。m i n cTxs.t.A x hx 0一般形式与规范形式的转化将 ai Xxx+

10、aj2x2+ai nxn=b.化为a.xx a.2x ai nxnb.-ai xi-ai 2x2-ai nxn -b.令X j=总xj,x j 0 xj 0,j =(7 +1,.例：将下面的线性规划转化为规范形式m a x z=-X j +x2-2x3W.2 玉-x2=-2xl-2X2 0.自由解:m i ns.t.Z =-工2+2%32X 1 Xj+0 43 N 2-2xt+x2-0 x3 2-X 1 +2A 2 N-3,x2 0人自由m i nz =x 1 -x2 4-2x4-2X52XJ 工2+0 1 4-0氏5 N 一2-2xl+x2-0 x4+0 x5 2-X +2X2+0 x4-0

11、 x5 -3Xpx2,x4,x5 0c=1,-1,2,-27,x =X j,x2,x4,x57,2-100A=-2 1 0 0,b=-2,2,-37-1 2 0 0LP问题的标准形式一般形式中/?=m,q=时，称为标准形式。min cTx0一般形式与标准形式的转化对即+bt即 再 +ai2x2 +4力 相 一 x：=,x 0,i=p+L，根.令 /=x；-xj,4；之 0 x；2 0,/=q+1,.这里的其称为剩余变量。例：将下面的线性规划转化为标准形式max z=-x,+x2-2x3s1 2玉-x2=-2 再-2X2 0刍自由解:m i n z =X -9+2x32工 x9+2-%)+2x0

12、 2-3xpx2 0X 3自由m i ns.t.z=xi-x2+2X4-2X52XJ 4 +0工4+。二5 二 2-%+2X2+0 x4+O x5 -3m i n z=xi-x2+2x4-2xs+0 x6s.t.2x,-x2+0 x4+0 x5+0 x6=-2 X +2x,+0 x4+0%5 入6=-32-1000-12 0 0 -1-12-20 2图解法例1用图解法解线性规划m a x z=一 为 +x2s j-2xl-x2-2x-2X2 2xl+x2 0z在(1,4)点达到最大值3。例 2用图解法解线性规划min z=x-5x2 +2X2 4例3用图解法解线性规划min z-2x+x2W.

13、x,+x2 1%1 3%2 3%1,x2 0无最优解关于可行域。与最优解的讨论：0=0，无解、不可行；。工0，无界；Dr 0，有最优解。3 单纯形法解LP问题1.单纯形方法考虑标准形式的L P问题（Tmin z=c x0设A的前机列为线性无关。（注意各向量、矩阵的维数）将A分为左右两块，左边?列为可逆方阵B,右边记为N。（左面加列是不是一定可逆？）对应将价值向量C和决策向量x的前m行与后n-m行分开,A=B,N,c=,/二解,可,SN./v 丁T Tx=,x =xB,x,v_XN _ XR1,Ax=bB,N=b=BXB+NXN=b_*N _xB=B-b-B-NxNZ=CTx=crB,cTN X

14、R=CTBXB+CTNXN.XN _cB-b-B-N xN)+cxN9=以3 -0,0,0,c；3-W-4 4_XN _令r=0,0,0,c-W-或,则2=或8-八，且=一 斤方或犷卬-或，或o=cj6T 8,N-，c jB-A-c7原 LP问题变形为min z=cB b-x0若取乐=0,则4 =8-8 得一个满足等式约束的解_ B-bX=,0 _其对应的指标值为 2=crx=cBB-b oB 称为基，B 的列称为基向量，天=B 1 称为基本解，0R-1卜x=2 0 时称为基本可行解，此时B 称为可行基0B”0 时称x 为非退化的基本可行解。下面假设我们要讨论的LP问题对所有的可行基6,都有B

15、-b 0。定 理 若 标 准LP问题有可行解，则必有基本可行解；若有最优解，则一定存在一个基本可行解是最优解。（证明略）定 理 若0WO,则亍是最优解。证 V x 0,0,rx cB7B-h 0定理 若二的第左个分量媒 0,且&=夕儿 o,（下面说明止匕X是可行解，且其指标值要多小有多小。）A c）=A j+A ek=B,N+4 =。A x=A（x +08）=Ax +0A 8=A x=bx 0,z =4 5 _ C=C gB b-4T(X+68=c1sB-%-骋5=crBB-b-Ok0,且4=少儿中存在正分量，则武2 0,使得4攵=6且c，攵 0 但不能任意取。）1）可以适当取6 0 使得 为

16、可行解:由A 8=A-4o+A e*=B,N一夕40+Ak=0知道4 =4 叵+防）=4 亍+。4 6 =4 亍=匕；要使得 2 0,即B b0+6(+e*)2 0 ,只需B-b0+0一 4 0,B-b-0B AkO设田与=瓦由乐NO等知道取6 =1 1 1 皿|生|纵 0,，=1,2 -,加 即可。4 2)z=4B%_qT玄=c11tB-%/短+%=以8-纥茯=43-/尹，4 板=clB-b-0k bii=p+wi 0i=p+1,，加%0j=1,2,qA：w%j=1,2,(7与自由j=q+,-,nAw=Cjj=q+l,-,n可是约束矩阵A 的第i 行，为是约束矩阵A 的第，歹 U。min c

17、Txmax bTw规范形式，s/.Ar 2 b 的对偶问题为,s/.Arw0w 0min cTxmax bTw标准形式，sf.Ax=6 的对偶问题为.W.AT w 0w 自由2.对偶理论定 理 如果一个L P问题有最优解，则它的对偶问题也有最优解，且它们的最优解值相等。定理 对偶的对偶为原始的LP问题。3.对 偶LP的来历将一般形式min cTxsL a；x=bi bi%0.自由i=l,，Pi=+j=q+l,，几 八 不m in c x化为标准形式 0wTAcT,即:卬3,展开为夕c=q,r c .N g N q+l，%+l，c“，一c,0,o ,日X1,.,，X g，K+l，K+l，,X/,

18、Xj,x吁 p，A =4,，4 4+|,-4+-一 1-m P Jxg+2(-g)+Lpa11an aq i.,+l f+i -ain 0 0 aplaP2%ap.q+-/M+l ap.q+ap.n ap+1.1品+1.2 .Qp+l.qap+,q+l-ap+l.q+l aP+i,q+-ap+t,n T .am la,n2 a,nqam.q+t-am.q+am,q+l-am.n 0-1人 人 TqBA-CT 0,令wT=c J B-,则 J，M O改写为Awc4卬4%4+产 W c*-4+产 A：卬-Anw0,i=p+第二章整数规划 1 整数线性规划问题要求变量值取整数值的线性规划问题称为整数

19、线性规划，其中变量只取0 或 1 的线性规划称为0-1规划。投资决策问题 总金额B万元，个项目，第J项目所需资金的 利润c r应该选哪些项目使总利润最大。maxj=iJ 1s.t.bFj W Bj=i房产投资 地产面积3000 M2,甲类房产每幢250M2,可收利润10万元，可建设不超过8 幢，乙类房产每幢400M2,可收利润 20万元，可建设不超过4 幢，应该建设甲乙各几幢使得利润最大？max z=10 x+20ys.t.250 x+400y3000 x8y4x,y&N货朗问题从心出发，恰好经过力，也，V各一次回到V 0，从均到V/路程为四，（公 充 分 大），怎么走最近？min z=Z d

20、uxui.j=Os.t.超=1,i=0Z%，尸。ui-j+nXq n l,Xu=0?r 1,%为实数，j=0,i=0,，及1 zj ni,j=0,i=1,，背包问题个物品，体积分别为中，也，为，价值分别为 P1，2，P”，一个容积为V 的包，取哪些物品放入包内，使包内物品总价值最高。例：1)V=100,vl=pl=49,v2=p2=51,v3=p3=522)V=100,vl=pl=49,v2np2=51,v3=52,p3=52.1算法：穷举，共 2 种物品的组合。max z=Z PRi=l_ S.t.Z匕 外4Vi=l=0,1 2 整数线性规划问题解法1.图解法图解法求解下面的I L P问题m

21、 i n z =-5x2s.t,X +2X2 4420且为整数2.分枝定界法m i n z=-xx-x2s.t,4%1 +2%1 4%j +2X9 1 1_ 2x?-12。且为整数m i n z =-%)-x2s,t,-4%1 +2 x2 4 -14%j +2尤2 1 1一 2 X2 Xj 1斗2 2 0且为整数m i n z=-x-x2s/.4 玉 +2 x2 14$+2X2 2X1,%N O且为整数第三章动态规划动态规划是多阶段决策问题，相对地，线性规划、非线性规划问题称为静态规划问题。1 最优化原理全局最优，则局部最优。（如何理解）最短路问题g6货郎问题设/（匕 W）表示从火出发，经 过

22、 V中的所有点恰一次后回到丫 0 的最佳路线总长度，则所求的就是/（%,匕,为，,匕）4+（%，眩，3-，匕,），/（%,匕，岭，匕 J）=m i n 少2 +/（彩，匕，匕，匕 ），4.+/（匕，2 2,，*）./（匕，匕，匕,，匕）=m i n d2+f（v2,v3,v4,-,vn）,九+八匕乂彩，！,，匕 J），*94“+/（乙，鱼，匕，3 ）./(v,.,V)=m i n +/(vy,V -vy)例：%+/(4，%，%)，/(v0,v,v2,v3)=m i n 0+/(匕,%,%),.九+八匕，匕，修),九+/(%，%)，/(v1,v2,v3)=m i n ,dl3+f(v3,v2)2

23、 用最优化原理解非线性规划问题就下面的非线性规划问题，讨论最优化原理解题思想，并具体求解该题m ax F=4%j2-x；+2xj+1 2 s.t.3西 +2X2+x3 0/3(9)=m ax 2 x32+1 2 +/2(9-x3)f2(y)=m ax -力+工(，一2%)0 2x2 y/1(Z)=m ax 4 x 12解得：（2）=4 ,故9,、(2 4 (y-2 x,)2.)=黑 黑 一+4-J 2 16 4 2 1m ax -yx7+y o p 2 0 9 9 2 9fm ax 一7(z x8 丁 4 2 17 y)一H y 0 2 x20/,/)=0,i 0,j=0012 j0/1111

24、01/23/4201/41/2i02.划分问题用动态规划思想，设计填表法，求解下面的划分问题在集合A=ai，做，an)上定义正整数函数s,令8 =25()，问是否存在4 1,/(/-1,J-5(,)=TF,o th e r s3.背包问题背 包 问 题“个物品，体积分别为力，V 2,，为，价值分别为Pl，P 2，Pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高。m ax z=Z Pixi/=iJ s.t.Z v,xf V=ix,=O,l设 P i 9 H 9，对i位数组（x g,厮），构造有序对,其中i j=ZP JZ，匕=目 J=I由于（XB%2,备）有2,种不同的取值，所以

25、对应有2 i个不同的有序对，将这些有序对组成集合不），但有两种情况对应的有序对不放入s（i）：1）W V；2）两个有序对和,满足尸0/,Vi Vj,1.e 则不放入 S（i）o不)构造完成后,如下构造型+21)c S(i+1)；2)I wS 且 Vi+vi+iV c 5(i+,)04.排工问题“个工件，每个工件都要按顺序经过A、B两个机床进行加工，工件i 在 A、B两个机床上加工时间分别为即bi，确定n个工件的加工顺序，使得总加工时间最短。例：N 1N 2A42B13先加工N 1,所需总时间为4+2+3=9,先加工N 2,所需总时间为2+4+1=7。定理 最优加工方案当工件在A、B机床上加工顺

26、序相同时达到(证略)。状态(X,t)：X中是还没有经过A机床加工的工件，是B机床加工X外的工件还需要的时间，如果取i e X 为下一个放在A上加工的工件，则i 在A上完成加工时达到下一个状态(X-i,z,(f),其中*r q+b1,4.（，）=t ai=m a x，一 知0 +2=m a x，-4 +2也令A x,。为处于状态(X#时剩余的最优排工时间，则 怨，。是，的单调上升函数，且f(X,t)=m i n +/(X -z,z;(f)ieX,，由1A x，。是 1 的单调上升函数,要想只要即，m a x f-q-%+向+6,也+%一%也 m a x t-q.-%+.+bJ,bi+与只需要ma

27、x/?.+4 一%也 W max+么 一也mina/9Z?.m in 也即 可。算 法：1、2、3、4、例：12345A37457B62734加工顺序为13542.第四章网络分析 1 图及网络图，点集，点，边集，边，平行边，自环3)BS)定 义 1设 V 是一个非空集合，E是一个V 中元素的无序对构成的多重集，有序对G=匕 E）称为一个图，其中，V称为顶点集，其元素称为顶点或点，E 称为边集，其元素称为边。以上定义的图也称为无向图。相邻，关联，度，握手定理，通路，简单通路，初级通路回路，圈，连通，连通分支，单连通，强连通关联矩阵，邻接矩阵子图，生成子图，边割，割集树，2网络上的优化问题1.最短

28、路问题在实际问题当中，图的边往往与某种数量相联系，例如，在铁路交通图中，根据所讨论的问题，每条边上可以标上其代表的铁路的长度，或标上修建该铁路所需的费用等，一般地，引入如下定义.定义1设G是一个图，若对G中每条边e都规定一个非负实数w(e),则称G为赋权图(或权图)，卬(e)称为边e的权.G的边与非负实数的这种对应关系(用卬表示)称为权函数.例如，设G是铁路交通图，对G中每条边e规定卬(e)为e所代表的铁路的长度，则得到一权图，若规定w(e)为修建e所代表的铁路所需费用，则乂得到另一权图.再如，设G是秘密通讯图，对边e规定以e)为泄秘可能性则得到一权图，又若规定w，(e)为维护e所需费用，则又

29、得到另一权图.按照通常惯例，当，V不相邻时，规定v v(w v)=8.定义2 设G是一个权图，是G的子图，中各边的权之和称为子图的权，记为w(功，即eeE(H)由于权图中的权常常代表某种耗费，许多最优化问题都是要在一个权图中找出某类具有最小权的子图,其中之一就是最短路问题.定义3 设G是一个权图，路P的权以P)称为P的长度，两点，v之间最短路的长度称为小v之间的距离，记为d(，v),即0,u=vJ(w,v)=.,这样一直下去，直到瓦=0,即可求出“0到G中任意一点的最短路.为了说明上述过程，考察图3.1,“0到任一点的最短路用粗黑线表示（带圈的数字、表示该过程中边加入最短路的顺序）.在上述过程

30、中，若每一步都通过搜索来计算式的最小值，则必定会有大量的重复比较，为避免重复并保留从每一步到下一步的计算信息，采用如下的标号方法：在整个算法中，每个顶点V给以标号/（v）,它是d（0，V）的一个上界，开始时,/（劭）=0 ,/）=8工劭），在算法进行时，这些标号不断修改，当求出Si时，l（u）=d（u（）,），“G Sj,并且/（v）=m i n J（Hn,w）+w（v）v e 5,.g，Dijkstra 算法1.令 Z(wo)0,/(y)=8(p#0),S0=W o,z=0.2.对 每 个 用 min/(v),/(%)+卬(加)代替 Z(v),计算min/(v)l v e S j,并把达到这

31、个最小值的一个顶点记为%+1 令 S+i=SU M,+I).3.若 则停止，若 iV u -l,i-i+1,转入 2.当算法结束时，或劭，V)由标号/)的终值给出.如上所述，Dijkstra算法仅确定了从“0到所有其他顶点的距离，而并未给出实际最短路，然而，只要附加某些指令，不难获得这些最短路.以上算法的计算量为。(/),因此是一个有效算法.2.最小生成树问题定义1若图G的生成子图T是树，则称T为G的生成树.定理1 G是连通图当且仅当G有生成树.证明 充分性 若G有生成树T,则由于T是连通的，易知G必是连通的.必要性 设G是连通图，若G中无回路，则G本身就是一棵树，从而有生成树.若G中有回路，

32、从回路中去掉一边，得到的图G i仍然连通，若G i中无回路，则G是G的生成树，若Gi中有回路，从回路中删去一边，一直下去，最后必得到一个图0.，G人 是连通的且无回路，从而G*是G的生成树.显然，一个图G可能有多棵生成树，特别地，在赋权图当中，生成树的权一般也是不相同的，由于赋权图中的权往往代表着某种花费，寻找权最小的生成树，便有一定的实际意义.权图G中带权最小的生成树称为最小生成树或最优树，看下面例子.我们设想要建筑一个连接若干城市的铁路网，已知建造直接连接城市u与v的铁路费用为C“v，试设计一个铁路网，要求建造费用最小.将每个城市作为顶点，在顶点小v之间连接一条权为的边，则得到一个权图G,

33、显然，我们建造的铁路网应该是连通的,且必定没有回路，因而，我们面临的问题便是求G的最小生成树.下面介绍最小生成树的Kruskal算法，先来介绍一下其直观思想.设有赋权图G,既然我们要寻找G的最小生成树，我们所取边的权当然是越小越好，采用贪心策略，我们首先找到G的权最小的边，并取出来.然后，在剩下的边中再找出权最小且与已选出的边不构成回路的，再把它取出来，一直下去，直到选不出边.在上述过程中，我们得到的图是无回路的.进一步地，我们可证明我们最终得到的是一棵最小生成树.将以上直观思想叙述成算法，即是Kruskal算法.设G是简单连通权图，w是其权函数.(1)选取 G 的一边 e”使卬(ei)=mi

34、nw(e)lewE,令 E尸 e j,(2)若已选出笈=ei，e,),那 么 从E 中选取一边ei+i,使(I)E,U e,+1 的导出子图中不含回路；(I I)w+i)=m i n 卬(e)l e e E E j,E,U e 的导出子图无回路(3)若 g+i 存 在,令 E i+i=E N e +J,i+lf,转 ;若.+1不存在，则输出三储，,e,算法停止.可以证明，如上算法所得到的边集的导出子图T*(就称其为算法得到的子图)，即为G的最小生成树.定理2 K r u s k a l算法得到的图是G的最小生成树.证明 由算法可知，T*必包含了 G的所有顶点且是连通、无回路的，从而可知T*是生

35、成树.因而，若设G有个顶点，则T*中也必有个顶点，从而T*中必有-1条边，于是，T*是边集En-e i，e 2，en-)的导出子图，这里，ex,e-i，,e”-i依次是算法产生的边.下面用反证法证明7*是最小生成树.若不然，取所有最小生成树中与炉具有最多公共边者为T i，则边集E(T*)HE(T1),设是T*中第一条不在T中的边，即e,e2,，ek-&E(T),ek 由树的性质，Q+e*必有回路C.由于T*中无叵I路，C中的边必有不在T*中者，设 回 路 中 的 边 任既7*),显然7 2 =(八+e*)或也是一棵生成树，且卬(7 2)=卬()+卬(伞)一 卬(e因为e i，ek_,e k G

36、 E(T1),故这左条边不构成回路，由K r u s k a l算法中e*的取法知w(e 0 2 w(e*).所以,可为庆卬),因此一也是一棵最小生成树，且与T*的公共边多于八，与 T1的定义矛盾.这样就证明了 T*必为最小生成树.3.最大流问题设N=匕(/为一个加权的有向图，权值为亦负擎数，若存 在 x,YV,满足xny=0,x 中所有顶点的入度均为o,Y中所有顶点的出度均为0,则称有向图N 为网络，并将X 中的点称为源点，将丫中的点称为聚点(汇点)，N中其他顶点称为中间点，N 上的权函数c 也称为容量函数.一条弧。=3 _/的权值称为a 的容量,记为(:(而或“3,/)或。亿).我们主要讨

37、论|x|=|K=1的情况，即假设网络中恰有一个源点x 和一个聚点y,并总是将中间点集合记为1.设N=匕U为恰含有一个源点和一个聚点的网络，/为 N的弧集U 上的实数值函数，V,V2c V,用VM，匕表示起点在弘中，终点在中的弧的集合，记/(匕 M)=Z.。)，ae V1,V2当 V产时可以将/(%,%)简记为/G,%).定义1 设/为网络N=匕U的弧集U上的实数值函数，如果函数/满足(1)容量约束：0勺(i,/)W c(i,j),V i,jU,守恒条件：f(i,V)=f(V,i),V ie/,则称函数/为网络N 的一个容许流，简称为流；当N 的源点为x,聚 点 为 寸，称/(x,V)为流的值，

38、简记为人九由定义2可以证明 fx,y，i =V定义2设函数/为网络N=的一个流，aC U,如果/()=0,则称弧。是 零 的；如果/5)0,则称弧4是/-正的；如果/(a)1 V o l,W o c V,.证 明 设G含有匹配M,它 饱 和V.的每个顶点，并设V o c V.由 于 的顶点在M下 和NG(%)中相异顶点配对，故1此()1 2 M l.反之，I NG(%)|2|V o l,WocV.假设G不含饱和弘所有顶点的匹配.设M*是G的一个最大匹配，根据假设，M*不饱和M的所有顶点.设是的一个M*不饱和顶点，并设。表示通过用*交错路与连接的所有顶点的集合.由于M*是最大匹配,由定理1知M为

39、。中唯一M*不饱和点.设吊尸Q Q%,VO=QHV2,显然，匕)一“中的顶点在M*下与V o中的顶点配对，因此I=l V o l T，又NG(VO)=V6，所以，I NG(VO)|=|V o|-l|均，矛盾.定义6设G含有匹配M,如果G的每一个顶点都是M-饱和的，则称M是图G的一个完美匹配.定理3设G是一个b正则二分图，则G有完美匹配.证明 设%是 G 的一个二划分，则上|七|三|回=川|,M =v2|.设U V.,用 E|和E2分别表示与%和NG(VO)中顶点关联的边的集合，则 ic2,故k NG(Vo)=E2 E=kVo|,所以M(Vo)1切 Vol,由定理2 及=得证.|我们用0(G)表

40、示图G 含有奇数个顶点的连通分支的个数，则有定理4图G 有完美匹配的充要条件为0(G-V()X l V()I,VV()c V(G).证明略.第二篇组合数学第五章排列组合 1 和、积的原则在排列和组合中，有两个最基本的简单法则：i是和的法则,一是积的法则。和的法则：如果一个事件可能以P 种方式出现而另一个事件可能以q种方式出现，则这两个事件之一可能出现的方式数为p+q。换言之,如 果&和 S2是两个集合,且ism s2i=o,则从s=5,US2中选取一个代表的可能的方式数等于Si中选一个代表的方式数加上S2中选一个代表的方式数。例如一个班级有30名男生，20名女生，在这个班级选一名代表的方式数为

41、5 0,等于在男生中选一名代表的方式数(3 0)与在女生中选一名代表的方式数(2 0)之和。积的法则：如果一个事件可能以p 种方式出现，而另一个事件可能以q种方式出现，则这两个事件同时出现的可能方式数为pq。换言之，如果Si和 S2是两个集合，且ISil=p,叫=4,则第一个元素在S i内，第二个元素在S2内的有序对总数为pq。例如，一个班里有30名男生，20名女生，要选一名男生代表和名女生代表，有多少种可能的选取结果?因为选一名男生代表有30种可能的结果，选一名女生代表有20种可能的结果，因此，搭配起来共有30 x20=600种可能的结果。容易看出，上述和的法则与积的法则，可推广到用个集合的

42、情况。2 排列什么是排列？排列是集合中元素的一个有序选取。两个排列是不同的，当且仅当它们的元素不同或者它们的排列顺序不同。个元素集合S的一个r-排列，是从S中取出r个元素的有序排列。令P(，r)表 示S的所有厂 排列的总数。例如，将红、白、蓝三 个 球 放 进1 0只编了号的箱子里。如果每一只箱子最多装一个球，那么将这三个球放到10只箱子里共有多少不同的放法？如 果 将10只编了号的箱子，视 为10个不同元素的集合S,三个不同的球放进三只箱子里，视为从S中选取三个元素的一个排列，因此，不同放法的总数，等于S中所有3-排列总数尸(10,3)。因为将三个球放进1 0只箱子里，可以把球一个一个地放入

43、箱子里，将红球放入箱子里，有10种可能，放完红球后，只 有9只空箱子，因此白球有9种可能的方法。白球放好后，只 有8只空箱子，放蓝球只有8种可能的放法。所以根据积的法则，三个不同的球放入10只编了号的箱子，共 有10 x9x8=720种不同的放法。一般的情况是，个中的六排列总数，等于从个元素中选取/个元素，放进厂个编了号的空位置上不同放法的总数。往空位子上放元素可以一个空位子一个空位子的放。第一个空位子的元素有 种可能的选取方式，第二个空位子上元素有(-1)种可能的选取方式，第r个空位子上元素有(-叶1)种选取方式。因此，根据积的法则，P(n,r)n(-1)(n-2).(n-r+1 )o注意，

44、上述讨论的排列，是将厂个元素按一定顺序排成一行，若两个排列元素相同，但其顺序不同，也是不同的排列，例如(a,b,c,d)和(b,c,d,a)是两个不同的4-排列。现在，考虑r-循环排列。一个循环排列，是将r个元素按一定顺序排成个圆圈。两个六循环排列是不同的，当且仅当一个厂循环排列，不能经过旋转来得到另一个循环排列。例如(。,b,c,d)和(6,c,d,a)是两个相同的4-循环排列。但(a,b,c,d)和(d,c,b,a)是两个不同的4-循环排列。对给定个元素集合S,其中有多少个r-循环排列？注意到，一个r-循环排列,对应着r个厂-排列。例如，排 列C a,b,c,d),(b,c,d,a),(c

45、,d,a,b)和 C d,a,b,c)是对应于同一个4-循环排列(a,b,c,d),因此，个元素的集合S,有工尸(小rr)个r-循环排列。在有些情况下，如四个不同的珠子，做成一个手镯。此时,(a,b,c,d)和(d,c,b,a)完全是同一个手镯。因为，手镯不仅可以旋转，还可以翻转。因此，(d,c,b,a)翻转以后就成 了(a,b,c,J)o两个r-翻转循环排列是不同的，当且仅当这两个翻转循环排列的元素不同，或者一个排列不能经过翻转和旋转而得到另一个。给定一个个元素集合S,那 么5有多少个 翻转循环排列呢？易见，它恰有二-P(，r)2r个不同的六翻转循环排列。3 重复排列前面讨论的是一个集合的

46、排列数。现在讨论一个多重集厂个(不必不同)元素的排列总数的问题。可分两种情况讨论之。一.重数无限的多重集让我们讨论，以5为首的四位数的电话号码有多少个。因为第一位数固定为5,而第二僚数有1 0种可能的选取方式，第三位也 有1 0种可能的选取方式，第四位数可能的选取方式也有1 0种。因此，根据积的法则，以5为首的四位数字电话号码共有IO?个。1 一个多重集，定义为一些对象的总体，但这些对象不必不同，如5=a,a,a,h,b,c 就是一个多重集。在多重集里，一个元素的重数，定义为它在该集合中出现的次数，如在S=(a,a,a,h,h,c)中，。的重数为3,的重数为2。象这样允许数字重复出现的排列，称

47、为重复排列。一般地，设s是个不同元素组成的多重集，其中每个元素的重数都是无限大。S的一个 重复排列定义为S中r个（不必不同）元素按-定顺序排成一行。两 个r-重 复 排 列（见，。2,4）和（仇,历，,儿）是不同的，当且仅当存在某个i,使勾声5的一个 重复排列，可以理解为有r个编了号的空位子，从S中取出r个（不必不同）元素，将它们放在r个空位子上。由于元素可以重复出现，所以每个空位子上可以放个不同元素中的任何一个，即是说，每个空位子上的元素有种可能的选取方式。因此，根据积的法则，不同的 重复排列数为一个等价的提法是：有个不同的箱子（相当于个不同的元素）和厂个不同颜色的球（相当于厂个空位子）。如

48、果每一个箱子都可以放无限个球（即每一个元素有重数是无限大），那么将厂个球放入箱子里，共有多少不同的放法（等价于取出厂个（不必不同）元素放在/个空位子上的方式数）？因为每个球可以放到n个箱子中的任何一个，而一个球放入一个箱子，可以视为从n个箱子中选出一个箱子，二个球放入同一个箱子，可以视为这个箱子被选了两次。放 个球的一种放法就对应于（个箱子的）一 个 重 复 排 列。所以，按积的法则，不同放法的总数为二.重数有限的多重集设S是个不同元素组成的多重集，第i个元素重数为加令Z=匕，则S的不同的h重复排列数为/=1k!kxk2-kn对于S中的h重复排列，如果交换该排列中两个相同元素的位置，则该排列不

49、变。而交换两个不同元素的位置，则可得一个新的h重复排列。如果将S视为左个元素的集合，其 h排列总数为P（k,k）=k 10同理，若 S i 视为自个元素的集合,则习的 排列排列总数为舟!，S,视为岛个元素的集合，则 S的匕-排列排列总数为履，S”视为鼠个元素的集合，则 5“的公-排列排列总数为K!，琨S中一个h重复排列与的心!心!个h排列相对应。所以S中h重复排列总数为k%也!尤了例 1.3.1 设 S是种不同颜色的球之多重集，第 i 种颜色的球有左个，i=l，2,n o 则共有球数为 那么将攵1=1个球放到r个（其中r k）编了号的箱子里，使得每一个箱子最多装一个球，试问共有多少种不同的放法

50、？首先注意，这里的两种放法是不同的，当且仅当存在一个i,使得或者在第i 个箱子里的球的颜色不同，或者球的数量不等（一个是一个，一个是零个）。我们构造一个多重集5 =S。/,其中/是第+1 种颜色的集合，且有kn+i=r-ko则S是+1个不同颜色球的多重集。S中的球数为k+r-k=f k j=r。于是5的六重复排列与S的h重复/=1排列是一一对应的。而5的r-重复排列总数为r!_ r!_ P（r,k）尤!,*+!匕!心!“!（”，）!匕叼左 !，这就是所要求的个球不同的放法。例1.3.2有一个6x8的棋盘，如下图示。如果要求只能向正东和正北方向（沿水平和垂直的格子线）行走，那么从A到B有多少条不