在图4-14中, (1) 是非简单图, (2) 是完全图, (3) 和 (4) 都是哈密尔顿图,其中 (3) 又是欧拉图, (5) 是树。
5()
A.A
B.B
C.C
D.D
参考答案:D
解析:
本题主要考查一些特殊图的概念,下面分别进行介绍。
非简单图:既无平行边也无环的无向图称为简单无向图,有平行边或有环的图是非简单图。在本题中,只有B有环,其余的5个图都既无平行边也无环,因而(26)的答案应为B。
完全图:每个顶点度数都等于n-1的n阶无向简单图称为n阶无向完全图,并记为 kn。在给定的6个图中,只有A图满足要求,它是k5,所以(27)的答案为A。
哈密尔顿图:通过连通图中所有结点一次且仅一次的回路称为哈密尔顿回路,具有哈密尔顿回路的图称为哈密尔顿图。一个图是哈密尔顿图的必要条件(注意:不是充分条件)是图的连通性和图中不存在度数为1的顶点。在本题中,E图是分离的k3,即E是非连通图,而C、D、F均有度数为1的顶点,所以C、D、E、F都不是哈密尔顿图。 A、B中均存在哈密尔顿回路,因而A、B均为哈密尔顿图。所以(28)、(29)的答案可以为A、B。
欧拉图:通过连通图(有向图或无向图)中每条边一次且仅一次遍历图中所有顶点的回路,称为欧拉回路,存在欧拉回路的图称为欧拉图。设G是连通图,则G是欧拉图,当且仅当G的所有顶点都是偶顶点(度数为偶数的顶点)。在本题中,只有A连通且无奇度顶点,因而A为欧拉图,在其余各图中,E无奇度顶点,但它不连通,所以不是欧拉图。而B、C、D、F中都有奇度顶点,因而它们也不是欧拉图,所以(28)的答案为A,(29)的答案为B。
树:连通且无回路的无向图称为无向树。在本题中,只有D满足要求,其余5个图中均有回路,因而都不是树,(30)的答案为D。
另外,还有一些特殊的图,我们也简单介绍一下。
平面图:平面图是指一个图能画在平面上,除顶点之外,再没有边与边相交。在本题中,B、C、D、F为平面图。
二部图:若能将无向图的顶点集V划分成两个子集V1和V2,使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称为偶图)。在本题中, D为二部图。