《运筹学》课程教学资源（试卷习题）第8章 图与网络分析习题

《运筹学》第八章图与网络分析习题1.思考题（1）解释下列名词，并说明相互之间的区别与联系：①顶点，相邻，关联边：②环，多重边，简单图：③链，初等链：圈，初等圈，简单拳；③回路，初等路；③节点的次，悬挂点，孤立点：）连通图，连同分图，支撑子图；③有向图，基础图，赋权图。③子图，部分图，真子图（2）通常用记号G一（V，E）表示一个图，解释V及E的涵义及这个表达式的涵义（3）通常用记号D=（V，A）表示一个有向图，解释V及A的涵义及这个表达式的涵义，（4）图论中的图与一般几何图形的主要区别是什么？（5）试述树与图的区别与联系：（6）试述求最短路问题的Diikstra算法的基本思想及其计算步骤（7）试述寻求最大流的标号法的步骤与方法（8）简述最小费用最大流的概念及其求解的基本思想和方法（9）通常用记号N=（V，A，C）表示一个网络，试解释这个表达式的涵义，（10）在最大流问题中，为什么当存在增广链时，可行流不是最大流？（11）试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。2.判断下列说法是否正确（1）图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。(2）一个图G是树的充分必要条件是边数最少的无孤立点的图。（3）如果一个图G从V到各点的最短路是唯一的，则连接V到各点的最短路再去掉重复边，得到的图即为最小支撑树。（4）图G的最小支撑树中从V.到V.的通路一定是图G从V.到V.的最短路。（5）（f：=0)总是最大流问题的一个可行流。（6）无孤立点的图一定是连通图。（7）图中任意两点之间都有一条简单链，则该图是一棵树。（8）求网络最大流的问题总可以归结为求解一个线性规划问题。(9)在图中求一点V到另一点V.的最短路问题总可以归结为一个整数规划问题（10）图G中的一个点Vi总可以看成是G的一个子图。3.证明：在人数超过2的人群中，总有两个人在这群人中恰有相同的朋友数。4.已知九个人"，V2，"，Vg，V和两个人握过手，V2，V3各和四个人握过手，V4，V'，V6，V各和五个人握过手，V8，V各和六个人握过手。证明这九个人中，一定可以找出三个人互相握过手

《运筹学》第八章图与网络分析习题 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.已知九个人 1 2 9 v ,v ,  ,v ， 1 v 和两个人握过手， 2 3 v ,v 各和四个人握过手， 4 5 6 7 v ,v ,v ,v 各和五个人握过手， 8 9 v ,v 各和六个人握过手。证明这九个人中， 一定可以找出三个人互相握过手

5.用破圈法和避圈法求下图的部分树VC2V4VVsC6C10(3)C13V,V96.写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。VV3(2)(1)7.完全图K，有多少条边？8.求下列各图的最小树O(2)（1(3)

１ ７ ３ ２ ５ ３ ６ ２ ８ ４ ５ ３ １ 5．用破圈法和避圈法求下图的部分树 6．写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。 7．完全图Ｋn 有多少条边？ 8．求下列各图的最小树 （３） C7 V1 V2 V3 V4 V5 V6 V7 V8 V9 C1 C2 C3 C4 C5 C6 C8 C9 C10 C11 C12 C13 C14 V1 V2 V3 V4 V6 V5 (1) V1 V2 V3 V V4 5 (2) ５ １ ３ ７ ４ ２ ５ ２ ８ ６ ２ ７ ４ ３ ７ ４ ３ （１） ５ ２ ３ ４ ２ ４ ６ １ ２ ４ ３ ９ （２） （３）

9.用标号法求下图中从V到各顶点的最短距离V3YV4V107V7110.在下图中用标号法求（1）从y到各顶点的最短距离：（2）若从v到Vg，走哪一条路最短。VVV2Vs211：已知8个村镇，相互间距离如下表所示，已知1号村镇离水源最近，为5公里，问从水源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修，水管要求在各村镇处分开）。各村镇间距离（单位：公里）到2346851人1.52.51.02.02.53.51. 5-21.02.01.03. 01.82.532.52.001.02..52.42.5S1.053.08.5心60.8

9.用标号法求下图中从 1 v 到各顶点的最短距离 10．在下图中用标号法求 （１）从 1 v 到各顶点的最短距离；（２）若从 1 v 到 9 v ，走哪一条路最短。 11．已知 8 个村镇，相互间距离如下表所示,已知 1 号村镇离水源最近，为 5 公里， 问从水源经 1 号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短 （为便于管理和维修，水管要求在各村镇处分开）。 各村镇间距离 （单位：公里） 到 从 2 3 4 5 6 7 8 1 1.5 2.5 1.0 2.0 2.5 3.5 1.5 2 1.0 2.0 1.0 3.0 2.5 1.8 3 2.5 2.0 2.5 2.0 1.0 4 2.5 1.5 1.5 1.0 5 3.0 1.8 1.5 6 0.8 1.0 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 2 6 3 5 7 5 2 1 3 7 2 3 4 1 4 3 1 6 7 3 8 4 V1 V2 V3 V4 V5 V6 V7 V8 V9 4 3 3 2 4 3 8 3 1 2 3 2 1

70.512.用标号法求下面网络的最大流15VV151018V2614813.用标号法求下面网络的最大流2NV414.求下列网络的最小费用最大流.括号内的两个数字，前一个是单位流量的费用，后一个是该弧的流量.(3,4)(5,6)(3,2)(6,6)(7,4)V(4,1)(1,1)V.V(5,1)(2,3)(4,19)(9,2)V(8,2)(10,5)(2,3)(1)(2)

7 0.5 12.用标号法求下面网络的最大流. 13. 用标号法求下面网络的最大流. 14.求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后 一个是该弧的流量. V1 Vt 4 4 5 3 3 4 2 5 3 5 8 2 3 12 V1 15 Vt 8 10 6 10 8 4 9 10 14 18 12 8 13 15 6 V1 Vt (5,6) (9,2) (3,2) (4,1) (3,4) (4,19) (2,3) (1,1) (2) V1 Vt (6,6) (10,5) (5,1) (2,3) (7,4) (8,2) (1)