运筹学上机试题5-图论

《运筹学》试题一、名词解释（20分）对偶可行基影子价格灵敏度分析平衡运输问题不平衡运输问题纯整数规划0—1规划问题混合整数规划网络最大流问题二、选择题（20分）1、我们可以通过（）来验证模型最优解。

A观察B应用C实验D调查2、建立运筹学模型的过程不包括（）阶段。

A观察环境B数据分析C模型设计D模型实施3、建立模型的一个基本理由是去揭晓那些重要的或有关的（）A数量B变量 C 约束条件 D 目标函数4、模型中要求变量取值（）A可正B可负C非正D非负5、运筹学研究和解决问题的效果具有（）A连续性 B 整体性 C 阶段性 D 再生性6、如果线性规划问题有可行解，那么该解必须满足（）A所有约束条件 B 变量取值非负 C 所有等式要求 D 所有不等式要求7、如果线性规划问题存在目标函数为有限值的最优解，求解时只需在（）集合中进行搜索即可得到最优解。

A基 B 基本解 C 基可行解 D 可行域8、线性规划问题是针对（）求极值问题.A约束B决策变量 C 秩D目标函数9、如果第K个约束条件是“≤”情形，若化为标准形式，需要（）A左边增加一个变量B右边增加一个变量C左边减去一个变量D右边减去一个变量10、若某个bk≤0, 化为标准形式时原不等式（）A不变 B 左端乘负1 C 右端乘负1 D 两边乘负1三、填空题（20分）1、线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求（）的线性规划问题与之对应，反之亦然。

2、在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的（）。

3、如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为（）。

4、对偶问题的对偶问题是（）。

5、若原问题可行，但目标函数无界，则对偶问题（）。

6、在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容许变动范围内发生Δb1的变化，则新的最优解对应的最优目标函数值是（）(设原最优目标函数值为Z﹡)7、若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用（）求解。

二、应用题题0：（1996年全国数学联赛）有n（n≥6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。

证明这n个人中必有3个人互相认识。

注：[n/2]表示不超过n/2的最大整数。

证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。

由条件可知，G是具有n个顶点的简单图，并且有（1）对每个顶点x，)(xN G≥[n/2]；（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。

情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。

情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。

若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。

故k ≠r+1，同理t ≠r+1。

所以t=r,k=r 。

记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。

若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。

图论测试题及答案一、选择题1. 在图论中，如果一个图的每个顶点的度数都是偶数，那么这个图一定存在欧拉路径吗？A. 是的B. 不一定C. 没有欧拉路径D. 无法确定答案：B2. 图论中的哈密顿路径是指什么？A. 经过图中所有顶点的路径B. 经过图中所有顶点的回路C. 经过图中某些顶点的路径D. 经过图中某些顶点的回路答案：A3. 如果一个图是完全图，那么它的边数是多少？A. 顶点数的一半B. 顶点数的平方C. 顶点数的两倍D. 顶点数减一答案：B二、填空题4. 在无向图中，如果存在一条路径，使得每个顶点只被经过一次，并且起点和终点相同，这样的路径被称为________。

答案：欧拉回路5. 图论中的二分图是指图中的顶点可以被分成两个不相交的集合，使得同一个集合内的顶点之间没有边，而不同集合之间的顶点之间有边，这种图也被称为________。

答案：二部图三、简答题6. 请简述图论中的最短路径问题，并给出解决该问题的一种算法。

答案：最短路径问题是在图中找到两个顶点之间的最短路径的问题。

解决该问题的一种算法是迪杰斯特拉算法（Dijkstra's algorithm），该算法通过维护一个顶点集合来记录已经找到最短路径的顶点，并迭代更新距离，直到找到从起点到所有顶点的最短路径。

7. 描述图论中的图着色问题，并说明其在实际生活中的应用。

答案：图着色问题是将图的顶点着色，使得任何两个相邻的顶点颜色不同。

在实际生活中，图着色问题可以应用于时间表的安排、频率分配、电路设计等领域，其中每个顶点代表一个任务或频道，而颜色则代表不同的时间段或频率。

结束语：以上是图论测试题及答案，希望能够帮助大家更好地理解和掌握图论的基本概念和算法。

四、图论1、求下图中从v1到v3最短路。

从节点 1到节点3的最短路起点终点距离1 2 12 3 6此问题的解为:72、最小生成树电信公司要在15个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。

试求出一个连接在15个城市的铺设方案，使得总费用最小。

此问题的最小生成树如下：起点终点距离1 4 11 2 22 5 25 8 15 6 26 3 18 7 28 9 39 12 212 11 411 10 110 13 313 14 114 15 3此问题的解为:283、最短路问题例. 求下图中从v1到各点的最短路，并指出有哪些点是不可达到的。

从节点 1到节点2的最短路起点终点距离1 2 4此问题的解为:41到3没有路1到4没有路从节点 1到节点5的最短路起点终点距离1 5 1此问题的解为:1从节点 1到节点6的最短路起点终点距离1 5 15 6 6此问题的解为:7从节点 1到节点7的最短路起点终点距离1 7 3此问题的解为:3从节点 1到节点8的最短路起点终点距离1 5 15 6 66 8 3此问题的解为:104、最短路问题有6个村庄，各村庄的距离如下图所示。

现在要开办一所小学，问应该建在哪个村庄，才能使得各村的学生上学的总路程最短？最小为17，选择村庄2或者村庄5建立学校5、例（多发点多收点的最大流问题）某产品有两个产地s1、s2，三个销地t1、t2、t3。

运输系统如下图所示，其中v1和v2是两个中转站，各弧旁的数字是最大运输能力。

求从产地到销地的最大运输量。

V1-V2流量为2从节点 1到节点9的最大流起点终点距离1 2 271 3 182 6 102 4 52 5 123 5 63 8 124 6 74 7 05 4 2s1s22727C85 76 5 8 10 6 9 17 7 9 689 22 此问题的解为:456 例（顶点有容量约束的最大流问题）某油田s 通过输油管道向一炼油厂t 输送原油，中间经过三个泵站v 1、v 2和v 3，管道的输送能力和各泵站的输送能力如下图。

图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。

答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。

答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。

答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。

答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。

答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。

答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。

2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。

四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。

答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。