第6章 图与网络图.doc

第六章 图与网络图一、选择1. 在图中用V表示点，用E表示边，如果有两个图G1=V1,E1和图G2=V2,E2,若有V1 V2 ,E1 E2，则称G1 是G2的一个（D）A 偶图 B 部分图 C 完全图 D子图2. 3. 在树图中，顶点有个，边有条，那么顶点和边的数量关系是（B ） A、= B、-1 C、-14. 在图中用V表示点，用E表示边，如果有两个图G1=V1,E1和图G2=V2,E2,若有V1= V2 ,E1 E2，则称G1 是G2的一个（A ）A 部分图 B 子图 C 二分图5.完全偶图中V1含m个顶点，V2含有n个顶点，则其边数共（ 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-18.具有n个顶点的树的边数恰好为（A ）条。A n-1条 B n条 C D n(n-1)9.在网络图中st的最大流量（ C ）它的最小割集的容量。A 大于 B 小于C 等于 D 无关10. 构成最大流问题的条件之一是（B ）A、网络有一个始点 B、网络有一个始点和一个终点 C、网络有一个终点 D 无要求11. 下图中（C ）是完全二分图A BC 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.如果给图中的点和边赋以具体的含义和权数，把这样的图称为（网络图）5. .图G可以定义为点和边的集合，记作（G=V,E ）6.在图中，（链 ）是点可重复，边不可重复的。7.在图中，（路）是点与边都不可以重复的。8.如果边e的两个端点相重，称该边为（ 环）9.对无环、无多重边的图称为（简单图）10.与某一个点相关联的边的数目称为点的（次）11.对起点与终点相重合的链称为（圈）。12.若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为（连通图）。13. 若在一个图中，如果每一对顶点之间至少存在一条（链），称这样的图为连通图。14.一个简单图中若任意两点之间均有边相连，称这样的图为（完全图）。15. 一个（简单图）中若任意两点之间均有边相连，称这样的图为完全图。16.对要研究的问题确定具体对象及这些对象间的性质联系，这就要对研究的问题建立（图的模型）17.（树）是无圈的连通图。18.在树图中，称次为1的点为（悬挂点）19.如果G1是G2的部分图，又是树图，则称G1是G2的（部分树）20.树枝总长最小的部分树，称为（最小支撑树）。21.把图的所有点分成V和两个集合，则两个集合之间连线的最短边一定包含在（最小部分树）内。22. (最短路问题)是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。23.矩阵算法中D（k）给出网络中任意两点直接到达，经过一个、两个、，到（2k-1）个中间点时比较得到的最短距离。24.设网络图有p个点，则一般计算到不超过D（k），k的值按公式（ ），即计算结束。25. 对图中每条边规定指向的图称为(有向图)26. 有向图的边称为(弧)，记作(vi , vj)，27. 弧(vi , vj)的最大通过能力，称为该弧的(容量)，记为c(vi , vj) ，或简记为 cij 。28. (流)是指加在网络各条弧上的一组负载量，对加在弧(vi , vj)上的负载量记作 f (vi , vj) ，或简记作 fij 29. （割）是指将容量网络中的发点和收点分割开，并使st 的流中断的一组弧的集合。30. （割的容量）是组成它的集合中各弧容量之和。31. 如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为 st 的弧（称前向弧，记作+），存在f 0(非零)，这样的链称（增广链）。32. 求网络最大流的方法是（标号算法）33.34.求网络的最大流，是指满足（容量限制条件）和（中间点平衡）的条件下，使值达到最大。三、判断1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（不正确）2.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（正确）3.如图中某点有若干个相邻点，与其距离最远的相邻点为，则边 i,j必不包含在最小支撑树内。（正确）4.如图中从至各点均有唯一的最短路，则连接至其他各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树。（正确）5. Dijkstra算法提供了从网络图中某一点到其他点的最短距离。（正确 ）6. 部分图不是子图，子图也不一定是部分图。（不正确）7.树图的任意两个点之间有一条且仅有一条唯一通路。（正确）8.一些重要的网络不能按数的结构设计。（正确）9. 一个图的最小部分树不唯一。（正确）10. 不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。（正确）11. D(k) 中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。（正确）12.零流不是可行流。（不正确）13. 在网络中 st 的最大流量等于它的最小割集的容量。（正确）14. 标号算法其本质是判断是否存在增广链，并找出增广链。（正确）15. 求最小费用流时，一方面通过增广链来调整流量，另一方面要找出每一步费用最小的增广链。是最大流和最短路问题的综合求解。（正确）四名词解释1.环：如果边e的两个端点相重，称该边为环。2.多重边 如果两个点之间的边多于一条，称为具有多重边。3.简单图 无环，无多重边的图称为简单图。4.次 与某一个点相关联的边的数目称为点的次（也叫做度或线度）。5.奇点 次为奇数的点称作奇点。6.偶点 次数为偶数的点称作偶点。7.孤立点 次数为0的点称作孤立点。8.链 有些点和边的交替序列=，若其中各边互不相同，且任意和（）均相邻，称为链。9.路 如果链中所有的顶点也不相同，这样的链称为路。10.圈 对起点与终点相重合的链称作圈。11.回路 起点与终点重合的路称作回路。12.连通图 若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。13.完全图 一个简单图中若任意两点之间均有边相连，称这样的图为完全图。含有n个顶点的完全图，其边数有条。14.偶图 如果图的顶点能分成两个互不相交的非空集合和，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图）。15.完全偶图：如果偶图的顶点集合，之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。完全偶图中含m个顶点，含n个顶点，则其边数共mn条。16.网络图：如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图。17.端点：若有边e可表示为,称和是边e的端点。18.关联边：若有边e可表示为，称边e为点或的关联边。19.点相邻：若点，与同一条边关联，称点和相邻。20.边相邻：若边和具有公共的端点，称边和相邻。21.子图：图和图，如果有和,称是的一个子图。22.部分图：如果有和,称是的一个部分图。23.图的模型：对要研究的问题确定具体对象及这些对象间的性质联系，并用图的形式表示出来，这就是对研究的问题建立图的模型。24.树图：是无圈的连通图。这类图与大自然中数的特征相似，因而得名树图。25.部分树：如果是的部分图，又是树图，则称是的部分树。26.树枝：树图的各条边称为树枝27.最小部分树：假定各边均有权重，一般图含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。28.弧：有向图上的连线是有规定指向的，称作弧。记作表明方向是从点指向点。29.弧的容量：对网络上的每条弧都给出一个最大的通过能力，称为该弧的容量，简写30.网络的最大流：网络中从发点到收点之间允许通过的最大流量。31.流：加在网络各条弧上的一组负载量。记32.零流：若网络上所有的=0，这个流称为零流。33.割：指将容量网络中的发点和收点分割开，并使的流中断的一组弧的集合。34割的容量：是组成它的集合中的各弧的容量之和，用表示。35.增广链：如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为 st 的弧（称前向弧，记作+），存在f 0(非零)，这样的链称增广链。36.悬挂点：次为1的点为悬挂点。37.悬挂边：与悬挂点关联的边称为悬挂边。四、简答2. 2. 一些重要的网络不能按数的结构设计，这是为什么。答：由于数图是无圈的连通图，即数图的任意两个点之间有一条且仅有一条唯一通路。因此数图是最脆弱的连通图，只要从树图中取走任一条边，图就不连通，因此一些重要的网络不能按数的结构设计。3.避圈法一在求最小部分树的步骤：1. 从图中任选一点 vi ，让 vi V ，图中其余点均包含在 中；2. 从 V 与 的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为vi , vj将其加粗，标记为最小部分树中的边。3. 令 VvjV， - vj ；4.重复2、3两步，一直到图中所有点均包含在 V 中4.破圈法一求最小部分树的步骤1. 从图 N 中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图 N1。2. 从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；3. 重复第 2 步，直到图中不再含有回路为止。5Dijkstra 算法的基本思路答：如果 v1 v2 v3 v4 是 v1 v4 的最短路径，则 v1 v2 v3 一定是 v1 v3 的最短路径。 v2 v3 v4 一定是 v2 v4 的最短路径。6可行流需要满足的条件(1) 容量限制条件: 对所有弧有 (2) 中间点平衡条件： 7.求最小费用流步骤第一步：从零流开始，是可行流，也是相应的流量为零时费用最小的；第二步：对可行流构造加权网络W（），方法是1.对0 )第四步 重复第2，3两步，一直到在网络W（ 找不到增广链（也即找不到最短路）时， 即为要寻找的最小费用最大流8.树的性质说明什么？1）树是无圈连通图中边数最多的，树中只要任意再加一条边，必出现圈。2）树中任意两点之间有且只有一条通路，从树中任意删掉一条边，就不再连通。9.避圈法二在求最小部分树的步骤：1）在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；2）在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；3）重复进行第二步，直到找到第 n-1 条边为止。（因为有 n 个顶点的树中一定有 n-1 条边）10. 破圈法二求最小部分树的步骤1）从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；2）重复上述步骤，直到剩余边数为 n-1 为止。11.最小部分树的求解注意事项1）一个图的最小部分树不唯一，如题中用几种解法得到的结果都是相同的，是特殊情况；2）不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小12. Dijkstra 算法步骤：1）对起始点，因 ，将标注在旁的小方框内，表示点已标号；2）从点出发，找出与相邻的点中距离最小的一个，设为，将的值标注在旁的小方框内，表明点也已标号；3）从已标号的点出发，找出与这些点相邻的所有未标号点，若有，则对点标号，并将的值标注在点旁的小方框内；4）重复第3步，直到点得到标号为止。13. 求网络最大流的标号算法的步骤第一步：首先给发点标号。第二步：列出与已标号点相邻的所有未标号点1)考虑从标号点出发的弧，如果有，不给点标号；若，则对 标号，记为，其中；2)考虑所有指向标号点的弧，如果有，对不标号， 若，则对点标号，记为，其中；3)如果某未标号点有两个以上相邻的标号点，可按(1),(2)中所述规则分别计算出的值，并取其中的最大的一个标记。第三步：重复第二步第四步：修改流量。设原图中可行流为，令这样得到网络上的一个新的可行流。 第五步：抹掉图上所有标号，重复第一到第四步。14. 求最小费用流的步骤： 第一步：从零流开始，是可行流，也是相应的流量为零时费用最小的；第二步：对可行流构造加权网络，方法是1)对的当其为正向弧时，通过单位流的费用为，为反向弧时，相应费用，故在和点间分别给出弧和，其权数分别为和；2)对的弧，因该弧流量已饱和，在增广链中只能作为反向弧，故在中只画出弧，其权数值为；3)对的弧，在增广链中该弧只能为正向弧，故在中只给出弧其权数值为。第三步 在加权网络中，寻找费用最小的增广链，也即求从的最短路，并将该增广链上流量调理至允许的最大值，得到一个新的流量。第四步 重复第2，3两步，一直到在网络找不到增广链（也即找不到最短路）时， 即为要寻找的最小费用最大流。15.标号法求最大流时，出现的两个结果是什么。1)标号过程中断，得不到标号，说明该网络中不存在增广链，给定流量即为最大流量。记已标号点集为，未标号点集为，为网络的最小割；2)得到标号，这时可用反向追踪法在网络中找到一条从的有标号点以及相应的弧连接而成的增长链。16.树的性质性质1. 任何树中必存在次为1 的点。性质2. 具有 n 个顶点的树恰有（n-1）条边。性质3. 任何具有n 个点、(n - 1)条边连通图是树。17.最小部分树的定理及推论定理1. 图中任一个点 i ，若 j 是与 i 相邻点中距离最近的，则边 i , j 一定包含在该图的最小部分树中。推论. 把图的所有点分成 V 和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。五、计算1.求最小部分树（第一题用破圈法，第二题用避圈法）（1） （7分） （2）（7分） 答（a）最小部分数为15 （7分） （b）最小部分树为18 （7分）2. 已知有6个村子，相互间道路的距离如图所示，拟合建一所小学，已知A处有学生50人，B处40人，C 处有60人，D处有20人，E处有70人，F处有90人，问小学应建在哪一个村子，使学生上学最方便（走的总路程最短）3. 1. 十名研究生参加六门课程的考试，由于选修的课程不同，考试门数也不一样，如下表给出了每个研究生应参加考试的课程（打号的），规定考试应在三天内结束，每天上下午各安排一门，研究生们提出希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。（15分）考试课程研究生ABCDEF12345678910上午下午第一天AE第二天CB第三天DF4有甲乙丙丁戊己6名运动员报名参加ABCDEF6个项目的比赛，下表中打的是各运动员报名参加的比赛项目，问6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛ABCDEF甲乙丙丁戊己答案：BCAFED（14分） 求图中从至的最小费用最大流，图中弧旁数字为（费用，容量）。（图要求画出来）最大流为6， 费用为84，6*6+4*7+8*2+2*2=84 （每个图1.5分）六、综合1. 图的建模有十六名运动员参加ABCDEFGH八种项目的游泳比赛，已知运动员号码及参加比赛项目如下表所示（表中打 者为参加项目）。为使参加多项比赛的运动员恢复体力，要求比赛顺序安排保证每个运动员不连续参加两项比赛，问如何安排才能做到这一点？运动员ABCDEFGH1 2 3