下载文档原格式
2012National English Contestfor College Students(Level B-Preliminary)参考答案及评分标准Part I.Listening Comprehension（30points）1—5CABBA6—10ABCBA11—15CBABC16—20BBACC21.a few(some)small22.earn23.salary24.budget25.a house 26.essentials27.credit card28.the interest29.10%(ten percent)30.every yearPart II.Multiple Choice(15points)Section A(10points)31—35BCCAA36—40ACBDBSection B(5points)41—45CBADAPart III.Cloze(10points)46.fossil47.contribute48.farmers49.oceans50.systematically 51.recycle52.decomposes53.genetically54.public55.inhabitedPart IV.Reading Comprehension(40points)Section A(10points)56.D57.B58.refined sugars,artificial colors and chemicals59.a moderate exercise lasting less than30minutes60.an intravenous fluidSection B(10points)61.It can be considered rude to tip.62.Up to20%of the bill.63.About$3to$5per room per day.64.Because workers are expected to increase their wager with tips.65.It lists the generous and bad/(not so generous)celebrity tippers.Section C(10points)66.universes67.unapproachable68.enticed69.well-intentioned70.interests and needsSection D(10points)71.T72.T73.F1--74.这些矿物盐分在皮肤上形成的保护层可以杀死细菌，以阻止体味的自然产生。
2012年第四届全国大学生数学竞赛初赛（非数学类）试卷及参考答案一、简答下列各题(本题共5个小题，每题6分，共30分) 1．求极限()12lim!.n n n →∞【参考答案】：因为2211ln !!,n n n n e而211ln1ln 2ln ln !,12n n n n n且ln lim 0.n n n 所以1ln1ln 2ln lim 0.12n n n n即 21lim ln !0n n n 21lim ! 1.n n n 2．求通过直线2320,:55430x y z L x y z ⎧⎪+-+=⎪⎪⎨⎪+-+=⎪⎪⎩的两个相互垂直的平面12,ππ，使其中一个平面过点()4,3,1.-【参考答案】：过直线L 的平面束方程为 23255430x y z x y z ，即 (25)534230.x y z 若平面1 过点 4,3,1 ，代入得0 ，即 ，从而1 的方程为3410.x y z 若平面束中的平面2 与1 垂直，则 3(25)451340. 解得3, 从而平面2 的方程为2530.x y z 3．已知函数(,),ax byz u x y e+=且20ux y∂=∂∂，确定常数,a b ，使函数(,)z z x y =满足方程20.z z zz x y x y∂∂∂--+=∂∂∂∂ 【参考答案】：(,),ax by z u e au x y x x (,),ax by zu e bu x y y y2(,),ax by z u ue b a abu x y x y x y21(1)(1)(,),ax by z z z u uz e b a ab a b u x y x y x y x y若是上式等于0，只有 1(1)(1)(,)0u ub a ab a b u x y x y，由此可得 1.a b 4．设()u u x =连续可微，(2)1u =，且()()32d d Lx y u x x uu y +++⎰在右半平面上与路径无关，求().u x 【参考答案】：由32u x u x y u yx，得34x u u u ，即214dx x u du u， 这是一个一阶线性微分方程，于是由公式有通解为ln 2ln 2442uux e u edu C uudu C u uC 由(2)1u 得0C ，所以1/3.2x u5．求极限lim d .x x x t +【参考答案】：因为当1x 时，x x xxdt0x所以lim0.x xx第二题：(10分)计算20|sin |d .xe x x +∞-⎰【参考答案】：由于220(1)1|sin ||sin |nn k xxk k ex dx ex dx12(1)11sin nk k x k k e xdx应用分部积分法，有1222(1)11sin 15k k x k k e xdx e e所以有 222011|sin |15n n x k k e x dx e e212221151n e e e e 当(1)n x n 时，(1)2220|sin ||sin ||sin |n x n x x x e x dx e x dx e x dx当n ，由两边夹法则，得2222011|sin |lim |sin |.51xxxx e ex dx ex dx e【注】如果最后不用夹逼准则，而用2222011|sin |lim |sin |.51n xxn e ex dx ex dx e需要先说明20|sin |x e x dx收敛。
2012年全国高中数学联合竞赛（B 卷）一试一、填空题：本大题共8个小题，每小题8分，共64分。
2012B1、对于集合{}b x a x ≤≤，我们把a b -称为它的长度。
设集合{}1981+≤≤=a x a x A ，{}b x b x B ≤≤-=1014，且B A ,都是集合{}20120≤≤=x x U 的子集，则集合B A 的长度的最小值是◆答案：983★解析：因为B A ,都是集合{}20120≤≤=x x U 的子集，所以310≤≤a ，20121014≤≤b ，{}19811014|+≤≤-=a x b x B A ，或{}b x a x B A ≤≤=| ，故当2012,0==b a 或者1014,31==b a 时，集合B A 的长度最小，最小为9833110149981981=-=-2012B 2、已知0,0>>y x ，且满足⎪⎩⎪⎨⎧=-=+=+120)sin()sin(1)sin(2)(cos 222y x y x y x ππππ，则有序实数对=),(y x ◆答案：()2,4★解析：由1)sin(2)(cos 2=+y x ππ及0)sin()sin(=+y x ππ得()()[]0sin 2sin =+x x ππ，得()0sin =x π，代入0)sin()sin(=+y x ππ得()0sin =y π可得y x ,都是整数。
由()()1222=-+=-y x y x y x ，y x y x +<-，得⎩⎨⎧=+=-62y x y x ，解得⎩⎨⎧==24y x ，故有序实数对),(y x 即为()2,4。
2012B3、如图，设椭圆12222=+b y a x （0>>b a ）的左右焦点分别为21,F F ，过点2F 的直线交椭圆于),(11y x A ，),(22y x B 两点。
若B AF 1∆内切圆的面积为π，且421=-y y ，则椭圆的离心率为◆答案：1★解析：由性质可知B AF 1∆的周长为a 4，内切圆半径为1，则2122114211y y c a S B AF -⨯⨯=⨯⨯=∆，可得c a 2=，即21==a c e 2012B 4、若关于x 的不等式组⎩⎨⎧≤-->--+012033223ax x x x x ，（0>a ）的整数解有且只有一个，则a 的取值范围为◆答案：⎪⎭⎫⎢⎣⎡34,43★解析：由03323>--+x x x 解得13-<<-x 或1>x ，所以不等式组的唯一整数解只可能为2-或2。
2012年全国初中数学联合竞赛试题参考答案第一试一、选择题：（本题满分42分，每小题7分） 1．已知1a =，b =2c =，那么,,a b c 的大小关系是 （ C ）A. a b c <<B. a c b <<C. b a c <<D.b c a <<解答：1a ===b ==，2c ===1显然：b a c <<2．方程222334x xy y ++=的整数解(,)x y 的组数为 （ B ） A ．3. B ．4. C ．5. D ．6. 解答：222222223232()234x xy y x xy y y x y y ++=+++=++=由0、1、2、3、4、5、6的平分别是0、1、4、9、16、25、36知唯有16+2⨯9=34故5555544444x y x y x y x y x y y y y y y +=-+=+=+=-⎧⎧⎧⎧+=±=±⎨⎨⎨⎨===-=-⎩⎩⎩⎩、，由、、、得 4444=9=1=9=1y y y y x x x x ===-=-⎧⎧⎧⎧⎨⎨⎨⎨--⎩⎩⎩⎩、、、共4组解。
3．已知正方形ABCD 的边长为1，E 为BC 边的延长线上一点，CE ＝1，连接AE ，与CD 交于点F ，连接BF 并延长与线段DE 交于点G ，则BG 的长为 （ D ）A．3 B．3 C．3 D．3EBD解答：如图，做G H ⊥BE 于H ，易证Rt △AB E ∽Rt △GHB ，设GH=a ，则HE=a ，BH=2-a ， 由GH BH a 2-a 2==a=AB BE 123得解得，故BG=3。
4．已知实数,a b 满足221a b +=，则44a ab b ++的最小值为 （ B ）A ．18-. B ．0. C ．1. D ．98. 解答：44222222219=2=21=2()48a ab b a b a b ab a b ab ab +++-+-++--+2（） 考查以ab 整体为自变量的函数的图像为抛物线219y=2()48ab --+其对称轴为14ab = 由22222020a b ab a b ab +-≥++≥和知1122ab -≤≤ 又1111()4242-->-，故当12ab =-时，函数取最小值0。
2012 National English Contest for College Students(Level D-Preliminary)参考答案及评分标准Part I Listening Comprehension（30marks）Section A(5marks)1—5BCACCSection B(10marks)6—10CACBC 11—15CBAABSection C(5marks)16—20BCACCSection D (10marks)21. employment opportunities 22. adapt to 23. considerably 24. personality 25. suspicious of 26. measure theeffects 27. belief sand values 28. distort29. madepositivechoices 30. cultureshockPart IIV ocabularyandStructure(15marks)31—35ACCDB 36—40BDBBA 41—45BCCADPart Cloze(10marks)46. countless 47. improve 48. suffering 49. resignation 50. innovative51. contributing 52. dedication 53. existing 54. that 55. toPart IV Reading Comprehension(40marks)Section A (10marks)56.B 57.C 58. State championships 59. participate 60. pioneering spiritSection B(10marks)61. Without aleader, there is nobody to keep the goal sclear.62. They should be sensitive, sociable andbeabletoget on with awiderangeof people.63.T 64.F 65.FSectionC(10marks)66. Theabilitytounderstandother people.67. They worry that the theory suggests that one gender is better thanthe other anda theory like this maycreategender stereotypes.68. Astudycarriedout inCambridgeUniversityshowsthat newborngirlslooklonger at aface, andnewbornboyslooklonger at amechanical mobile, whichsuggeststhat certaindifferencesbetweenmaleandfemalebrainsarebiological.69.女性更有可能选择与时尚、浪漫故事、美容、咨询服务和养育子女相关的杂志；而男性则更可能选择以2 - -计算机、汽车、摄影、体育和户外活动为特色的杂志。
时代杯”2012年江苏省中学数学应用与创新邀请赛试题参考解答(初中组)(2012 年 12 月 19 日下午 15 : 30 ~ 17 : 00)、选择题（下列各题的四个选项中，只有一个是正确的•每题 7分，共42分）7.若将9个数按照从小到大的顺序排成一列， 中间的数恰是这9个数的平均数，前5个数的平均数是40,后5个数的平均数是 60,则这9个数的和为 ___________ 450 ____ .的值为 C .1 3D .20 3( A )4 A . 31 B . 22.在平面直角坐标系xOy 中，平行四边形 OABC 的顶点为O （0, 0)、 A(1 , 1)、 B(3, 0),则顶点C 的坐标是( D )A . (£, 1)B . (4, 1)C . (-2, 1)D..(2, -1)1•从-3, - 2, - 1，45中任取2个数相乘，所得积中的最大值为a，最小值为b，则I在厶ABC 中，AD 为BC 边上的中线.已知AC = 5, AD = 4,贝U AB 的取值范围是 （) 3.B 4. 5. A . 1v AB v 9B . 3v AB v 13如图，扇形OAB 是圆锥的侧面展开图，点边长为1cm ,则这个圆锥的底面半径为 A . 2 2 cm c 2 C . T cmB . .2 cm1D . — cm22 2设整数x , y 满足不等式x + y w 2x + 2y , C . 5v AB v 13D . 9v AB v 13O 、A 、B 分别是格点.已知小正方形方格的O则x +y 的不同值的个数为6.在如图所示的4 4方格中，每一横行、纵行和对角线上都应是1, 2, 3, 4四个数，则a 与b 的乘积的值为A . 5 C . 312a b31、填空题（每题 7分，共28分）（第4题）2& 设b 为实数，点P （m , n ） （m > 0）在函数y = — x bx 2的图象上，点 P 关于原点的对 称点Q也在此函数的图象上，则m 的值为 ____ 迄 ____.9. 口袋中装有5个小球，其中1个红球，2个黄球，2个白球，它们的大小、形状完全一样•从袋中摸出一个球后放回，再摸第二个球，则两次摸到的两个球为同色球的概率是9 25.10. 德国数学家洛萨•科拉茨在 1937年提出了一个猜想：如果n 是奇数，我们计算 3n + 1;如果n 是偶数，我们除以2•不断重复这样的运算， 经过有限步骤后一定可以得到 1•例 女口，n = 6时，经过上述运算，依次得到一列数 6, 3, 10, 5, 16, 8, 4, 2, 1 .小梁同 学对某个正整数 n ,按照上述运算，得到一列数，已知第 6个数为1,则正整数n 的所 有可能取值为 4, 5, 32 ____________ .三、解答题（第11题、第12题每题18分，第13题22分，第14题22分，共80分） 11. （本题满分18分）在凸四边形 ABCD 中，/ BAD = 90°对角线AC 与BD 互相垂直且相等， 其交点为E , E 为AC 的中点，求证：BE = DE .证明：（证法一）因为 AC 丄BD ，所以/ AED = Z BEA = 90°因此/ BAE + Z ABE = 90°. 又因为/ BAD = 90 ° 所以/ BAE + Z DAE = 90 °从而/ ABE = Z DAE .因此 DE • BE = （DE ；BE ）2,得 BE = DE . （证法二）因为 E 为AC 的中点，AC 丄BD ,所以BD 是线段AC 的垂直平分线，从而 AD = CD , AB = CB . 又 BD = BD ，所以△ ABD CBD .于是△ ABEDAE ，得 DE又因为E 为AC 的中点，所以 AE = EC . 又 AC = BD ，所以 AE = BD DE + BE212分18分C6分AEAE ，即 AE 2= DE •BE .又因为/ BAD = 90 ° 所以/ BCD = 90 °中信息，求:(1) 圆柱形容器的高与底面积; (2) “柱锥体”中锥体的高与底面积.解：(1 )由图②知，圆柱形容器的高为 12 cm .从第26秒到第42秒，共注入水(42 — 26) X 5( cm 3),则圆柱形容器的底面积为 (42 — 26) X 5- (12 — 8) = 20(cm 2). (2)由图②知，“柱锥体”中，下部小圆柱的高为5cm ,上部小圆锥的高为 8— 5= 3(cm).从开始到第15秒，共注入水15X 5 ( cm 3),则圆柱形容器的底面积—“柱锥体”中锥体的底面积=15 X 5 — 5 = 15(cm 2).2所以“柱锥体”中锥体的底面积为 20— 15 = 5(cm ).所以/ BAD + Z BCD = 180 ° 所以A 、B 、C 、D 四点共圆. 12分由/ BAD = 90。
2012年下学期七年级数学竞赛试题及答案时量：120分钟 满分：120分一、选择题（每小题3分，共30分） 1. a b c -+的相反数是（ C ）A.a b c -+B.b a c -+C.a b c -+-D.a b c +-2. 已知数轴上三点A 、B 、C 分别表示有理数a 、1、1-，那么1a +表示（ B ）A.A 与B 两点的距离B.A 与C 两点的距离C.A 与B 两点到原点的距离之和D.A 与C 两点到原点的距离之和3. 在()23-，22-，2-，()31-，2--，()211n n --（为正整数）这六个数中，负数有（ A ） A.4个 B.3个 C.2个 D.1个 4. 小刚做了一道数学题：“已知两个多项式为A ，B ，B=32x y -，求A+B 的值．”他误将“A B +”看成了“A B -”，结果求出的答案是x y -，那么原来的A B +的值应该是（ D ）A ．43x y +B ．2x y -C ．2x y -+D ．75x y -5. 如图是用棋子摆成的“H ”字，按这样的规律摆下去，摆成第10个“H ”字需要（ C ）个棋子.A.50B.51C.52D.53 6. 一辆汽车从A 地匀速驶往B 地，如果汽车行驶的速度增加%a ，则所用的时间减少%b ，则a ，b 的关系是（ D ） A.1001%a b a =+ B.1001%b a =+ C.1a b a=+ D.100100a b a=+7. 方程12233445x xx x ++++⨯⨯⨯⨯ (201220122013)x+=⨯的解是（ A ）A.2013x =B.2012x =C.2011x =D.1x =8. 9点12分时，时钟的分针和时针的夹角（小于180°的角）为（ C ）A.150°B.154°C.156°D.162°9. A 站与B 站之间还有3个车站，那么往返于A 站与B 站之间的车辆，应安排多少种车票？（ B ）A.4B.20C.10D.910. 希望中学开展以“我最喜欢的职业”为主题的调查活动，通过对学生的随机抽样调查得到一组数据，如图是根据这组数据绘制的不完整的统计图，则下列说法中，不正确的是（ C ）A ．被调查的学生有200人B ．被调查的学生中喜欢教师职业的有40人C ．被调查的学生中喜欢其他职业的占40%D ．扇形图中，公务员部分所对应的圆心角为72° 二、选择题（每小题4分，共32分）11. 有理数a ，b ，c 在数轴上的位置如图所示，则化简a a b b c b c --+-++＝b 12. 国务院总理温家宝在政府工作报告中指出，我国2011年国内生产总值47.2万亿元．47.2万亿元用科学记数法表示为为：134.7210⨯ 元． 13. 已知235x y -=，用含有x 的代数式表示y ，得253x y -= ；用含有y 的代数式表示x ，得352y x +=. 14. 已知235x x +-的值为7，则2293x x --的值为34- .15. 如果规定运算a ※b =2ab a b +++，那么x ※3=1中的x =1- ． 16. 若关于x 的方程243x m -=和2x m +=有相同的解，则m 的值是8- . 17. 27.24︒=27 度14 分24 秒，108°21′36″=108.36 度．18. 如图是七年级（1）班学生参加课外兴趣小组人数的扇形统计图．如果参加外语兴趣小组的人数是12人，那么参加绘画兴趣小组的人数是 5 人．5三、解答题（共58分） 19. （6分）计算：()()420051481221349-÷⨯--+-+-解：原式=4481161399-⨯⨯--+=161613---+ =30-20. （8分）如果单项式2amx y 与235a nxy --是关于x 、y 的单项式，且它们是同类项. （1）求()2013413a -的值；（2）若23250a a mx y nx y -+=，且0xy ≠，求()201325m n +的值.21. （8分）为庆祝建党91周年，某中学开展了“红诗咏诵”活动，九年一班为推选学生参加此项活动，在班级内举行一次选拔赛，成绩分为A 、B 、C 、D 四个等级，并将收集的数据绘制了两幅不完整的统计图．请你根据图中所给出的信息，解答下列各题：（1）求九年一班共有多少人； （2）补全折线统计图；（3）在扇形统计图中等极为“D”的部分所占圆心角的度数为___________ （4）若等级A 为优秀，求该班的优秀率．22. （8分）一队学生从学校步行前往国家历史博物馆参观，速度为5km/h ，走了1小时后，一名学生回学校取东西，他以7.5km/h 的速度回到学校，取了东西后立即以同样的速度追赶队伍，结果在离博物馆2.5千米处追上队伍，求学校到博物馆的距离．23. （8分）有这样一道题：“当2x =-，23y =时，求221312323m x x y x y ⎛⎫⎛⎫--+-+ ⎪ ⎪⎝⎭⎝⎭的值”．在做此题时，小刚把2x =-看成了2x =，但结果也正确，已知计算过程无误，求m 的值．24. （10分）小马在解方程21132x x a -+=-．去分母时，方程右边的1-忘记乘6，因而求得的解为2x =，试求a 的值，并正确解这个方程．25.（10分）如图，已知∠AOC与∠AOB互为补角，OM、ON分别是∠AOC、∠AOB的平分线，且∠MON=35°，求∠COB的补角和∠AON的余角．。
韶关学院第十二届数学建模竞赛题参考解答
一、 成品检验
解: 设每个车间原有成品x 个，每天每个车间能生产y 个成品；则一个车间生产两天的所有成品为 (x + 2y ) 个，一个车间生产6天的所有成品为 (x + 6y ) 个，由于A 组的9个检验员每天的检验速度相等，所以A 组检验员每天检验的成品数量是相同的, 可得
4
)
6(32)2(2y x y x +=+ 解得：x =10y , 从而, 每一个检验员每天检验的成品数量为：
3
492)2(2y
y x =⨯+
又因为B 组所检验的是6个车间，这6个车间生产6天的所有成品为6(x + 6y )个，而这
6(x + 6y )个成品要B 组的人检验6天，所以B 组的人每天检验成品的数量为 (x + 6y ) 个.
因为所有检验员的检验速度都相等，所以 (x + 6y ) 个成品所需的检验员人数为：
1243
163/46=⨯=+y
y y y x （人）.
答：B 组有12个检验员.
二、 投圈游戏
解: 按规则, 圆圈的圆心须落在如图中的阴影部分方能获奖, 则按几何概型可知, 此时获奖概率为
%450)20250()2(2
222=⨯-=-=a r a p
另外, 要想使获奖的概率不超过1%, 即
%150
)250()2(2
2
22≤-=-=r a r a p 可解得 2r ≥ 45CM, 即当圆圈的直径大于等45CM 时(当然要小于50CM)可使获奖率不超
过1%.
三、科学施肥
解: 设每周需用有机肥料x kg,化学肥料y kg,每周总的肥料费用为z 元,那么可得如下线
性规划模型
⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≥≥++=0
20000010
14000..3.09.0min y x x y y x t s y x z 用图解法求解, 作出可行域如下图所示
:
作一组平行直线 0.9x +0.3y = t , 其中经过可行域内的点且和原点最近的直线,经过直线x
+ y =14000和直线y = x /10的交点A(140000/11, 14000/11), 即x = 140000/11, y = 14000/11时,肥料费用最低. 所以, 有机肥料和化学肥料应按10:1的比例混合时成本最低.
四、陶罐药量
解：设x 表示任一时刻t 在陶罐内药物总量。
那么，d x /d t 表示在陶罐内药物总量的变化率.药物进入陶罐速率为：
50(ml/s) × 0.1(g/ mL) ＝ 5(g/s)
某时刻陶罐内存药物为 x (t ) (单位：g )，浓度是 x / 500(g / mL)，药物离开陶罐的速率为：
50(ml/s) ×
500x (g/ mL) ＝ 10
x
(g/s) 又由于总量的变化率等于药物进入速率与离开速率之差，故可得如下微分方程模型:
⎪⎩⎪⎨⎧=⨯
-⨯=0
)0(500501.050d d x x t
x
这就是我们建立的微分方程模型。
求解此模型，由
10
5d d x
t x -= 解得
10
50)(t
Ce
t x -
-=，
将x (0)=0代入，得C =50.
因此，陶罐药物总量关于时间t 的函数10
50)(t Ce
t x -
-=, 1分钟后陶罐内药物总量为：x (60)
= 50 – 50e -6 ≈ 49.88g.
五、 船身长度
解: (1) 不能顺利通过; (2) 船身长为 AB + BC , 易知有
θ
θθcos sin )(b
a BC AB l +=
+= (3)显然 l ( θ ) 是 (0, π/2) 上的连续函数, 其最小值即为船能通过的最大长度. 为此, 先求其导数得
θθθθθcot csc tan sec )(a b l -='
令 l '( θ ) = 0, 可得唯一驻点 θ0 满足
b
a =
03tan θ 代入l ( θ ) 可得船身最大长度为
θθθθ22min tan 1cot 1sec csc +++=+=b a b a l
3/23/2)(1)(1b
a
b a b a +++=
2
/33/23
/23/23/23/23/23/23/2)
(b
a
b a b b a a +=+++=
将数据代入可得船身最大长度为125米.
六、电力供应
解:
问题(1)求解:
解法一（最大流算法）: 这是单源网络最大流问题. 记 f ij 为结点 i 到 结点 j 的弧流量, c ji 为弧容量, c ji 为相应的逆向弧容量. 第一次迭代：令所有 f ij = 0, c ji = 0；
选取从结点0到结点8→ ① → ⑤ → ⑧, 该路径的容量 c =min{20, 10, 15}= 10; 计算各边的流量及容量如下:
f 01 = f 15 = f 58 = 0 + 10 = 10;
c 01 = 20 – 10 = 10, c 15 = 10 – 10 = 0, c 58 = 15 – 10 = 5; 逆向弧容量 c 85 = c 51 = c 10 = 0 + 10 = 10.
将结果画在如下图中, 图中连线上数字表示当前弧容量, 带下划线数字为逆向弧容量.
第二次迭代：
选取路径→③→⑦→⑧, 容量为c =min{40, 25, 35}= 25; 计算各边的流量及容量如下:
f03 = f37 = f78 = 0 + 25 = 25;
c03 = 40 – 25 = 15, c37 = 0, c78 = 35 – 25 = 10;
逆向弧容量c87 = c73 = c30 = 0 + 25 = 25.
将结果画在如下图中:
由于从结点0到结点8只有上述两条路径, 且从上图可看出两条路径都已无正容量, 所以结点0到结点8的最大流为10 + 25 = 35.
解法二: (列举法)可将从结点0到结点8的所有路径一一列出如下:
路径1: ①→⑤→⑧; 路径12 →③→⑦→⑧
路径上所能通过的最大流量为该路径上各边的最小容量. 容易看出这两条路径的最小容量分别为10与25,且没有重边, 故到结点8的最大流为35.
问题(2)求解: 最大流算法(也可用图上作业法).
第一次迭代：令所有f ij = 0, c ji = 0；
选取从结点0到结点6→①→⑤→⑥, 该路径的容量c = 10; 计算各边的流量及容量如下:
f01 = f15 = f56 = 10;
c01 = 20 – 10 = 10, c15 = 10 – 10 = 0, c56 = 10 – 10 = 0;
c65 = c51 = c10 = 0 + 10 = 10.
将结果画在如下图中.
第二次迭代：
选取路径①→④→⑥, 容量为c =min{c01, 15, 25}= 10; 计算各边的流量及容量如下:
f01 = f01 + 10 = 20, f14 = 0 + 10 = 10, f46 = 0 + 10 = 10;
c01 = c01– 10 = 0, c14 = 15 – 10 = 5, c46 = 25 – 10 = 15;
c10 = c10 + 10 = 20,c41 = 0 + 10 = 10, c64 = 0 + 10 = 10.
将结果画在如下图中:
第三次迭代：
选取路径②→④→⑥, 容量为c =min{25, 25, c46}= 15; 计算各边的流量及容量如下:
f02 = f24 = 15, f46 = f46 + 15 = 25;
c02 = 25 – 15 = 10, c24 = 25 – 15 = 10, c46 = c46– 15 = 0;
c20 =0+ 15 = 15,c42 = 0 + 15 = 15, c64 = c64 + 15 = 25.
将结果画在如下图中:
第四次迭代:
选取路径→③→⑥, 容量为c =min{40, 30}= 30; 计算各边的流量及容量如下: f03 = f36 = 0 + 30 = 30;
c03 = 40 – 30 = 10, c36 = 30 – 30 = 0;
c30 =0+ 30 = 30,c63 = 0 + 30 = 30.
将结果画在如下图中:
第五次迭代:
选取路径→③→⑦→⑥, 容量为c=min{c03, 25, 20}= 10; 计算各边的流量及容量如下:
f03 = f03 + 10 = 40, f37 = 0 + 10 = 10, f76 = 0 + 10 = 10;
c03 = c03– 10 = 0, c37 = 25 – 10 = 15, c76 = 20 – 10 = 10;
c30 = c30 + 10 = 40,c73 = 0 + 10 = 10, c67 = 0 + 10 = 10.
将结果画在如下图中:
从上图可看出已再找不出从结点0到结点6正容量的路径了, 所以结点0到结点6的最大流为f36 + f46 + f56 + f76 = 30+25+10+10 = 75.。
