应如何指派最有利？

表3-2

课程 学生 数学 物理 化学 外语 A B C D 89 87 95 75 92 88 90 78 68 65 85 89 81 78 72 96 4. 下表给出了使用各台设备完成各种工作的生产费用。试确定最优的指派方案，使总的生产费用最低。

表3-3

工作 设备 甲 乙 丙 丁 A B C D E 25 22 39 34 24 29 19 38 37 42 31 35 26 28 36 42 18 20 40 23 5. 某设备公司有三台设备可以租给A，B，C和D四项工程使用，各台设备用于各工程创造的利润如下表所示，问怎样分配设备才能使创造的总利润最大？

表3-4

工程 设备 M1 M2 M3 A 4 9 12 B 10 8 3 C 8 7 D 5 2 4 6. 已知下列五名运动员各种姿势的游泳成绩（各为50米）如下表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。

表3-5 仰泳 蛙泳 蝶泳 自由泳 赵 钱 孙 李 周 37.7 43.4 33.3 29.2 32.9 33.1 28.5 26.4 33.8 42.2 38.9 29.6 37.0 34.7 30.4 28.5 35.4 41.8 33.6 31.1 7. 现在有五项任务让甲、乙、丙、丁四个人去完成。其中一个人要完成两项任

9

务，每人完成各项任务的时间如下表所示。试确定总的花费时间为最少的分配方案。

表3-6 工作 工人 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 8. 从甲、乙、丙、丁、戊五个人中挑选四个人去完成四项工作。已知每人完成各项工作的时间如下表所示。规定每项工作只能有一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因为某种原因决定不同意承担第四项任务，在满足上述条件下，如何分配工作，使完成四项工作的总的花费时间为最少。

表3-7

工人 工作 甲 乙 丙 丁 戊 1 2 3 4 10 5 15 20 2 10 5 15 3 15 14 13 15 2 7 6 9 4 15 8 9. 6个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需要1人操作，试求使总收益最大的指派方案？

表3-8

工人 工作 1 2 3 4 A 3 5 4 5 B 6 7 6 8 C 8 9 8 10 D 10 10 9 11 E 12 11 10 12 F 13 12 11 13 10. 有四项工作要交给甲、乙、丙、丁四个人去完成，以致每个人完成各项工作的时间如下表所示，问应该怎样指派才能使总的消耗时间为最少。

表3-9

工作 工人 甲

A 15 B 18 C 21 D 24 10

乙 丙 丁

19 26 19 23 17 21 22 16 23 18 19 17 11

第四章 网络图论 4.1 图与网路的基本概念

1. 证明：任何G＝(V, E) 图中，所有节点次数之和必然是所有边数的2倍。 2. 证明：任何图G＝(V, E) 中，如果图中有奇点必为偶数个。 3. 写出下图4-1-1的开链、闭链、初等链、回路各2条。

图4-1-1

4. 证明如下序列不可能是某个简单图的次的序列。

1) 7, 6, 3, 4, 3, 2 2) 6, 5, 5, 4, 3, 2, 1

4.2 树图及最小生成树

1. 证明：若树图T中点的最大次大于等于k，则T中至少有k个悬挂点。2. 分别用广探法和深探法求下图的一颗生成树。

12