1、第八章习题解答第八章习题解答 8.1 证明在证明在9座工厂之间，不可能每座工厂只与其座工厂之间，不可能每座工厂只与其他他3座工厂有业务联系，也不可能只有座工厂有业务联系，也不可能只有4座工厂与偶数座工厂与偶数个工厂有业务联系。个工厂有业务联系。解：将有联系的工厂做一条连线。解：将有联系的工厂做一条连线。如果仅有如果仅有9座工厂只与其他座工厂只与其他3座工厂有业务联系，座工厂有业务联系，说明顶点次数之和为说明顶点次数之和为27，矛盾。，矛盾。如果只有如果只有4座工厂与偶数个工厂有业务联系，其他座工厂与偶数个工厂有业务联系，其他5个工厂一定与奇数个工厂有业务联系，说明顶点次个工厂一定与奇数个工厂有
2、业务联系，说明顶点次数之和还是奇数，矛盾。数之和还是奇数，矛盾。第八章习题解答第八章习题解答 8.2 有八种化学药品有八种化学药品A、B、C、D、E、F、G、H要要放进贮藏室。从安全角度考虑，下列各组药品不能贮放进贮藏室。从安全角度考虑，下列各组药品不能贮存在同一室内：存在同一室内：AC，AF，AH，BD，BF，BH，CD，CG，DE，DG，EG，EF，FG，GH，问至少需要几间贮藏室存放这些药品。，问至少需要几间贮藏室存放这些药品。解：能贮存在同一室内的两种药品之间作一条连解：能贮存在同一室内的两种药品之间作一条连线。贮存在同一室内的药品应该构成一个完全图。线。贮存在同一室内的药品应该构成一
3、个完全图。ABG，CFH，DE构成完全图。故，存放这些药品最少需构成完全图。故，存放这些药品最少需要要3间储藏室。间储藏室。第八章习题解答第八章习题解答 8.3 6个人围成圆圈就座，每个人恰好只与相邻者个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每不相识，是否可以重新就座，使每 个人都与邻座认识个人都与邻座认识?解：两个人认识作一条连线。解：两个人认识作一条连线。第八章习题解答第八章习题解答 8.4 判定图判定图8-50中的两个图能否一笔画出，若能，中的两个图能否一笔画出，若能，则用图形表示其画法。则用图形表示其画法。解：解：(a)图都是偶点，可以一笔画出。图都是偶点，可
4、以一笔画出。(b)图只有两图只有两个奇点，一个奇点为起点，另一个奇点为终点。个奇点，一个奇点为起点，另一个奇点为终点。第八章习题解答第八章习题解答 8.5 求解如图求解如图8-51所示的中国邮路问题，所示的中国邮路问题，A点是邮点是邮局。局。第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.6 分别用深探法、广探法、破圈法找出图分别用深探法、广探法、破圈法找出图8-52所所示图的一个生成树。示图的一个生成树。第八章习题解答第八章习题解答第八章习题解答第八章习题解答第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.7 设计如图设计如图5-53所示的锅炉房到各座楼铺设暖气所
5、示的锅炉房到各座楼铺设暖气管道的路线，使管道总长度最管道的路线，使管道总长度最(单位：单位：m)。第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.8 分别用避圈法和破圈法求图分别用避圈法和破圈法求图8-54所示各图的最所示各图的最小树。小树。第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.9 给定权数给定权数1，4，9，16，25，36，49，64，81，构造构造棵霍夫曼树。棵霍夫曼树。第八章习题解答第八章习题解答 8.10 如图如图8-55，v0是一仓库，是一仓库，v9是商店，求一条是商店，求一条从从v0到到v9的最短路。的最短路。第八章习题解答第八章习题解答第八
6、章习题解答第八章习题解答 8.11 求图求图8-56中中v1到各点的最短路。到各点的最短路。第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.12 求图求图8-57网络中各顶点间的最短路。网络中各顶点间的最短路。第八章习题解答第八章习题解答091201820014020121650)0(D0912018200321436020121650)1(D0948123201820032143602012191650)2(D0948123201820032143602012191650)3(D第八章习题解答第八章习题解答0948123201820032143602012191650)4(D0
7、948123201820020503214360201219165054321)5(54321VVVVVDVVVVV第八章习题解答第八章习题解答 8.13 某设备今后五年的价格预测分别是某设备今后五年的价格预测分别是(5，5，6，7，8)，若该设备连续使用，其第，若该设备连续使用，其第j年的维修费分别为年的维修费分别为(1，2，3，5，6)，某单位今年购进一台，问如何确定更新，某单位今年购进一台，问如何确定更新方案可使方案可使5年里总支出最小年里总支出最小(不管设备使用了多少年，不管设备使用了多少年，其残值为其残值为0)。解：最优解为：先使用两年，更新后再使用三年。解：最优解为：先使用两年，更
8、新后再使用三年。或先使用三年，更新后再使用两年。最小总支出或先使用三年，更新后再使用两年。最小总支出20。第八章习题解答第八章习题解答 8.14 求图求图8-58中网络最大流，边上数为中网络最大流，边上数为(cij，fij)。解：最大流量为解：最大流量为14。第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.15 如图如图8-59，发点，发点S1，S2分别可供应分别可供应10和和15个个单位，收点单位，收点t1，t2可以接收可以接收10和和25个单位，求最大流，个单位，求最大流，边上数为边上数为cij。第八章习题解答第八章习题解答 解：最大流量为解：最大流量为21。第八章习题解答第
9、八章习题解答 8.16 如图如图8-608-60，从，从v v0 0派车到派车到v v8 8，中间可经过，中间可经过v v1 1，v v7 7各站，若各站间道路旁的数字表示单位时间各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达使单位时间到达v v8 8的车辆最多的车辆最多?第八章习题解答第八章习题解答 解：最大流量为解：最大流量为40辆。辆。第八章习题解答第八章习题解答 8.17 某单位招收懂俄、英、日、德、法文翻某单位招收懂俄、英、日、德、法文翻译各译各1人，有人，有5人应聘。已知：乙懂俄文，甲
10、、乙、人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这懂法文，问这5个人是否都能得到聘书个人是否都能得到聘书?最多几人能最多几人能得到招聘，各从事哪一方面的翻译任务得到招聘，各从事哪一方面的翻译任务?解：某人懂某种语言作一条连线，权数为解：某人懂某种语言作一条连线，权数为1 1。甲甲-英语英语 乙乙-俄语俄语 丁丁-日语日语 戊戊-法语法语最多招聘最多招聘4 4个人。个人。第八章习题解答第八章习题解答 8.18 甲、乙、丙、丁、戊、己甲、乙、丙、丁、戊、己6人组成一个小人组成一个小组，检查组，检查5个单位的工作
11、，若一单位和乙、丙、丁三个单位的工作，若一单位和乙、丙、丁三人有工作联系，则用人有工作联系，则用乙，丙，丁乙，丙，丁表示，其余四个单表示，其余四个单位分别为位分别为甲，戊，己甲，戊，己，甲，乙，戊，己甲，乙，戊，己，甲，乙，甲，乙，丁，己丁，己，甲，乙，丙甲，乙，丙。若到一个单位去检查工作的。若到一个单位去检查工作的人必须是和该单位没有联系的人，问应如何安排人必须是和该单位没有联系的人，问应如何安排?解：此题应该假设解：此题应该假设1 1人只能去人只能去1 1个单位检查工作。个单位检查工作。但是一个单位可以有多人去检查。具体安排如下：但是一个单位可以有多人去检查。具体安排如下：甲和己甲和己单位
12、单位1、乙、乙单位单位2、丙、丙单位单位3、丁、丁单单位位5、戊、戊单位单位4。第八章习题解答第八章习题解答 8.19 图图8-61所示网络中，有向边旁数字为所示网络中，有向边旁数字为(cij，dij)，cij表示容量，表示容量，dij表示单位流量费用，试求从表示单位流量费用，试求从vs到到vt流值为流值为6的最小费用流。的最小费用流。解：解：最小费用为最小费用为3535。流量分布见下一个图形。流量分布见下一个图形。第八章习题解答第八章习题解答第八章习题解答第八章习题解答 8.20 某种货物由某种货物由2个仓库个仓库A1，A2运送到运送到3个配货中个配货中心心B1，B2，B3。A1，A2的库存
13、量分别为每天的库存量分别为每天13t，9t；B1，B2，B3每天需求分别为每天需求分别为9t，5t，6t。各仓库到配货。各仓库到配货中心的运输能力、单位运费如表中心的运输能力、单位运费如表84，求运费最省的，求运费最省的运输方案。运输方案。表表8-4运程运程运量限制运量限制(t(td)d)运费运费(百元百元/t)/t)AlB1AlB183AlB2AlB271lAlB3AlB3510A2B1A2B16SA2B2A2B237A2B3A2B354第八章习题解答第八章习题解答 解：最小费用流为解：最小费用流为105。流量分布如下：。流量分布如下：第八章习题解答第八章习题解答 8.21 8.21 有有5
14、 5批货物，要用船只从批货物，要用船只从x x1 1,x,x2 2地分别运地分别运往往y y1 1,y,y2 2,y,y3 3地。规定每批货物出发日期如表地。规定每批货物出发日期如表8-58-5所示，所示，又知船只航行所需时间又知船只航行所需时间(d)(d)如表如表8-68-6所示。每批货物只所示。每批货物只需一条船装需一条船装运，在空载和重载时航行时间相同，要求运，在空载和重载时航行时间相同，要求制定计划，以最少的船只完成这制定计划，以最少的船只完成这5项运输任务。项运输任务。表表8-5地点地点y y1 1y y2 2y y3 3x x1 15 51010/x x2 2/12121,81,8
15、表表8-5地点地点y y1 1y y2 2y y3 3x x1 12 23 32 2x x2 21 11 12 2 (提示：用提示：用Ti表示运输任务表示运输任务(i=1，2，3，4，5)。作二部图，。作二部图，凡完成凡完成Ti项任务后可继续完成项任务后可继续完成Tj项任务的在项任务的在Ti,Tj间连线，再求间连线，再求二部图的最大匹配。二部图的最大匹配。)p 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings结束语讲师：XXXXXX XX年XX月XX日
