当前位置：问答库＞考研试题

一、计算题

1． 证明如下序列不可能是某个简单图的次的序列:

（l ）7，6，5，4，3，2;

（2）6，6，5，4，3，2，l ;

（3）6，5，5，4，3，2，l 。

【答案】（1）由定理知，

能是图的次序列。

（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。

（3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。

； v 2与v 1之间存在边e 12:，而①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7）

v 7的次为1，所以必不与v 1外的其他点相连。因而，v 2与除v 1，v 7外的四点之间各有一条连线。 至此，v l 、v 2与v 3、v 4、v 5和v 6中任意一个就组成了环，则G 不是简单图。

②假定G 中无环，则根据情形①的分析，v 1的关联边中必存在重复边。从而G 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。

2． 某建筑公司最近几年的发展重点是承接中东等地区的建筑项目。公司需要一种大型的建筑设备，该设备 今后4年的购买价格（预测值）分别为（5 .0，5.3，5.7，6.0）（万元）（产品购买价+运输到工地的费用）。如该设备连 续使用，其第i 年的使用费及维修费分别为（l ，1.7，2.5，3.3）

，（万元）由于路途遥远，淘汰后的设备就在当地折价 处理了，使用满i 年的设备处理价格为（3.3，

2.5，1.5，0.8）（万元）. 公司在制定一个4年的设备购买计划，你有什 么建议? （限用图论理论，写出算法，计算过程，最终结论，最佳总费用）

【答案】可以把这个问题转化为最短路问题，根据题意绘制如下赋权有向图。

为偶数，而在此序列中，为奇数，所以此序列不可

图

采用Dijksra 算法计算图1中的最短路为:

（l ）对起点1进行P 标号，即p （l ）=0; 对其余点进行T 标号，

即

第 2 页，共 50 页

检查点1，进行T 标号：

（2）点2获得P 标号，.

（3）点3获得P 标号，

（4）点4获得P 标号，

（5）点5获得P 标号，）

上图中的最短路为检查点2，修改T 标号:检查点3，修改T 标号:检查点4，无需修改T 标号。 求解结束。 。即第一年初购进一台设备，第三年初淘汰掉并购置新设备，直至第四年末淘汰 掉。最佳总费用11.1万元。

3． 设D=（W ，A ，C ）是一个网络。证明:如果D 中所有弧的容量c ij 都是整数，那么必存在一个最大流

初始号为:

。对于弧。 ，v j 的标号为:，因为c ij 均为整数，所以最终得至。调整量【答案】证明:将该问题转化为网络最大流的问题，并由寻求最大流的标号法进行求解。 ; 对于弧，v j 的标也为整数。故

标号最终结果，得最大流f 必为整数。

4． 某软件公司可承揽四个软件开发项目，每一项目均由A ，B ，C ，D 四个模块中的不同模块构成。对于 项目中的共有模块，只需研发一次就可以为所有需要的项目服务. 各项目售价与模块构成及各模块研发成本如表1 、表2所示. 那么这家公司应选择承揽哪些项目才能使利润最大化? 试就这一问题建立相应的数学模型。

表

1

表

2

【答案】设

第 3 页，共 50 页

5． 泰泽公司是一家制药公司。在研究了市场的需求，分析了当前药物的不足并且拜会了大量在有良好前景 的医药领域进行研究的科学家之后，总裁罗宾斯先生决定进行五个项目的开发研究:U P 项目、stable 项目、choice 项目、Hope 项目和Release 项目。公司现在有五位资深的科学家来领导进行这五个项目。总裁清楚，科学家们只 有在受到项目所带来的挑战和激励的时候才会努力工作。为了保证这些科学家都能够到他们感兴趣的项目中去， 项目开发部为这个项目建立了一个投标系统。这五位科学家每个人都有1000点的投标点。他们向每一个项目投 标，并且把较多的投标点投向自己最感兴趣的项目之中。如下表显示了这五位科学家进行投标的情况。 试建立反映如下各问题的数学模型并求解:

（l ）将这五位科学家指派各负责一个项目，使他们总的满意的投标点数最大;

（2）罗林斯博士接到哈佛医学院的邀请去完成一个教学任务必须离开公司，而且每个人只负责一个项目，这 时公司应当放弃哪个项目?

（3）若公司不愿意因罗林斯博士离开而放弃任何一个项目，这时应该由哪一个科学家兼任两个项目的研究才 能使得对项目的总的热情最大?

表 五位科学家进行投标的情况

【答案】首先建立这个问题的数学模型为:

（l ）这是个最大化指派问题，先将它化为最小化指派问题为:

第 4 页，共 50 页