第七章图与网络分析
一、单项选择题
1．关于可行流，以下叙述不正确的是（）
A.可行流的流量大于零而小于容量限制条件
B．在网络的任一中间点，可行流满足流人量=流出量
C．各条有向边上的流量均为零的流是一个可行流
D．可行流的流量小于或等于容量限制条件而大于或等于零
2．关于最小树，以下叙述（）正确。
A.最小树是一个网络中连通所有点而边数最少的图
B．最小树是一个网络中连通所有的点，而权数最少的图
C．一个网络中的最大权边必不包含在其最小树内
D．一个网络的最小树一般是唯一的。
3．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（）
A. 边缘结点
B.未接结点
C.已接结点
D.最重要结点
4.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（）
A.连接的总长度最大
B.连接的总长度最小
C.连接的总长度为0
D.计算总长度5．最小树问题就是在网络图中，找出若干条边，连接（）
A.相邻结点
B.头尾结点
C.部分结点
D.所有结点
6．任一树中的边数和它的点数之间的关系是（）
A.边数等于点数减1
B.边数等于点数加1
C.点数等于边数减1
D.点数等于边数加1 7．最大流问题中，对于一个可行流，V i V j有向边上的流量f ij必须满足的条件之一是（）
A.0≤f ij≥c ij
B.0≥f ij≤c ij
C. 0≤f ij≤c ij
D. 0≥f ij≥c ij
8.一个连通图中的最小树可能不唯一，其权（）
A.是唯一确定的
B.可能不唯一
C.可能不存在
D.一定有多个
二、多项选择题
1.关于图论中图的概念，以下叙述正确的的（）
A.图中的边可以是有向边，也可以是无向边
B.图中的各条边上可以标注权
C.结点数等于边数的连通图必含圈
D.结点数等于边数的图必连通
E.图中的边只能是有向边
2.关于最短路，以下叙述不正确的有（）
A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的
B．从起点出发到终点的最短路是唯一的
C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上
D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上
E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上
3.关于增广链，以下叙述正确的有（）
A．增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致
B．增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致
C．增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边 D．增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边
E．增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边4.在下图中，根据（a）生成的支撑树有（）
三、应用题
1.下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做?最小的总长度是多少?
2．对下面的连通图，试求出最小树。
3．用标号法求下图所示的最大流问题，弧上数字为容量和初始可行流量。
4．
5．
参考答案
一、单项选择题
1-5．ABBDD 6-8．ACA
二、多项选择题
1. ABC
2.BCDE
3. BC
4. BCD
三、应用题
2.解：
3．最大流f*=15
4．
5．
第二节 最大流和最小割 一、割 若S 为V 的一个子集，S y S V S S x ∈-=∈,,，记),(S S K =为起点在S 中，终点在S 中的全体有向边的集合，即 {} S v S u v u K ∈∈=,),( （11-4） 我们称边集),(S S K =为网络G 的一个割，称∑∈K e e C )(为K 的容量，记为 Cap K 。 例5 给运输网络如图11-8所示，试 求与给定的j S （j =1，2，3）相对应的 Cap j K 。 解取{}11,v x S =， {}),(),,(),,(221311v x v v v v K =， Cap 1K =10+6+9=25。 图11-8 取 {}4212,,,v v v x S =， {}),(),,(),,(5254312v v v v v v K =， Cap 2K =10+6+13=29。 取 {}54213,,,,v v v v x S =， {}),(),,(5313y v v v K =， Cap 3K =10+10=20。 可见，若把割K 的边全从G 中移去，G －K 不一定分离成两部份（如例5中，3K G -仍为一个连通图），但是它一定把G 的全部自源x 到汇y 的路断开，也就是说此时流不能在G 上发生。故从直观上不难理解，G 的任一流f 的流值Val f 不能超过任一割的容量。 二、最大流与最小割 若?f 为满足下列条件的流： Val ?f ={}的一个流 为G f Valf max ， （11-5）
则称?f 为G 的最大流。 若?K 为满足下列条件的割。 Cap ?K ={}的一个割 为G K K Cap min ， （11-6） 则称?K 为G 的最小割。 例1 这个运输问题，就是一个在图11-6中求x 至y 的最大流问题。对此，我们不难建立线性规划模型来求出最优解。但由于网络模型结构的特殊性，我们可以建立有效的求最大流的算法，且求出的最优解是一个整数解。 定理1 对于G 中任一流f 和任一割),(S S K =，有 Val )()(s f S f f -+-= 其中，∑∈+= ),()()(S S e e f S f ，∑∈-=),()()(S S e e f S f 例如，在图11-7中，取{}11,,v x x S =，则 {}),(),,(),,(),,(),,(),(221412121x x x x v v v v v x S S = {}),(),(12v x S S = 4815510315)(=++++=+S f 8)(=-S f 可见，Val )()(40S f S f f -+-== 定理1说明，通过G 的任一横截面的净流值都为Val f ，亦即Val f 为任一横截面的输出量与输入量的代数和。 若f 为G 上一个流，对任E e ∈，若)()(e C e f =，称边e 为f 饱和边；若)(e f ＜)(e C ，称边e 为f 不饱和边；若)(e f ＞0，称边e 为f 正边；若)(e f =0，称e 为f 零边。 定理2 对于G 上任一流f 和任一割),(S S K =，有 1．Val f ≤Cap K ； 2．Val f =Cap K 的充要条件为：任),(S S e ∈，边e 为f 饱和边；任),(S S e ∈，边e 为f 零边。 证 1．∑∈+= ),()()(S S e e f S f ≤∑∈=K e CapK e C )( 又 )(S f -≥0，
第七章网络安全 7-01 计算机网络都面临哪几种威胁？主动攻击和被动攻击的区别是什么？对于计算机网 络的安全措施都有哪些？ 答：计算机网络面临以下的四种威胁：截获（），中断()，篡改(),伪造（）。 网络安全的威胁可以分为两大类：即被动攻击和主动攻击。 主动攻击是指攻击者对某个连接中通过的进行各种处理。如有选择地更改、删除、 延迟这些。甚至还可将合成的或伪造的送入到一个连接中去。主动攻击又可进一步 划分为三种，即更改报文流；拒绝报文服务；伪造连接初始化。被动攻击是指观察和分析某一个协议数据单元而不干扰信息流。即使这些数据对 攻击者来说是不易理解的，它也可通过观察的协议控制信息部分，了解正在通信的协议 实体的地址和身份，研究的长度和传输的频度，以便了解所交换的数据的性质。这种被 动攻击又称为通信量分析。 还有一种特殊的主动攻击就是恶意程序的攻击。恶意程序种类繁多，对网络安全威胁 较大的主要有以下几种：计算机病毒；计算机蠕虫；特洛伊木马；
逻辑炸弹。 对付被动攻击可采用各种数据加密动技术，而对付主动攻击，则需加密技术与适当的 鉴别技术结合。 7-02 试解释以下名词：（1）重放攻击；（2）拒绝服务；（3）访问控制；（4）流量分析； （5）恶意程序。 答：（1）重放攻击：所谓重放攻击（）就是攻击者发送一个目的主机已接收 过的包，来达到欺骗系统的目的，主要用于身份认证过程。（2）拒绝服务：( )指攻击者向因特网上的服务器不停地发送大量 分组，使因特网或服务器无法提供正常服务。 （3）访问控制：（）也叫做存取控制或接入控制。必须对接入网络的权限 加以控制，并规定每个用户的接入权限。 （4）流量分析：通过观察的协议控制信息部分，了解正在通信的协议实体的地址和 身份，研究的长度和传输的频度，以便了解所交换的数据的某种性质。这种被动攻击又 称为流量分析（）。 （5）恶意程序：恶意程序（）通常是指带有攻击意图所编写的
第七章图与网络分析 一、单项选择题 1．关于可行流，以下叙述不正确的是（） A.可行流的流量大于零而小于容量限制条件 B．在网络的任一中间点，可行流满足流人量=流出量 C．各条有向边上的流量均为零的流是一个可行流 D．可行流的流量小于或等于容量限制条件而大于或等于零 2．关于最小树，以下叙述（）正确。 A.最小树是一个网络中连通所有点而边数最少的图 B．最小树是一个网络中连通所有的点，而权数最少的图 C．一个网络中的最大权边必不包含在其最小树内 D．一个网络的最小树一般是唯一的。 3．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（） A. 边缘结点 B.未接结点 C.已接结点 D.最重要结点 4.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（） A.连接的总长度最大 B.连接的总长度最小 C.连接的总长度为0 D.计算总长度5．最小树问题就是在网络图中，找出若干条边，连接（） A.相邻结点 B.头尾结点 C.部分结点 D.所有结点 6．任一树中的边数和它的点数之间的关系是（） A.边数等于点数减1 B.边数等于点数加1 C.点数等于边数减1 D.点数等于边数加1 7．最大流问题中，对于一个可行流，V i V j有向边上的流量f ij必须满足的条件之一是（） A.0≤f ij≥c ij B.0≥f ij≤c ij C. 0≤f ij≤c ij D. 0≥f ij≥c ij 8.一个连通图中的最小树可能不唯一，其权（） A.是唯一确定的 B.可能不唯一 C.可能不存在 D.一定有多个 二、多项选择题 1.关于图论中图的概念，以下叙述正确的的（） A.图中的边可以是有向边，也可以是无向边 B.图中的各条边上可以标注权 C.结点数等于边数的连通图必含圈 D.结点数等于边数的图必连通 E.图中的边只能是有向边 2.关于最短路，以下叙述不正确的有（） A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的 B．从起点出发到终点的最短路是唯一的 C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上 E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上 3.关于增广链，以下叙述正确的有（） A．增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致 B．增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致 C．增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边 D．增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边 E．增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边4.在下图中，根据（a）生成的支撑树有（）
运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 n n x C x C x C Z ++=211m i n ????? ?? ??=≥≥+++≥+++≥+++??) ,,2,1(0, ,, 22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n 或更简洁地表为 ∑== n j j j x C Z 1 m i n ??? ??? ?==≥≥??∑=),,2,1,,2,1(01 n j m i x b x a t s j n j i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 n n x C x C x C Z +++= 2211m a x
第二节欧拉图和哈密尔顿回路 一、欧拉图 欧拉（Euler）在1736年发表的关于图论方面的第一篇论文，解决了一个著名问题，称为哥尼斯堡七桥问题，从而使他成为图论的创始人。问题是这样的：十八世纪的德国有座哥尼斯堡城，在流贯全城的普格尔河两岩和河中两个岛之间架设了七座桥，如图6.10（a）所示。当时那里的居民热衷于这样一个游戏，即一个散步者能否从任一陆地出发，走过每座桥一次且仅走过一次，最后回到原地。问题乍看起来很简单，但当时谁也不明白为什么没有人能够成功。 为了弄清这个问题，欧拉将每一块陆地用一顶点表示，每一座桥用连接相应的两个顶点的连线（即边）来代替，从而得到一个“图”（图 6.10（b））。这个“图”使问题变得简洁明了。直观上不难发现，为了能回到原来的陆地，要求与每个顶点（陆地）相关联的边数是偶数，这样才能保证从一条边出去，从另一条边回来。由于在图6.10（b）中，与四个顶点相连的边数都是奇数，因而不可能 自任一顶点出发过每条边一次且仅一次而回到原地。 （a）图6.10（b）欧拉并不限于处理这个特殊事例，他推广了这个问题，提出并证明了下述定理。 定义1 在连通无向图G中，若存在经过每条边恰好一次的一个圈或一条链，就称此圈或链为欧拉圈或欧拉链。或图G含一条欧拉圈，则称它为欧拉图。 显然，欧拉圈或欧拉链都可“一笔画出”；反之，若一个图能一笔画出，则它必然是欧拉圈或欧拉链。 定理1连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。 事实上，若G是欧拉图，C是其欧拉圈，则由定义，C包含G的所有边，由于图连通，故亦包含所有顶点。C是任一中间顶点每出现一次，必与两条不同的边相关联，另因C的起点也是终点，故所有顶点都是偶次顶点。 定理2 连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。 上述定理提供了判断一笔画问题的准则：若连通无向图G无奇次顶点，则可由任一点起一笔画成并回到起点；若有两个奇次顶点，则由一奇次顶点起到另一奇次顶点终可一笔画成。为能将一个图一笔画下去，当去掉已画出部分时，乘下的部分不应成为不连通图。 二、哈密尔顿回路 1859年英国数学家哈密尔顿（Hamilton）提出了一种名为周游世界的游戏。
习题六图与网络分析习题及参考答案 .1 十名学生参加六门课程的考试。由于选修内容不同，考试门数也不一样。下表给出了每个学生应参加考试的课程（打⊙的）： 学生考试课程 A B C D E F 1 ⊙⊙⊙ 2 ⊙⊙ 3 ⊙⊙ 4⊙⊙⊙ 5⊙⊙⊙ 6 ⊙⊙ 7⊙⊙⊙ 8 ⊙⊙ 9 ⊙⊙⊙ 10⊙⊙⊙ 规定考试在三天内结束，每天上下午各安排一门。学生希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。 参考答案 把同一个研究生参加的考试课程用边连接，得图如下。由图看出，课程A只能同E排在一天，B同C排在一天，D同F在一天。再据题意，考试日程表只能是下表： B E 上午下午 第一天 A E A F 第二天 C B 第三天 D F D C 2 求下图的最小生成树和最大生成树：
V6 3 需 参考答案 将每小块稻田及水源地各用一个点表示，连接这些点的树图的边数即为至少要挖开的堤埂数。（至少挖开11条） 4. 请用标号法求下图所示的最短路问题，弧上数字为距离：
参考答案 路线为1－2－4－6，距离为9个单位 5 用Dijkstra标号法求下图中始点到各顶点的最短路，弧上数字为距离： v3 3 v5 1 5 4 v1 2 4 v2 2 v4 参考答案 1－2，3，4，5最短路：3*,1*,5*,4* 6最短路问题：某公司使用一种设备，此设备在一定年限内随着时间的推移逐渐损坏。每年购买价格和不同年限的维修使用费如下表所示。假定公司在第一年开始时必须购买一台此设备，请建立此问题的网络图，确定设备更新方案，使维修费和新设备购置费的总数最小。说明解决思路和方法，不必求解。 年份 1 2 3 4 5 价格20 21 23 24 26 使用年限0－1 1－2 2－3 3－4 4－5 费用8 13 19 23 30 参考答案 弧（i，j）的费用或“长度”等于j－i年里的设备维修费加上第i年购买的新设备的价格。例如，弧（1，4）的费用为（8＋13＋19）＋20＝60
计算机网络课后题答案第七章 第七章网络安全 7-01 计算机网络都面临哪几种威胁？主动攻击和被动攻击的区别是什么？对于计算机网 络的安全措施都有哪些？ 答：计算机网络面临以下的四种威胁：截获( interception )，中断 (interruption) ，篡改 (modification), 伪造( fabrication )。 网络安全的威胁可以分为两大类：即被动攻击和主 动攻击。 主动攻击是指攻击者对某个连接中通过的 PDU 进行各种处理。如有选择地更改、 删除、延迟这些PDU 。甚至还可将合成的或伪造的 PDU 送入到一个连接中去。主动攻击 又可进一步划分为三种，即更改报文流；拒绝报文服务；伪造连接初始化。 被动攻击是指观察和分析某一个协议数据单元 PDU 而不干扰信息流。即使这些数据对攻 击者来说是不易理解的，它也可通过观察 PDU 的协议控制信息部分，了解正在通信的协 议实体的地址和身份，研究 PDU 的长度和传输的频度，以便了解所交换的数据的性质。 这种被动攻击又称为通信量分析。 还有一种特殊的主动攻击就是恶意程序的攻击。恶意程序种类繁多，对网络安全威胁较大 的主要有以下几种：计算机病毒；计算机蠕虫；特洛伊木马； 对付被动攻击可采用各种数据加密动技术，而对付主动攻击， 技术结合。 7-02 试解释以下名词：( 1)重放攻击；( 2)拒绝服务； 析；( 5) 恶意程序。 ( 1)重放攻击：所谓重放攻击( replay attack )就是攻击者发送一个目的主机已接收过 的包，来达到欺骗系统的目的，主要用于身份认证过程。 (2)拒绝服务：DoS(De nial of Service)指攻击者向因特网上的服务器不停地发送大量分 组，使因特网或服务器无法提供正常服务。 (3)访问控制：(access control )也叫做存取控制或接入控制。必须对接入网络的权限 加以控制，并规定每个用户的接入权限。 ( 4)流量分析：通过观察 PDU 的协议控制信息部分，了解正在通信的协议实体的地址和 身份，研究 PDU 的长度和传输的频度，以便了解所交换的数据的某种性质。这种被动攻 击又称为流量分析( traffic analysis )。 5)恶意程序：恶意程序( rogue program )通常是指带有攻击意图所编写的一段程序。 7-03 为什么说，计算机网络的安全不仅仅局限于保密性？试举例说明，仅具有保密性的 计算机网络不一定是安全的。 逻辑炸弹。 则需加密技术与适当的鉴别 3)访问控制；( 4)流量分
第5章习题参考答案 1．请在括号填入适当答案。在CPU中： (1)保存当前正在执行的指令的寄存器是（ IR ）； (2)保存当前正在执行的指令地址的寄存器是（ AR ） (3)算术逻辑运算结果通常放在（ DR ）和（通用寄存器）。 2．参见图5.15的数据通路。画出存数指令“STO Rl，(R2)”的指令周期流程图，其含义是将寄存器Rl的容传送至(R2)为地址的主存单元中。标出各微操作信号序列。 解： STO R1, (R2)的指令流程图及微操作信号序列如下：
STO R1, (R2) R/W=R DR O, G, IR i R2O, G, AR i R1O, G, DR i R/W=W 3．参见图5.15的数据通路，画出取数指令“LAD (R3)，R0”的指令周期流程图，其含义是将(R3)为地址主存单元的容取至寄存器R2中，标出各微操作控制信号序列。 解： LAD R3, (R0)的指令流程图及为操作信号序列如下：
PC O , G, AR i R/W=R DR O , G, IR i R 3O , G, AR i DR O , G, R 0i R/W=R LAD (R3), R0 4．假设主脉冲源频率为10MHz ，要求产生5个等间隔的节拍脉冲，试画出时序产生器的逻辑图。 解：
5．如果在一个CPU 周期中要产生3个节拍脉冲；T l ＝200ns ，T 2=400ns ，T 3=200ns ，试画出时序产生器逻辑图。 解：取节拍脉冲T l 、T 2、T 3的宽度为时钟周期或者是时钟周期的倍数即可。所以取时钟源提供的时钟周期为200ns ，即，其频率为5MHz.；由于要输出3个节拍脉冲信号，而T 3的宽度为2个时钟周期，也就是一个节拍电位的时间是4个时钟周期，所以除了C 4外，还需要3个触发器——C l 、C 2、C 3；并令 211C C T *=；321C C T *=；313C C T =，由此可画出逻辑电路图如下：