4.1 图的概念和相关术语

4.1 图的概念和相关术语


4.1 图的概念和相关术语
一、选择题
  1.选择题题目部分

   ● 在图3-13中, (1) 是非简单图, (2) 是完全图, (3) 和 (4) 都是哈…

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  选择题练习自测表

题    号

考  查  点

得    分

(1)~(5) 简单图、完全图,哈密尔顿图、欧拉图  
(6) 无向图  
(7) 连通无向图  
(8) 出度、入度和度  
(9) 生成树的概念  
(10) 连通无向图的边数  

4.1 图的概念和相关术语

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部