DOC《习题》

习题 证明在9座工厂之间,不可能每座工厂只与其它3座工厂有业务联系,也不可 能只有4座工厂与偶数个工厂有业务联系.

有八种化学药品A,B ,C,D,E,F,G,H要放进贮藏室.从安全角度虑,下 列各组药品不能贮存在同一室内:A-C,A-F,A-H,B-D,B-F,B-H,C-D,C-G,D-E,D-G,E-G,E-F,F-G,G-H,问至少需要几间贮藏室存放这此药品. 8.3 6个人围成圆圈就座,每个人恰好与相邻者不相识,是否可以重新就座,使每个人都与邻座认识? 8.4 判定图8-49中的两个图能否一笔画出,若能,则用图形表示其画法. 求解如图8-50所示中的中国邮路问题,A点是邮局. 分别用深探法、广探法、破圈法找出图8-51所示的一个生成树. 设计如图8-52所示的锅炉房到各座楼铺设暖气管道的路线,使管道总长度最小(单位:cm). 分别用避圈法和破圈法求图8-53所示各图的最小树. 8.9 最优检索问题.使用计算机进行图书分类.现有五类图书共100万册,其中有A类50万册,有B类20万册,C类5万册,D类15万册.问如何安排分检过程,可使总的运算(比较)次数最小? 8.10 如图8-54,是一仓库,是商店,求一条从到的最短路. 8.11 求图8-55中到各点的最短路. 求图8-56网络中各顶点间的最短路. 某设备今后五年的价格预测分别是(5,5,6,7,8),若该设备连续使用,其第j年的维修费用分别为(1,2,3,5,6),某单位今年购进一台,问如何确定更新方案可使5年里总支出最小(不管设备使用了多少年,其残值为0). 求图8-57中网络最大流,边上数为. 如图8-58,发点分别可供应10和15个单位,收点可以接收10和25 个单位,求最大流,边上数为. 8.16 如图8-59,从派车到,中间可经过各站,若各站间道路旁的数学表示单位时间内此路上所能通过的最多车辆数,问就如何派车才能使单位时间内达的车辆最多? 8.17 某单位招收懂俄、英、日、德、法文翻译各1人,有5人应聘.已知:乙懂英文,甲、乙、丙懂英文,

四、丙、丁懂日文、乙、戊懂德文,戊懂法文,问这5个人是否都能得到聘书?最多几人能得到招聘,各从事哪一方面的翻译任务? 8.18 甲、乙、丙、丁、戊、已6 组成一个小组,检查5个单位的工作,若一单位和乙、丙、丁三人有工作联系,则用{乙,丙,丁}表示,其余四个单位分别为{甲,戊,已},{甲,乙,戊,已},{甲,乙,丁,已},{甲,乙,丙}.若一单位去检查工作的人必须是和该单位没有联系的人,问应如何安排? 8.19 图8-60所示网络中,有向边旁数学为,表示容量,表示单位流量费用,试求从到流值为6的最小费用流. 8.20 某种货物由2个仓库运送到3个配货中心.的库存量分别为每天13t,9t;

每天需求分别为9t,5t,6t.各仓库到配货中心的运输能力、单位运费如表8-4所示,求运费最省的运输方案. 表8-4 运程 运量限制(t/d) 运费(百元/t)

8 7

5 6

3 5

3 11

10 8

7 4 8.21 有5批货物,要用船只从地分别运往地.规定每批货物出发日期如表8-5所示,又知船只航行所需时间(d)如表8-6所示.每批货物只需一条船装运,在空载和重载时航行时间相同,要求制订计划,以最少的船只完成这?5项运输任务. 表8-5 地点

5 10 / /

12 1.8 表8-5 地点

2 3

2 1

1 2 (提示:用表示运输任务(i=1,2,3,4,5).作两部图,凡完成项任务后可继续完成项任务的在,间连续,再求两部图的最大匹配.)