admin 
4.1 图的概念和相关术语
一、选择题
1．选择题题目部分
● 在图3-13中， （1） 是非简单图， （2） 是完全图， （3） 和 （4） 都是哈密尔顿图，其中 （3） 又是欧拉图， （5） 是树。
● 具有n(n>0)个顶点的无向图最多含有 （6） 条边。
（6）A．n(n-1) B． C． D．n(n+1)
● 若G是—个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有 （7）顶点。
（7）A．11 B．10 C．9 D．8
● 在一个图中，所有顶点的度数之和等于所有边数 （8） 倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 （8） 倍。
（8）A．1，2 B．2，1 C．1，1 D．2，2
● 连通图的极小连通子图称为该图的 （9） 。
（9）A．生成树 B．回路 C．最小回路 D．关键路径
● 一个n个顶点的连通无向图，其边的个数至少为 （10） 。
（10）A．n1 B．n C．n+1 D．0
2．选择题练习答案与分析
题号（1） （2） （3） （4） （5）
答案 B A A B D
习题分析：
本题主要考查一些特殊图的概念。
非简单图：既无平行边也无环的无向图称为简单无向图，有平行边或有环的图是非简单图。在本题中，只有（B）有环，其余的5个图都既无平行边也无环，因而（1）的答案应为B。
完全图：每个顶点度数都等于n–1的n阶无向简单图称为n阶无向完全图，并记为kn。在给定的6个图中，只有A图满足要求，它是k5，所以（2）的答案为A。
哈密尔顿图：通过连通图中所有节点一次且仅一次的回路称为哈密尔顿回路，具有哈密尔顿回路的图称为哈密尔顿图。一个图是哈密尔顿图的必要条件（注意：不是充分条件）是图的连通性和图中不存在度数为1的顶点。在本题中，E图是两分离的k3，即E是非连通图，而C、D、F已均有度数为1的顶点，所以C、D、E、F都不是哈密尔顿图。A、B中均存在哈密尔顿回路，因而A、B均为哈密尔顿图。所以（3）、（4）的答案为A、B。
欧拉图：通过连通图（有向图或无向图）中每条边一次且仅一次遍历图中所有顶点的回路，称为欧拉回路，存在欧拉回路的图称为欧拉图。设G是连通图，则G是欧拉图，当且仅当G的所有顶点都是偶顶点（度数为偶数的顶点）。在本题中，只有A连通且无奇度顶点，因而A为欧拉图，在其余各图中，E无奇度顶点，但它不连通，所以不是欧拉图。而B、C、D、F中都有奇度顶点，因而它们也不是欧拉图，所以（3）的答案为A。
树：连通且无回路的无向图称为无向树。在本题中，只有D满足要求，其余5个图中均有回路，因而都不是树，（5）的答案为D。
另外，还有两种特殊的图。
平面图：平面图是指一个图能画在平面上，除节点之外，再没有边与边相交。在本题中，B、C、D、F为平面图。
二部图：若能将无向图的顶点集V划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图（也称为偶图）。在本题中，（4）为二部图。
题号（6）
答案 C
习题分析：
具有n个节点的无向图边最多的图是无向完全图，在无向完全图中，每个顶点与其他的n1个顶点都有边。含有n个顶点的无向完全图共有n×(n-1)/2条边。
题号（7）
答案 B
习题分析：
本题考查对于非连通无向图这个概念的理解能力。只需首先分析出具有36条边的连通无向图至少有多少个顶点，再加上一个孤立点（即没有任何边的点），就形成了非连通无向图。
根据对图的相关定义的理解可知，对于给定的边数的连通无向图，若该图为完全图，则此时的顶点数最少。若顶点数为n，则完全图的边数为n(n-1)/2。
n(n-1)/2=36，则可知，n=9。因此本题答案是B。
题号（8）
答案 B
习题分析：
图的所有顶点的度数之和等于图的边数的两倍，有向图的所有顶点的入度之和等于所有顶点的出度之和。
题号（9）
答案 A
习题分析：
连通图的极小连通子图称为该图的生成树。
题号（10）
答案 A
习题分析：
根据无向图的性质可知，对于一个有n个顶点的连通无向图，只需要n-1条边即可成为连通无向图。
3．训练自测表（如表4-1所示）
表4-1 选择题练习自测表
|
题 号 |
考 查 点 |
得 分 |
| （1）～（5） | 简单图、完全图，哈密尔顿图、欧拉图 | |
| （6） | 无向图 | |
| （7） | 连通无向图 | |
| （8） | 出度、入度和度 | |
| （9） | 生成树的概念 | |
| （10） | 连通无向图的边数 |
4.1 图的概念和相关术语
评论列表 人参与