《运筹学》-第八章图与网络分析习题及-答案(共5页).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,8)为11．解：此为最短路问题铺设路线由下图给出，最短输水管道为6.5公里 ①④⑧ ② ③⑤⑥⑦12．最大流为3213．最大流为1014．解：（1）最大流量为6，最小费用为84；（2）最大流量为3，最小费用为27专心---专注---专业。