学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 管理学 > 《运筹学》 第八章图与网络分析习题及 答案

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

《运筹学》 期末考试 试卷 习题库 答案

《运筹学》第八章图与网络分析习题

1.思考题

(1)解释下列名词,并说明相互之间的区别与联系:①顶点,相邻,关联边;

②环,多重边,简单图;③链,初等链;④圈,初等圈,简单拳;⑤ 回 路,初等路;⑥节点的次,悬挂点,孤立点;⑦)连通图,连同分图, 支 撑子图;⑧有向图,基础图,赋权图。⑨子图,部分图,真子图.

(2)通常用记号G=(V,E)表示一个图,解释V及E的涵义及这个表达式 的涵义.

(3)通常用记号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的人群中,总有两个人在这群人中恰有相同的朋友数。

v4.已知九个人1,v2, ,v9,v1和两个人握过手,v2,v3各和四个人握过手,

v4,v5,v6,v7各和五个人握过手,v8,v9各和六个人握过手。证明这九个人中,一定可

以找出三个人互相握过手。

V2CC3

V6 V4

V1 C6

V5C1011

V7

CV8

14

C13

V9

5.用破圈法和避圈法求下图的部分树

第1页

我要评论

相关文档

  • 《运筹学教程》(第三版)第八章 图与网络分析

    《运筹学教程》(第三版)第八章 图与网络分析 隐藏>> 第八章 图与网络分析图论 是广泛应用在物理学、化学、控制论、信息论、 科学管理、电力通讯、编码理论、...

  • 运筹学课件 第八章 图与网络分析

    运筹学课件 第八章 图与网络分析_自然科学_专业资料...数学家Euler在1736年巧妙地给出 了这个问题的答案,...? ? ? 1.思考题 子图与生成子图的区别是什么?...

  • 运筹学课件第八章 图与网络分析

    运筹学课件第八章 图与网络分析_数学_自然科学_专业...弧集:A={a1,a1,…,am} 3、有向图:由点及弧...在家全套瑜伽练习教程 89份文档 爆笑大撞脸 超爆笑...

  • 《运筹学》第8章_图与网络分析

    《运筹学》第8章_图与网络分析《运筹学》第8章_...为了寻找答案,1736年欧拉将这个问题抽 象成所示图形...练习1:上图表示 个村庄的线路图 个村庄的线路图,...

  • 运筹学第八章图与网络分析

    第八章 图与网络分析h 运... 暂无评价 56页 2财富值 《运筹学》第8章_图与网络... 80页 2财富值喜欢此文档的还喜欢 第5章_图与网络分析 132页 2财富...

  • 运筹学:第八章图与网络分析

    运筹学:第八章图与网络分析运筹学:第八章图与网络分析隐藏>> 第六章 图与网络分析 例1、哥尼斯堡七桥问题 、C C A B A B D D 1 §6.1 图与网络的...

  • 第八章运筹学图与网络分析

    运筹学课件 第八章 图... 67页 免费 第八章 图与网络分析h 运... 暂无评价 56页 2财富值 《运筹学》第8章_图与网络... 80页 2财富值喜欢...

  • 运筹学第八章图与网络分析

    第八章 图与网络分析h 运... 暂无评价 56页 2财富值 《运筹学》第8章_图...按题意,相邻顶点对应 课程不能连续考试,不相邻顶点对应课程允许 连续考试,因此,...

  • 运筹学8图与网络分析

    《运筹学》 第八章图与网络... 5页 10财富值 ...2009生物高考试题A卷(广东... 66页 免费 计算机二级...为了寻找答案,1736年欧拉将这 个问题抽象成图8.1b...

  • 运筹学8图与网络

    运筹学第八章 图与网络分析 教学目的:让学生了解...例8—2 一个乡有9个自然村,其间道路及 各道路...驾考新题抢先版 89份文档 应届生求职季宝典 英文...

  • 运筹学习题答案(第八章)

    运筹学习题答案(第八章)_数学_自然科学_专业资料。...运筹学教程 第八章习题解答 8.12 求图8-57网络...《运筹学》 第八章图与网... 5页 4下载券 ...

更多文档:

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.xuehai.net All Rights Reserved.  email
返回顶部