- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《运筹学》 第八章图与网络分析习题及 答案
《运筹学》第八章图与网络分析习题
1.思考题
解释下列名词,并说明相互之间的区别与联系:①顶点,相邻,关联边;
②环,多重边,简单图;③链,初等链;④圈,初等圈,简单拳;⑤ 回
路,初等路;⑥节点的次,悬挂点,孤立点;⑦)连通图,连同分图, 支
撑子图;⑧有向图,基础图,赋权图。⑨子图,部分图,真子图.
通常用记号G=(V,E)表示一个图,解释V及E的涵义及这个表达式
的涵义.
通常用记号D=(V,A)表示一个有向图,解释V及A的涵义及这个表
达式的涵义.
(4) 图论中的图与一般几何图形的主要区别是什么?
(5) 试述树与图的区别与联系.
(6) 试述 求最短路问题的Dijkstra算法的基本思想及其计算步骤.
(7) 试述寻求最大流的标号法的步骤与方法.
(8) 简述最小费用最大流的概念及其求解的基本思想和方法.
(9) 通常用记号N=(V,A,C)表示一个网络,试解释这个表达式的涵义.
(10) 在最大流问题中,为什么当存在增广链时,可行流不是最大流?
(11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。
2.判断下列说法是否正确
(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系,它与图的几何
形状无关。
(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。
(3) 如果一个图G从V1到各点的最短路是唯一的,则连接V1到各点的最短路,再去掉重复边,得到的图即为最小支撑树。
(4 )图G的最小支撑树中从V1到Vn的通路一定是图G从V1到Vn的最短路。
(5) {fij=0}总是最大流问题的一个可行流。
(6 )无孤立点的图一定是连通图。
(7) 图中任意两点之间都有一条简单链,则该图是一棵树。
(8) 求网络最大流的问题总可以归结为求解一个线性规划问题。
(9)在图中求一点V1到另一点Vn的最短路问题总可以归结为一个整数规划问题
(10) 图G中的一个点V1总可以看成是G的一个子图。
3.证明:在人数超过2的人群中,总有两个人在这群人中恰有相同的朋友数。
4.已知九个人,和两个人握过手,各和四个人握过手,各和五个人握过手,各和六个人握过手。证明这九个人中,一定可以找出三个人互相握过手。
5.用破圈法和避圈法求下图的部分树
6.写出下面各图中的顶点数、边数及顶点的次数,哪些是简单图。
7.完全图Kn 有多少条边?
8.求下列各图的最小树
(3)9.用标号法求下图中从到各顶点的最短距离
10.在下图中用标号法求
(1)从到各顶点的最短距离;(2)若从到,走哪一条路最短。
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 7 0.5 12.用标号法求下面网络的最大流.
13. 用标号法求下面网络的最大流.
14.求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量.
《运筹学》第八章图与网络分析习题解答
2.(1)√ (2)X(3)√ (4)X(5)√ (6)X(7)X(8)√(9)√(10)√
6.解:图(1)顶点数6个;边数12条;每个顶点的次数都为4次,是简单图。
图(2)顶点数5个;边数9条;每个顶点的次数v4 ,v5 3次,其它各顶点都为4次,是简单图。
7.解:完全图的边数为条。
9.解:
10.解:
从到的最短路为。
11.解:此为最短路问题。铺设路线由下图给出,最短输水管道为6.5公里。
12.最大流为32。
13.最大流为10。
14.解:(1)最大流量为6,最小费用为84;
(2)最大流量为3,最小费用为27。
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
V5
V6
(1)
V1
V2
V3
V4
V5
(2)
5
1
3
7
4
2
5
2
8
6
2
您可能关注的文档
- XX公司招标管理工作总结.doc
- XX公司煤改气工程 燃气工程项目策划书.doc
- XX公司财务规划书.doc
- XX农资连锁超市行政总务管理制度汇编.doc
- XX医院信息系统.doc
- XX县创建全国农村中医药工作先进单位汇报.doc
- XX商业管理公司运作思路.doc
- XX商业广场智能化系统技术方案.doc
- XX学校安全管理制度及应急预案.doc
- XX学校园区网络设计方案.doc
- 中国国家标准 GB/T 18233.4-2024信息技术 用户建筑群通用布缆 第4部分:住宅.pdf
- GB/T 18233.4-2024信息技术 用户建筑群通用布缆 第4部分:住宅.pdf
- GB/T 18978.210-2024人-系统交互工效学 第210部分:以人为中心的交互系统设计.pdf
- 《GB/T 18978.210-2024人-系统交互工效学 第210部分:以人为中心的交互系统设计》.pdf
- 中国国家标准 GB/T 18978.210-2024人-系统交互工效学 第210部分:以人为中心的交互系统设计.pdf
- GB/T 16649.2-2024识别卡 集成电路卡 第2部分:带触点的卡 触点的尺寸和位置.pdf
- 《GB/T 16649.2-2024识别卡 集成电路卡 第2部分:带触点的卡 触点的尺寸和位置》.pdf
- 中国国家标准 GB/T 16649.2-2024识别卡 集成电路卡 第2部分:带触点的卡 触点的尺寸和位置.pdf
- GB/T 17889.4-2024梯子 第4部分:铰链梯.pdf
- 《GB/T 17889.4-2024梯子 第4部分:铰链梯》.pdf
文档评论(0)