4.1 图的概念和相关术语

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．n1 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个节点的无向图边最多的图是无向完全图，在无向完全图中，每个顶点与其他的n1个顶点都有边。含有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  选择题练习自测表