图论复习试题及答案

时间:2022-03-31 15:29:21 期末试题 我要投稿
  • 相关推荐

图论复习试题及答案

  图论是数学的一个分支,它以图为研究对象。以下是由阳光网小编整理关于图论复习试题的内容,希望大家喜欢!

图论复习试题及答案

  图论复习试题及答案

  1、设G是一个哈密尔顿图,则G一定是( )。

  (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图

  答:(4)(考察图的定义)

  2、一个图的哈密尔顿路是一条通过图中( )的路。

  答:所有结点一次且恰好一次

  3、在有向图中,结点v的出度deg+(v)表示( ),入度deg-(v)表示( )。 答:以v为起点的边的条数, 以v为终点的边的条数

  4、设G是一棵树,则G 的生成树有( )棵。

  (1) 0 (2) 1 (3) 2 (4) 不能确定

  答:1

  5、n阶无向完全图Kn 的边数是( ),每个结点的度数是( )。 n(n?1)答:, n-1 2

  6、一棵无向树的顶点数n与边数m关系是( )。

  答:m=n-1

  7、一个图的欧拉回路是一条通过图中( )的回路。

  答:所有边一次且恰好一次

  8、有n个结点的树,其结点度数之和是( )。

  答:2n-2(结点度数的定义)

  9、n个结点的有向完全图边数是( ),每个结点的度数是( )。 答:n(n-1),2n-2

  10、一个无向图有生成树的充分必要条件是( )。

  答:它是连通图

  11、设G是一棵树,n,m分别表示顶点数和边数,则

  (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

  答:(3)

  12、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( )片树叶。 答:2

  13、任何连通无向图G至少有( )棵生成树,当且仅当G 是( ),G的生成树只有一棵。

  答:1, 树

  14、设G是有n个结点m条边的连通平面图,且有k个面,则k等于:

  (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

  答:(1)

  15、设T是一棵树,则T是一个连通且( )图。

  答:无简单回路

  16、设无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。

  (1) 10 (2) 4 (3) 8 (4) 16

  答:(4)

  17、设无向图G有18条边且每个顶点的.度数都是3,则图G有( )个顶点。

  (1) 10 (2) 4 (3) 8 (4) 12

  答:(4)

  18、设图G=<V,E>,V={a,b,c,d,e},E={<a,b>,<a,c>,<b,c>,<c,d>,<d,e>},则G是有向图还是无向图?

  答:有向图

  19、任一有向图中,度数为奇数的结点有( )个。

  答:偶数

  20、具有6 个顶点,12条边的连通简单平面图中,每个面都是由( )条边围成?

  (1) 2 (2) 4 (3) 3 (4) 5

  答:(3)

  21、在有n个顶点的连通图中,其边数( )。

  (1) 最多有n-1条 (2) 至少有n-1 条

  (3) 最多有n条 (4) 至少有n 条

  答:(2)

  22、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为( )。

  (1) 5 (2) 7 (3) 8 (4) 9

  答:(4)

  23、若一棵完全二元(叉)树有2n-1个顶点,则它( )片树叶。

  (1) n (2) 2n (3) n-1 (4) 2

  答:(1)

  24、下列哪一种图不一定是树( )。

  (1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图

  (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 答:(3)

  25、连通图G是一棵树当且仅当G中( )。

  (1) 有些边是割边 (2) 每条边都是割边

  (3) 所有边都不是割边 (4) 图中存在一条欧拉路径

  答:(2)

下一页更多有关“图论复习试题及答案”的内容


  26、证明在有n个结点的树中,其结点度数之和是2n-2。

  证明:

  设T=<V,E>是任一棵树,则|V|=n,且|E|=n-1。

  由欧拉握手定理,树中所有结点的度数之和等于2|E|.

  从而结点度数之和是2n-2。

  27、任一图中度数为奇数的结点是偶数个。

  证明:

  设G=〈V,E〉是任一图。设|V|=n。

  由欧拉握手定理可得 ?deg(v)=2|E|可得,图中所有结点度数之和是

  v?V

  偶数。显然所有偶数度结点的度数之和仍为偶数,从而所有奇数度结点的度数之和也是偶数。因此,图中度数为奇数的结点一定为偶数个。

  28、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗?若是对的请证明之,否则请举例说明。

  证明:

  不对。

  反例如下:若G 本身是一棵树时,则G的每一条边都不可能是G的任一棵生成树(实际上只有惟一一棵)的弦。

  29、设T=<V,E>是一棵树,若|V|>1,则T中至少存在两片树叶。

  证明:

  (用反证法证明)设|V|=n。

  因为T=〈V,E〉是一棵树,所以|E|=n-1。

  由欧拉握手定理可得 ?deg(v)=2|E|=2n-2。

  v?V

  假设T中最多只有1片树叶,则?deg(v)?2(n-1)+1>2n-2。

  v?V

  得出矛盾。

  30、设无向图G=<V,E>,|E|=12。已知有6个3度顶点,其他顶点的度数均小于3。问G中至少有多少个顶点?

  解:

  设G中度数小于3的顶点有k个,由欧拉握手定理

  24=?deg(v)

  v?V

  知,度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时,G的

  顶点最少。即G中至少有9个顶点。

  30、设图G=<V,E>,|V|=n,|E|=m。k度顶点有nk个,且每个顶点或是k度

  顶点或是k+1度顶点。证明:nk=(k+1)-2m。

  证明:

  由已知可知,G中k+1度顶点为n-nk个。再由欧拉握手定理可知

  2m=?deg(v)=knk+(k+1)(n-nk)=(k+1)n+-nk

  v?V

  故nk=(k+1)-2m。

  31、如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。

  解: 用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图:

  树权C(T)=23+1+4+9+3+17=57即为总造价。

  一、填空题(每个2分,共20分)

  二、选择题(每个2分,共20分)

  三、问答题(每个4分,共20分)

  1、图的同构

  2、图的连通

  3、Hamilton图

  4、Euler 图

  5、树图

  6、割边

  7、割点

  8、关联矩阵

  9、邻接矩阵

  10、连通度

  11、完全图

  12、二部图

  13、简单图

  14、平面图

  15、生成树

  四、证明题(每题10分,共20分)

  五、计算题(20分)


【图论复习试题及答案】相关文章:

《证券投资分析》试题及答案-证券投资分析复习试题05-10

初二语文复习期末试题及参考答案05-10

心理学期末复习试题及答案03-25

初一语文上册期末复习试题附答案05-04

法学专业《商法》期末复习考试题及答案05-09

外企面试的经典的试题及答案05-09

药物分析试题及答案12-09

《采访学》试题及答案04-22

外企面试经典的试题及答案05-09

初一语文期末总复习测试题及答案参考05-06