试日程表。（15分） 考试课程 研究生 1 2 3 4 5 6 7 8 9 10 A B C D E F ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ BEAFDC上午 下午 第一天 A E 第二天 C B 第三天 D F
4有甲乙丙丁戊己6名运动员报名参加ABCDEF6个项目的比赛，下表中打●的是各运动员报名参加的比赛项目，问6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛 甲 A B C D ● E F ● 乙 丙 丁 戊 己 ● ● ● ● ● ● ● ● ● ● 答案：BCAFED
DFABCE（14分） 求图中从
v至v的最小费用最大流，图中弧旁数字为（费用bstij，容量
cij）。
(6,6)(7,4)(2,3)vs(10,5)
(5,1)vt
(8,2)（图要求画出来）
V164V17Vt280V2V24Vs812Vs000
-66-7Vt28V20Vs012226V148
-6-7Vs812-22-8Vt
最大流为6， 费用为84，6*6+4*7+8*2+2*2=84 （每个图1.5分）
六、综合
1. 图的建模
有十六名运动员参加ABCDEFGH八种项目的游泳比赛，已知运动员号码及参加比赛项目如下表所示（表中打 ● 者为参加项目）。为使参加多项比赛的运动员恢复体力，要求比赛顺序安排保证每个运动员不连续参加两项比赛，问如何安排才能做到这一点？ 运动员 1 2 3 4 5 6 7 A ● ● ● B ● C ● ● ● D ● ● E ● ● F ● ● G H ● ● 8 9 10 11 12 13 14 15 16 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ABCDEGFH
解：将每个比赛项目用一个点表示，同一运动员参加比赛项目的点用边连接，如同所示。安排比赛的顺序做到相邻的项目点隔开安排。
安排顺序上可以有多个方案，其中之一可以是：E-A-G-D-C-F-B-H
2. 图建模：
有八种化学药品A,B,C,D,P,R,S,T要放进储藏室保管，出于安全原因，下列各组药品不能贮藏在同一室内：A-R,A-C,A-T,R-P,P-S,S-T,T-B,B-D,D-C,R-S,R-B,P-D,S-C,S-D,问贮藏这八种药品至少需要多少房间？
解：用八个点1.2.3.4.5.6.7.8.分别代表A,B,C,D,P,R,S,T八种药品，将不能放在同一室内的药品用边连接，得如下图
将1着红色，则7可着红色，2可着红色，将3着为绿色，则5可着为绿色，8可着绿色，而4,6可着黄色。
于是至少需要三个房间贮藏这八种化学药品，其中一个最优方案是ABS占一间，CPT占一间，DR占一间。
