资源描述：
《运筹学教程 第2版 教学课件 作者 邱菀华 冯允成 图论作业答案_第7章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章作业eEdHGCBAabcfgDFhi7.1.构造一个图，其顶点集合是你获得学位所必须通过的那些课程。如果课程x是课程y的先修课程，则从顶点x至顶点y画一条弧。结合这个问题来解释以下名词：路、链、圈、回路、连通子图。链：有向图中，任意两节点之间可以构成一条由有限个节点与弧组成的连续序列，在序列中节点与弧交替出现，称这样的一个序列为一条链。A,a,B,d,E,e,C.圈：若链的两端点为同一节点时，则该链称为圈。B,b,C,e,E,d,B路：在一条链中，若在节点和弧的序列中，每一条弧的方向与序列的走向
2、一致，则称该链为一条路。F,h,D,f,E,g,H.回路：类似于圈，我们可以定义两个端点（起始点和终结点）重合于同一节点的路为回路。E,i,F,h,D,f,E.连通子图：若图G的子图g是连通的，则称图g为图G的连通子图。CBHDE7.2.证明：顶点为n的简单图，其最大边数为。若它的边数大于，则必连通。证明：假设图G顶点为n，其边数大于，非连通。由于非连通图可分为几个连通图，设G分为连通图和，图顶点为a，则有以下条件成立：图和的最大边数之和==当取得最大值时，为最大。，因此，当=1时，取得最大值，但是a<
3、n,因此，可取a=n-1.由上可知，与条件矛盾，因此在图G可分为两个连通图时，图G是连通图。当图G可分为m（m>2）个连通图时，最大边数小于，与条件矛盾。综上所述，命题成立。7.3.证明：如果树T中顶点的最大次不小于k，，则T中至少有k个悬挂点。证：树中不含圈。从任一点出发，选择任意两条路径，不相交，否则与树中不含圈矛盾。因此，由次为k的顶点出发，最终形成k个悬挂点。7.4构造图7-63中的最小生成树。若要求最小生成树包含弧（a，b）和（c，d），又如何构造？图7-63解：先将图中边按大小顺序由小至大排
4、列：(b,d)=-3(f,e)=(c,d)=-2(e,d)=0(e,c)=1(b,f)=2(c,a)=3(a,b)=(a,f)=4(c,b)=(f,b)=6(f,d)=7取定=(b,d)=(f,e)=(c,d)=(e,d)=(c,a)得到图的一棵最小生成树，它的权是-4.acdefb最小生成树是不可能包括弧（a,b）的。7.5试求图7-64中v1至v7的最短路，并建立该问题的整数规划模型。图7-64解：求解过程如下表所示问题7.5的求解过程节点步iv1v2v3v4v5v6v7先驱点00*¥¥¥¥¥¥10
5、98*¥¥¥¥v1209*816¥15¥v130981110*15¥v2409811*101513v2509811101413*v5最短路径为（v1，v2），（v2，v5），（v5，v7），路径长13.7.6求图7-65网络中，节点s到t的最短路径及其长度。图7-65解：初始条件为：=0,=1,=2,===第一轮迭：=min{+,+,+,+,+,+}=0;类似可得：=1，=2，=-1，=-1。全部计算过程可用下表表示：ji012000003-1-211110-3222220-2-2-1-1-101-1-
6、3-30-3-3空格为+到的最短路径为（，），（，），（，），路径长-3.7.7.求图7-66中顶点1到其它所有顶点的最短路。图7-66解：从点5到点6有两条路径，权分别为1和2，可省略权为2的路径。初始条件为：=0，=-1，=+，=2，=+，=+第一轮迭代：=min{+,+,+,+,+,+}=0类似可得：=-1，=3，=2，=5，=+全部计算过程可用下表表示。ji0-1200000204-1-1-1-1-130-2333310322222201552210111迭代到第五步时，发现=(j=1,2,…,
7、6)则停止。表中最后一列数字分别为到各点的最短路长。到得最短路为：到得最短路为：，到得最短路为：，，到得最短路为：，到得最短路为：，，，，到得最短路为：，，，7.8.某公司承担一个项目，计划四年完成。现需购置一台专用设备，该设备售价1500万元，正常使用期为一年。一年过后可有两种选择，一是通过维修继续使用旧设备；二是再购买一台新设备，并将老设备折价售出。每年末旧设备的折扣售价与用于次年继续使用所需的维修费用如表7-10所示。试利用图论方法建立求解最佳购买计划的模型（使总费用最小），并利用标号法求出最佳计
8、划与相应的费用。表7-10设备的折扣售价与维修费用使用时间（年）折扣售价（万元）维修费用（万元）1750300250060032008754251000解：设Vi：第i年初（i=1,2……5）；(Vi,Vj)：第i年初购进设备，一直使用到第j年；Wij：第i年初购进设备，一直使用到第j年的总费用V5V4V3V2V14250307519001900那么得到下图：105010501050105019003075原问题转化为求V1到V5的的最短路
