第六章 图与网络图 一、选择
1. 在图中用V表示点，用E表示边，如果有两个图G1={V1,E1}和图G2={V2,E2},若有V1?
V2 ,E1? E2，则称G1 是G2的一个（D）
A 偶图 B 部分图 C 完全图 D子图 2. 3. 在树图中，顶点有
A、
v个，边有e条，那么顶点和边的数量关系是（B ）
v=e B、e＝v-1 C、v＝e-1
4. 在图中用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 m×n D m÷n 6. 任何树中必存在次为（ A）的点
A 1 B 2 C 3 D4 7．含有n个顶点的完全图，其边数有（ B ）条。
1A n B n(n?1) C n(n-1) D n-1
28.具有n个顶点的树的边数恰好为（A ）条。
1A n-1条 B n条 C n(n?1) D n(n-1)
29.在网络图中s?t的最大流量（ C ）它的最小割集的容量。 A 大于 B 小于C 等于 D 无关
10. 构成最大流问题的条件之一是（B ）
A、网络有一个始点C、网络有一个终点
v B、网络有一个始点vs和一个终点vt
sv D 无要求
t11. 下图中（C ）是完全二分图
A
B
C 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.与某一个点
v相关联的边的数目称为点v的（次）
ii11.对起点与终点相重合的链称为（圈）。
12.若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为（连通图）。 13. 若在一个图中，如果每一对顶点之间至少存在一条（链），称这样的图为连通图。 14.一个简单图中若任意两点之间均有边相连，称这样的图为（完全图）。 15. 一个（简单图）中若任意两点之间均有边相连，称这样的图为完全图。
16.对要研究的问题确定具体对象及这些对象间的性质联系，这就要对研究的问题建立（图的模型）
17.（树）是无圈的连通图。
18.在树图中，称次为1的点为（悬挂点）
19..如果G1是G2的部分图，又是树图，则称G1是G2的（部分树） 20.树枝总长最小的部分树，称为（最小支撑树）。
21.把图的所有点分成V和V两个集合，则两个集合之间连线的最短边一定包含在（最小部分树）内。
22. (最短路问题)是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。
（）
23.矩阵算法中Dk给出网络中任意两点直接到达，经过一个、两个、···，到（2k-1）个中间点时比较得到的最短距离。
24.设网络图有p个点，则一般计算到不超过D（k），k的值按公式（ lg( p ? 1 ) ），即计算结束。
k?1??k lg225. 对图中每条边规定指向的图称为(有向图) 26.有向图的边称为(弧)，记作(vi , vj)，
27.弧(vi , vj)的最大通过能力，称为该弧的(容量)，记为c(vi , vj) ，或简记为 cij 。
28. (流)是指加在网络各条弧上的一组负载量，对加在弧(vi , vj)上的负载量记作 f (vi , vj) ，或简记作 fij
29. （割）是指将容量网络中的发点和收点分割开，并使s→t 的流中断的一组弧的集合。 30. （割的容量）是组成它的集合中各弧容量之和。
31.如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为 s→t 的弧（称前向弧，记作μ+），存在f < c (非饱和)；所有指向为 t →s 的弧（称后向弧，记为μ -），存在f > 0(非零)，这样的链称（增广链）。 32.求网络最大流的方法是（标号算法）
?
33.34.求网络的最大流，是指满足（容量限制条件）和（中间点平衡）的条件下，使v(f)值达到最大。
三、判断
1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（不正确） 2.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（正确） 3.如图中某点
v有若干个相邻点，与其距离最远的相邻点为vi1j，则边 [i,j]必不包含在最小
支撑树内。（正确） 4.如图中从
则连接v至其他各点的最短路在去掉重复部分后，v至各点均有唯一的最短路，
1恰好构成该图的最小支撑树。（正确）
5. Dijkstra算法提供了从网络图中某一点到其他点的最短距离。（正确 ）
6. 部分图不是子图，子图也不一定是部分图。（不正确） 7.树图的任意两个点之间有一条且仅有一条唯一通路。（正确） 8.一些重要的网络不能按数的结构设计。（正确） 9.. 一个图的最小部分树不唯一。（正确）
10. 不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。（正确）
(k)
11.D中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。（正确） 12.零流不是可行流。（不正确）
13. 在网络中 s→t 的最大流量等于它的最小割集的容量。（正确） 14. 标号算法其本质是判断是否存在增广链，并找出增广链。（正确）
15.求最小费用流时，一方面通过增广链来调整流量，另一方面要找出每一步费用最小的增广链。是最大流和最短路问题的综合求解。（正确）
四．名词解释
1.环：如果边e的两个端点相重，称该边为环。
2.多重边 如果两个点之间的边多于一条，称为具有多重边。
3.简单图 无环，无多重边的图称为简单图。
vv4.次 与某一个点i相关联的边的数目称为点i的次（也叫做度或线度）。
5.奇点 次为奇数的点称作奇点。
6.偶点 次数为偶数的点称作偶点。
7.孤立点 次数为0的点称作孤立点。
8.链 有些点和边的交替序列μ=不相同，且任意
?v0,e1,v1,???,ek,vk?，若其中各边
e1,e2,???,ek互
vi,t?1和
vit（2?t?k）均相邻，称μ为链。
9.路 如果链中所有的顶点
v0,v1,???,vk也不相同，这样的链称为路。
10.圈 对起点与终点相重合的链称作圈。
11.回路 起点与终点重合的路称作回路。
12.连通图 若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。
13.完全图 一个简单图中若任意两点之间均有边相连，称这样的图为完全图。含有n个顶 点的完全图，其边数有条
2Cn?1n(n?1)2。
14.偶图 如果图的顶点能分成两 个互不相交的非空集合V1和V2，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图）。
15.完全偶图：如果偶图的顶点集合V1，V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。完全偶图中V1含m个顶点，V2含n个顶点，则其边数共m·n条。 16.网络图：如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样
的图称为网络图。
?v,v?,称v和v是边e的端点。
18.关联边：若有边e可表示为e??v,v?，称边e为点v或v的关联边。
17.端点：若有边e可表示为e?ijijijij19.点相邻：若点20.边相邻：若边21.子图：图
v，vij与同一条边关联，称点具有公共的端点，称边和图
v和vij相邻。 相邻。
e和ei1je和eijG?V,E11G?V,E222，如果有
V?V12和
E?E12,称
G是
1G2的一个子图。
22.部分图：如果有
V?V12和
E?E12,称
G是G12的一个部分图。
23.图的模型：对要研究的问题确定具体对象及这些对象间的性质联系，并用图的形式表示出来，这就是对研究的问题建立图的模型。
24.树图：是无圈的连通图。这类图与大自然中数的特征相似，因而得名树图。 25.部分树：如果
G是G12的部分图，又是树图，则称
G是G12的部分树。
26.树枝：树图的各条边称为树枝
27.最小部分树：假定各边均有权重，一般图分树，称为该图的最小部分树。
28.弧：有向图上的连线是有规定指向的，称作弧。记作点。
29.弧的容量：对网络上的每条弧简写
G2含有多个部分树，其中树枝总长最小的部
(v,v)表明方向是从vi点指向vijj(v,v)都给出一个最大的通过能力，称为该弧的容量，
ijcij
