《运筹学》 第八章图与网络分析习题及 答案.doc

运筹学第八章图与网络分析习题1.思考题() 解释下列名词，并说明相互之间的区别与联系：顶点，相邻，关联边；环，多重边，简单图；链，初等链；圈，初等圈，简单拳；回路，初等路；节点的次，悬挂点，孤立点；）连通图，连同分图，支撑子图；有向图，基础图，赋权图。子图，部分图，真子图() 通常用记号（，）表示一个图，解释及的涵义及这个表达式的涵义() 通常用记号（，）表示一个有向图，解释及的涵义及这个表达式的涵义() 图论中的图与一般几何图形的主要区别是什么？() 试述树与图的区别与联系() 试述 求最短路问题的ijkstra算法的基本思想及其计算步骤() 试述寻求最大流的标号法的步骤与方法() 简述最小费用最大流的概念及其求解的基本思想和方法() 通常用记号（，）表示一个网络，试解释这个表达式的涵义(10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？(11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。2.判断下列说法是否正确(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。(3) 如果一个图G从V1到各点的最短路是唯一的，则连接V1到各点的最短路，再去掉重复边，得到的图即为最小支撑树。(4 )图G的最小支撑树中从V1到Vn的通路一定是图G从V1到Vn的最短路。(5) fij=0总是最大流问题的一个可行流。(6 )无孤立点的图一定是连通图。(7) 图中任意两点之间都有一条简单链，则该图是一棵树。(8) 求网络最大流的问题总可以归结为求解一个线性规划问题。(9)在图中求一点到另一点n的最短路问题总可以归结为一个整数规划问题(10) 图G中的一个点V1总可以看成是G的一个子图。3.证明：在人数超过2的人群中，总有两个人在这群人中恰有相同的朋友数。4.已知九个人，和两个人握过手，各和四个人握过手，各和五个人握过手，各和六个人握过手。证明这九个人中，一定可以找出三个人互相握过手。C7V1V2V3V4V5V6V7V8V9C1C2C3C4C5C6C8C9C10C11C12C13C145用破圈法和避圈法求下图的部分树V1V2V3V4V5V6(1)6写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。V1V2V3V4V5(2) 7完全图n 有多少条边？8求下列各图的最小树（）（）（）（）9.用标号法求下图中从到各顶点的最短距离V1V2V3V4V5V6V7V8V9V10V11263575213723414316738410在下图中用标号法求（）从到各顶点的最短距离；（）若从到，走哪一条路最短。V1V2V3V4V5V6V7V8V9433243831232111已知8个村镇，相互间距离如下表所示,已知1号村镇离水源最近，为5公里，问从水源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修，水管要求在各村镇处分开）。 各村镇间距离 （单位：公里） 到从234567811.52.51.02.02.53.51.521.02.01.03.02.51.832.52.02.52.01.042.51.51.51.053.01.81.560.81.070.51215V1Vt8106108491014181281315612.用标号法求下面网络的最大流.13. 用标号法求下面网络的最大流.V1Vt4453342535823 V1Vt(5,6)(9,2)(3,2)(4,1)(3,4)(4,19)(2,3)(1,1)(2)V1Vt(6,6)(10,5)(5,1)(2,3)(7,4)(8,2)(1)14.求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量. 运筹学第八章图与网络分析习题解答2（1） （2）X（3） （4）X（5） （6）X（7）X（8）（9）（10）6解：图（）顶点数个；边数条；每个顶点的次数都为次，是简单图。图（）顶点数个；边数条；每个顶点的次数v4 ,v5 次，其它各顶点都为次，是简单图。7解：完全图的边数为条。V1V2V3V4V5V6V7V8V9V10V11（o,0）(v1,2)(v1,6)(v1,3)(v2,7)(v5,8)(v9,14)(V9,12)(v4,10)(v7,11)(v10,15)9解：10解：从到的最短路 V1V2V3V4V5V6V7V8V91（o,0）(v1,4)(v2,7)(V1,3)(V2,6)(V2,7)(V5,6)(V7,8)(V7