1、第六章 图与网络图一、选择1. 在图中用 V表示点,用 E表示边,如果有两个图 G1=V1,E1和图 G2=V2,E2,若有 V1 V2 ,E1 E2,则称 G1 是 G2的一个(D)A 偶图 B 部分图 C 完全图 D 子图2. 3. 在树图中,顶点有 个,边有 条,那么顶点和边的数量关系是(B )veA、 = B、 -1 C、 -1evve4. 在图中用 V表示点,用 E表示边,如果有两个图 G1=V1,E1和图 G2=V2,E2,若有 V1= V2 ,E1 E2,则称 G1 是 G2的一个( A )A 部分图 B 子图 C 二分图5.完全偶图中 V1含 m个顶点,V 2含有 n个顶点,则
2、其边数共( C)条。A m+n B m-n C mn D mn6. 任何树中必存在次为( A)的点A 1 B 2 C 3 D47含有 n个顶点的完全图,其边数有( B )条。A n B C n(n-1) D n-1)(28.具有 n个顶点的树的边数恰好为(A )条。A n-1条 B n 条 C D n(n-1)1(n9.在网络图中 s t的最大流量( C )它的最小割集的容量。A 大于 B 小于 C 等于 D 无关10. 构成最大流问题的条件之一是(B )A、网络有一个始点 B、网络有一个始点 和一个终点 vs vstC、网络有一个终点 D 无要求t11. 下图中(C )是完全二分图A BC
3、D 12.下面(D)是最短路问题A 课程排序问题 B 生产计划问题 C 人力资源问题 D 选址问题13. 求网络图中任意两点之间的最短距离的方法是(C )A 求最小部分树 B 矩阵算法 C Dijkstra 算法 D 破圈法14.下面 (A)是矩阵算法求最短路问题A 小学生选校址问题 B 课程排序问题 C 生产计划问题 D 人力资源问题 15.下面(A)是最大流问题。 A 桥梁问题 B 设施布局问题 C 生产计划问题 D 以上都不是16.二、填空1. 在图论中,称 (无圈的) 连通图为树。2. 树是无圈连通图中边数最多的,在树图上只要任意再加上一条边,必定会出现(圈) 。3.在图中一般用点表示
4、(研究的对象) ,用边表示这些(对象的联系) 。4.如果给图中的点和边赋以具体的含义和权数,把这样的图称为(网络图)5. .图 G 可以定义为点和边的集合,记作( G=V,E )6.在图中, (链 )是点可重复,边不可重复的。7.在图中, (路)是点与边都不可以重复的。8.如果边 e 的两个端点相重,称该边为( 环)9.对无环、无多重边的图称为(简单图)10.与某一个点 相关联的边的数目称为点 的(次)vi vi11.对起点与终点相重合的链称为(圈) 。12.若在一个图中,如果每一对顶点之间至少存在一条链,称这样的图为(连通图) 。13. 若在一个图中,如果每一对顶点之间至少存在一条(链) ,
5、称这样的图为连通图。14.一个简单图中若任意两点之间均有边相连,称这样的图为(完全图) 。15. 一个(简单图)中若任意两点之间均有边相连,称这样的图为完全图。16.对要研究的问题确定具体对象及这些对象间的性质联系,这就要对研究的问题建立(图的模型)17.(树)是无圈的连通图。18.在树图中,称次为 1 的点为(悬挂点)19.如果 G1 是 G2 的部分图,又是树图,则称 G1 是 G2 的(部分树)20.树枝总长最小的部分树,称为(最小支撑树) 。21.把图的所有点分成 V 和 两个集合,则两个集合之间连线的最短边一定包含在(最小部分树)内。22. (最短路问题)是指从给定的网络图中找出任意
6、两点之间距离最短(权值和最小)的一条路。23.矩阵算法中 D(k) 给出网络中任意两点直接到达,经过一个、两个、,到(2 k-1)个中间点时比较得到的最短距离。24.设网络图有 p 个点,则一般计算到不超过 D(k) ,k 的值按公式( ) ,即计算结束。25. 对图中每条边规定指向的图称为(有向图)26. 有向图的边称为(弧),记作(v i , vj),27. 弧(v i , vj)的最大通过能力,称为该弧的(容量) ,记为 c(vi , vj) ,或简记为 cij 。28. (流)是指加在网络各条弧上的一组负载量,对加在弧(v i , vj)上的负载量记作 f (vi , vj) ,或简记
7、作 fij 29. (割)是指将容量网络中的发点和收点分割开,并使 st 的流中断的一组弧的集合。30. (割的容量)是组成它的集合中各弧容量之和。31. 如果在网络的发点和收点之间能找到一条链,在这条链上所有指向为 st 的弧(称前向弧,记作 +) ,存在 f 0(非零),这样的链称(增广链) 。32. 求网络最大流的方法是(标号算法)33.34.求网络的最大流,是指满足(容量限制条件)和(中间点平衡)的条件下,使值达到最大。)(fv三、判断1.图论中的图不仅反映了研究对象之间的关系,而且是真实图形的写照,因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。 (不正确)2.在任一
8、图 G 中,当点集 V 确定后,树图是 G 中边数最少的连通图。 (正确)3.如图中某点 有若干个相邻点,与其距离最远的相邻点为 ,则边 i,j必不包含在最vi vj小支撑树内。 (正确)kk2lg)1(4.如图中从 至各点均有唯一的最短路,则连接 至其他各点的最短路在去掉重复部分后,v1 v1恰好构成该图的最小支撑树。 (正确)5. Dijkstra算法提供了从网络图中某一点到其他点的最短距离。 (正确 )6. 部分图不是子图,子图也不一定是部分图。 (不正确)7.树图的任意两个点之间有一条且仅有一条唯一通路。 (正确)8.一些重要的网络不能按数的结构设计。 (正确)9. 一个图的最小部分树
9、不唯一。 (正确)10. 不同解法得到的最小部分树所包含的边虽然可能不相同,但是,每个最小部分树中所有边权的总和一定都是相同的,即都达到了最小。 (正确)11. D(k) 中的元素给出了各点间的最短距离,但是并没有给出具体是经过了哪些中间点才得到的这个最短距离,如果要知道中间点具体是什么,需要在计算过程中进行记录。 (正确)12.零流不是可行流。 (不正确)13. 在网络中 st 的最大流量等于它的最小割集的容量。 (正确)14. 标号算法其本质是判断是否存在增广链,并找出增广链。 (正确)15. 求最小费用流时,一方面通过增广链来调整流量,另一方面要找出每一步费用最小的增广链。是最大流和最短
10、路问题的综合求解。 (正确)四名词解释1.环:如果边 e 的两个端点相重,称该边为环。2.多重边 如果两个点之间的边多于一条,称为具有多重边。3.简单图 无环,无多重边的图称为简单图。4.次 与某一个点 iv相关联的边的数目称为点 iv的次(也叫做度或线度) 。5.奇点 次为奇数的点称作奇点。6.偶点 次数为偶数的点称作偶点。7.孤立点 次数为 0 的点称作孤立点。8.链 有些点和边的交替序列 = kveve,10,若其中各边ke,21互不相同,且任意 1,tiv和 it( k2)均相邻,称 为链。9.路 如果链中所有的顶点 kv,10也不相同,这样的链称为路。10.圈 对起点与终点相重合的链
11、称作圈。11.回路 起点与终点重合的路称作回路。12.连通图 若在一个图中,如果每一对顶点之间至少存在一条链,称这样的图为连通图,否则称该图是不连通的。13.完全图 一个简单图中若任意两点之间均有边相连,称这样的图为完全图。含有 n 个顶点的完全图,其边数有条 )1(2nCn。14.偶图 如果图的顶点能分成两 个互不相交的非空集合 1V和 2,使在同一集合中任意两个顶点均不相邻,称这样的图为偶图(也称二分图) 。15.完全偶图:如果偶图的顶点集合 1V, 2之间的每一对不同顶点都有一条边相连,称这样的图为完全偶图。完全偶图中 含 m 个顶点, 含 n 个顶点,则其边数共 mn 条。16.网络图
12、:如果给图中的点和边赋以具体的含义和权数,如距离、费用、容量等,把这样的图称为网络图。17.端点:若有边 e 可表示为 ,称 和 是边 e 的端点。vjiij18.关联边:若有边 e 可表示为 ,称边 e 为点 或 的关联边。ji vij19.点相邻:若点 , 与同一条边关联,称点 和 相邻。vij ij20.边相邻:若边 和 具有公共的端点,称边 和 相邻。ij ij21.子图:图 和图 ,如果有 和 ,称 是EVG11,22,V21E21G1的一个子图。222.部分图:如果有 和 ,称 是 的一个部分图。2121G1223.图的模型:对要研究的问题确定具体对象及这些对象间的性质联系,并用图
13、的形式表示出来,这就是对研究的问题建立图的模型。24.树图:是无圈的连通图。这类图与大自然中数的特征相似,因而得名树图。25.部分树:如果 是 的部分图,又是树图,则称 是 的部分树。12 1226.树枝:树图的各条边称为树枝27.最小部分树:假定各边均有权重,一般图 含有多个部分树,其中树枝总长最小的部2分树,称为该图的最小部分树。28.弧:有向图上的连线是有规定指向的,称作弧。记作 表明方向是从 点指向),(vji i点。vj29.弧的容量:对网络上的每条弧 都给出一个最大的通过能力,称为该弧的容量,),(vji简写 cij30.网络的最大流:网络中从发点到收点之间允许通过的最大流量。31
14、.流:加在网络各条弧上的一组负载量。记 fij32.零流:若网络上所有的 =0,这个流称为零流。fij33.割:指将容量网络中的发点和收点分割开,并使 的流中断的一组弧的集合。ts34割的容量:是组成它的集合中的各弧的容量之和,用 表示。),(Vc35.增广链:如果在网络的发点和收点之间能找到一条链,在这条链上所有指向为 st 的弧(称前向弧,记作 +) ,存在 f 0(非零),这样的链称增广链。36.悬挂点:次为 1 的点为悬挂点。37.悬挂边:与悬挂点关联的边称为悬挂边。四、简答2. 2. 一些重要的网络不能按数的结构设计,这是为什么。答:由于数图是无圈的连通图,即数图的任意两个点之间有一
15、条且仅有一条唯一通路。因此数图是最脆弱的连通图,只要从树图中取走任一条边,图就不连通,因此一些重要的网络不能按数的结构设计。3.避圈法一在求最小部分树的步骤:1. 从图中任选一点 vi ,让 vi V ,图中其余点均包含在 中;V2. 从 V 与 的连线中找出最小边,这条边一定包含在最小部分树中,不妨设这条边为vi , vj将其加粗,标记为最小部分树中的边。3. 令 VvjV, - vj ;V4.重复 2、3 两步,一直到图中所有点均包含在 V 中4.破圈法一求最小部分树的步骤1. 从图 N 中任取一回路,去掉这个回路中边权最大的边,得到原图的一个子图 N1。2. 从剩余的子图中任找一回路,同
16、样去掉回路中边权最大的一条边,得一新的子图;3. 重复第 2 步,直到图中不再含有回路为止。5Dijkstra 算法的基本思路答:如果 v1 v2 v3 v4 是 v1 v4 的最短路径,则 v1 v2 v3 一定是 v1 v3 的最短路径。 v2 v3 v4 一定是 v2 v4 的最短路径。6可行流需要满足的条件(1) 容量限制条件: 对所有弧有 ),(),(0vjijicf(2) 中间点平衡条件: ,0, tsfvjiji 7.求最小费用流步骤第一步:从零流 开始, 是可行流,也是相应的流量为零时费用最小的;f00第二步:对可行流 构造加权网络 W( ) ,方法是kfk1.对 0 )fk1
17、k第四步 重复第 2,3 两步,一直到在网络 W( 找不到增广链(也即找不到最短fmk路)时, 即为要寻找的最小费用最大流fmk8.树的性质说明什么?1)树是无圈连通图中边数最多的,树中只要任意再加一条边,必出现圈。2)树中任意两点之间有且只有一条通路,从树中任意删掉一条边,就不再连通。9.避圈法二在求最小部分树的步骤:1)在所有各边中找到边权最小的一条,将其作为最小部分树中的第一边;在剩余的边中,仍然找到边权最小的作为最小部分树的第二条边;2)在剩余的边中,找到边权最小的边,查看其是否与前面的边形成圈,如果没有,则在最小部分树中添加该边,如果形成了圈,则不再考虑该边;3)重复进行第二步,直到
18、找到第 n-1 条边为止。 (因为有 n 个顶点的树中一定有 n-1 条边)10. 破圈法二求最小部分树的步骤1)从剩余图中找到边权最大的一条边,如果将其删除后图仍然是连通的,则删除此边,否则不再考虑此边;2)重复上述步骤,直到剩余边数为 n-1 为止。11.最小部分树的求解注意事项1)一个图的最小部分树不唯一,如题中用几种解法得到的结果都是相同的,是特殊情况;2)不同解法得到的最小部分树所包含的边虽然可能不相同,但是,每个最小部分树中所有边权的总和一定都是相同的,即都达到了最小12. Dijkstra 算法步骤:1)对起始点 ,因 ,将 标注在 旁的小方框内,表示 点已标号;s0sLss2)
19、从点 出发,找出与 相邻的点中距离最小的一个,设为 ,将 的值标注rsrsrdL在 旁的小方框内,表明点 也已标号;rr3)从已标号的点出发,找出与这些点相邻的所有未标号点 ,若有p,则对 点标号,并将 的值标注在 点旁的小方框内;rpspsspdLL,min sL4)重复第 3步,直到 点得到标号为止。t13. 求网络最大流的标号算法的步骤第一步:首先给发点 标号 。s)(,0s第二步:列出与已标号点相邻的所有未标号点1)考虑从标号点 出发的弧 ,如果有 ,不给点 标号;若 ,则对 iji,ijijcfjijijcfj标号,记为 ,其中 ;)(,j )(),mn)(ijijf2)考虑所有指向
20、标号点 的弧 ,如果有 ,对 不标号, 若 ,则对 点iih,0hi 0hif标号,记为 ,其中 ;)(,iif),()(3)如果某未标号点 有两个以上相邻的标号点,可按 (1),(2)中所述规则分别计算出k的值,并取其中的最大的一个标记。)(k第三步:重复第二步第四步:修改流量。设原图中可行流为 ,令f所 有 非 增 广 链 上 的 弧对 增 广 链 上 所 有 后 向 弧对 增 广 链 上 所 有 前 向 弧,)(,ftf这样得到网络上的一个新的可行流 。 f第五步:抹掉图上所有标号,重复第一到第四步。14. 求最小费用流的步骤: 第一步:从零流 开始, 是可行流,也是相应的流量为零时费用
21、最小的;0f0f第二步:对可行流 构造加权网络 ,方法是k)(kfW1)对 的当其为正向弧时,通过单位流的费用为 ,为反向弧时,相应费用ijijcf ijb,故在 和 点间分别给出弧 和 ,其权数分别为 和 ;ijjibji,i,ijjib2)对 的弧 ,因该弧流量已饱和,在增广链中只能作为反向弧,故在 中ijijcfj, )(kfW只画出弧 ,其权数值为 ;,ijb3)对 的弧 ,在增广链中该弧只能为正向弧,故在 中只给出弧 其权0ijfji )(kfji,数值为 。ijb第三步 在加权网络 中,寻找费用最小的增广链,也即求从 的最短路,并将)(kfWts该增广链上流量调理至允许的最大值,得
22、到一个新的流量 。kf1第四步 重复第 2,3 两步,一直到在网络 找不到增广链(也即找不到最短路)时,)(mkf即为要寻找的最小费用最大流。mkf15.标号法求最大流时,出现的两个结果是什么。1)标号过程中断, 得不到标号,说明该网络中不存在增广链,给定流量即为最大流量。记t已标号点集为 ,未标号点集为 , 为网络的最小割;VV,2) 得到标号,这时可用反向追踪法在网络中找到一条从 的有标号点以及相应的弧连t ts接而成的增长链。16.树的性质性质 1. 任何树中必存在次为 1 的点。性质 2. 具有 n 个顶点的树恰有(n-1)条边。性质 3. 任何具有 n 个点、(n - 1)条边连通图
23、是树。17.最小部分树的定理及推论定理 1. 图中任一个点 i ,若 j 是与 i 相邻点中距离最近的,则边 i , j 一定包含在该图的最小部分树中。推论. 把图的所有点分成 V 和 两个集合,则两集合之间连线的最短边一定包含在最小部分树内。五、计算1.求最小部分树(第一题用破圈法,第二题用避圈法)(1) (7 分) (2) (7 分)275413534147213567824153654334答(a)最小部分数为 15 (7 分) 513312(b)最小部分树为 18 (7 分)132133322. 已知有 6个村子,相互间道路的距离如图所示,拟合建一所小学,已知 A处有学生 50人,B 处 40人,C 处有 60人,D 处有 20人,E 处有 70人,F 处有 90人,问小学应建在哪一个村子,使学生上学最方便(走的总路程最短)