第6章 图与网络图

《第6章 图与网络图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章图与网络图一、选择1.在图中用V表示点，用E表示边，如果有两个图G1={V1,E1}和图G2={V2,E2},若有V1V2,E1E2，则称G1是G2的一个（D）A偶图B部分图C完全图D子图2.3.在树图中，顶点有个，边有条，那么顶点和边的数量关系是（B）A、=B、＝-1C、＝-14.在图中用V表示点，用E表示边，如果有两个图G1={V1,E1}和图G2={V2,E2},若有V1=V2,E1E2，则称G1是G2的一个（A）A部分图B子图C二分图5.完全偶图中V1含m个顶点，V2含有n个顶点，则

2、其边数共（C）条。Am+nBm-nCm×nDm÷n6.任何树中必存在次为（A）的点A1B2C3D47．含有n个顶点的完全图，其边数有（B）条。AnBCn(n-1)Dn-18.具有n个顶点的树的边数恰好为（A）条。An-1条Bn条CDn(n-1)9.在网络图中st的最大流量（C）它的最小割集的容量。A大于B小于C等于D无关10.构成最大流问题的条件之一是（B）A、网络有一个始点B、网络有一个始点和一个终点C、网络有一个终点D无要求11.下图中（C）是完全二分图ABCD12.下面（D）是最短路问题A课

3、程排序问题B生产计划问题C人力资源问题D选址问题13.求网络图中任意两点之间的最短距离的方法是（C）A求最小部分树B矩阵算法CDijkstra算法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.与某一个点相关联的边的数目称为点的（次）11.对起点与终点相重合的链称为（圈）。12.若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为（连通图）。13.若在一个图中，

5、如果每一对顶点之间至少存在一条（链），称这样的图为连通图。14.一个简单图中若任意两点之间均有边相连，称这样的图为（完全图）。15.一个（简单图）中若任意两点之间均有边相连，称这样的图为完全图。16.对要研究的问题确定具体对象及这些对象间的性质联系，这就要对研究的问题建立（图的模型）17.（树）是无圈的连通图。18.在树图中，称次为1的点为（悬挂点）19..如果G1是G2的部分图，又是树图，则称G1是G2的（部分树）20.树枝总长最小的部分树，称为（最小支撑树）。21.把图的所有点分成V和两个集合

6、，则两个集合之间连线的最短边一定包含在（最小部分树）内。22.(最短路问题)是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。23.矩阵算法中D（k）给出网络中任意两点直接到达，经过一个、两个、···，到（2k-1）个中间点时比较得到的最短距离。24.设网络图有p个点，则一般计算到不超过D（k），k的值按公式（），即计算结束。25.对图中每条边规定指向的图称为(有向图)26.有向图的边称为(弧)，记作(vi,vj)，27.弧(vi,vj)的最大通过能力，称为该弧的(容量)，记为c

7、(vi,vj)，或简记为cij。28.(流)是指加在网络各条弧上的一组负载量，对加在弧(vi,vj)上的负载量记作f(vi,vj)，或简记作fij29.（割）是指将容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。30.（割的容量）是组成它的集合中各弧容量之和。31.如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为s→t的弧（称前向弧，记作μ+），存在f0(非零)，这样的链称（增广链）。32.求网络最大流

8、的方法是（标号算法）33.34.求网络的最大流，是指满足（容量限制条件）和（中间点平衡）的条件下，使值达到最大。三、判断1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（不正确）2.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（正确）3.如图中某点有若干个相邻点，与其距离最远的相邻点为，则边[i,j]必不包含在最小支撑树内。（正确）4.如图中从至各点均有唯一的最短路，则连接至其他各点的最