图论智慧树知到期末考试答案章节答案2024年长安大学

图论智慧树知到期末考试答案+章节答案2024年长安大学

答案:错如果图G是一个非平凡简单图且是一个正则图，则其独立数不超过图G的顶点数的一半.（）

答案:对k正则图一定存在完美匹配.（）

答案:错设n,m,c分别表示图G的顶点数、边数和连通分支数，则G是森林的充分必要条件是m=n-c.（）

答案:对任何k-边连通图都是k-连通图.（）

答案:错每棵树都是二部图.（）

答案:对设M和N是简单图G的两个不同的匹配，则由M与N的对称差在G中的边导出子图的每个连通分支必为一个偶圈.（）

答案:错设n,m,c分别表示图G的顶点数、边数和连通分支数，则G至少包含n–m+c个不同的圈.（）

答案:对5个顶点的完全图不是可平面图，但其删掉任一条边后所得之图是可平面图.（）

答案:对设M和N是简单图G的两个不同的匹配，则由M与N的对称差在G中的边导出子图的每个连通分支必为一条路.（）

答案:错图G有完美匹配的充分必要条件是G有偶数个顶点.（）

答案:错

答案:对每个没有割边的3-正则图都有完美匹配.（）

答案:对不是块的连通图G至少有两个块，他们每个恰含有G的一个割点.（）

答案:对存在一个平面图使得它恰好有5个面且任两个面之间至少有一条公共边.（）

答案:错

答案:错如果图G的直径至少是3，则其补图的控制数不超过2.（）

答案:对任意图的边色数不超过它的最大度加1.（）

答案:对设G是简单图且G的每个顶点的度等于2，则G是一个圈.（）

答案:错两人或更多人组成的人群中，总有两人在该人群内恰好有相同的朋友数.（）

答案:对

答案:错

答案:对连通是图的顶点集上的一个等价关系.（）

答案:对恰有两个顶点不是割点的简单连通图不一定是路.（）

答案:错一棵树T最多只有一个完美匹配.（）

答案:对若图G的每个顶点的度都是偶数，则G没有割边.（）

答案:对任意两个顶点均由唯一的路所连接的简单图一定是树.（）

答案:对如果非空连通图G有2个奇度顶点，则G有Euler闭迹.（）

答案:错至少有两个顶点的树的最长路的起点和终点的度都等于1.（）

答案:对每条闭迹的边集可被表示成一些圈的边集的不交并.（）

答案:对设G=(X,Y)是k-正则二部图，则X与Y所含顶点的个数可以不相等.（）

答案:错连通图中的两条最长路必有公共顶点.（）

答案:对

答案:错设G是简单图且其最小度至少为k，则G中一定有长为k的路.（）

答案:对同构关系是由简单图构成的集合上的一种等价关系.（）

答案:对

答案:错

答案:对以下选项正确的是（）.

答案:最小控制集必是一个极小控制集###极小控制集不唯一###极小点覆盖集未必是极小控制集设T是有n个顶点m条边的一棵树，则下列正确的是（）.

答案:T中任两个顶点均由唯一的路连接###T连通###m=n-1###T无圈2n个顶点的完全图的边色数等于（）.

答案:2n-1设G是有n个顶点m条边的简单图，则下列哪些可以作为G是树的等价条件（）.

答案:G无圈且m=n-1###G连通且m=n-1###G连通，且对G的任意两个不相邻的顶点u与v，G+uv恰有1个圈###G连通，且对G中的任意一条边e，G-e不连通正十二面体的顶点数、边数和面数分别为（）.

答案:20,30,12每个不连通图有1个孤立点（即度等于0的顶点）.（）

答案:错简单图G的补图H是指和G有相同顶点集的一个简单图，在H中两顶点相邻当且仅当它们在G中不相邻.则下列正确的是（）.

答案:下列对Ramsey问题的描述，正确的是（）.

答案:用红、蓝两种颜色对完全图的边染色,要求无论怎么染,都能要么出现染红色的p阶完全子图,要么出现染蓝色的q阶完全子图,这样的完全图至少应有多少个顶点?###求满足条件的图的最小顶点数，使得图中要么有p-团，要么该图的补图有q-团###求满足条件的图的最小顶点数，使得图中要么有p-团，要么有q个顶点的独立集Petersen图的连通度等于（）.

答案:3M是图G的一个最大匹配当且仅当G中无M可扩路.（）

答案:对

答案:r(3,4)≥9

答案:m,n均为偶数正六面体的顶点数、边数和面数分别为（）.

答案:8,12,6偶数个顶点的圈，匹配数和点覆盖数的关系是（）.

答案:相等设M是图G的关联矩阵，则M的每一列元素之和等于（）.

答案:2四个顶点的非同构的树有（）.

答案:2个Petersen图中长度等于6的圈的个数等于（）.

答案:10

答案:m=n

答案:图G的围长定义为图G的最短圈的长度（若图G中无圈，则定义G的围长为无穷大）.Petersen图的围长等于（）.

答案:5设G是4个顶点的标号完全图（即给G的每个顶点标号），则G的不同的生成树（注意“不同”是指标号不同，不是不同构）的个数等于（）.

答案:16

答案:5

答案:4

答案:3

答案:81设G是一个有n个顶点、m条边的连通图，则下列一定成立的是（）.

答案:G至少包含n-m+1个不同的圈

答案:4下列选项哪个是正确的（）.

答案:图G的极大独立集必是G的极小控制集三个顶点的非同构简单图有（）.

答案:4个一个非空连通图G是Euler图的充分必要条件是（）.

答案:G没有奇度顶点

答案:对设G是n（n大于或等于3）个顶点的路，则G的边色数和彩虹连通数分别为（）.

答案:2,n-1

答案:10五个顶点的完全图的谱为（）.

答案:4,-1,-1,-1,-1

答案:-3,0,0,0,0,3Petersen图是可平面图.（）

答案:错可平面图有可能存在子图是不可平面图.（）

答案:错从Petersen图中需至少删除几条边才能得到一个可平面子图（）.

答案:2条正八面体的顶点数、边数和面数分别为（）.

答案:6,12,8若地图上每两个地区都相邻，则最多能有几个地区（）.

答案:4个设H是图G的子图，则H的边色数不超过G的边色数.（）

答案:对Petersen图的边色数等于（）.

答案:4设G是n个顶点的圈，则G的色多项式P(G,k)等于（）.

答案:Petersen图的色数等于（）.

答案:33-正则Hamilton图的边色数为（）.

答案:3对于控制数为1的n个顶点的图，其控制集中顶点的度为n-1.（）

答案:对以下选项中正确的是（）.

答案:Q是G的极大团的充分必要条件是Q是G的补图中的极大独立集###任意6个人的聚会上,总有3人互相认识或互不认识若I是独立集,则它是极大独立集的充分必要条件是I是极小控制集.（）

答案:错

答案:下列命题中正确的是（）.

答案:顶点子集F是图G的点覆盖集当且仅当V(G)\F是G的独立集###一个图的独立数和点覆盖数的和等于它的顶点数目下列哪些是非空连通图G有Euler迹的充分条件（）？

答案:G没有奇度顶点###G有2个奇度顶点如果非空连通图G恰有2个奇度顶点，则G的Euler迹一定是从其中一个奇度顶点出发，终止于另一个奇度顶点.（）

答案:对

答案:错

答案:m=n

答案:错2n个顶点的完全图中不同的完美匹配个数为（）.

答案:(2n-1)!

答案:错设M和N是简单图G的两个不同的完美匹配，则由M与N的对称差在G中的边导出子图的每个连通分支必为（）.

答案:偶数个顶点的圈如果每个小伙子恰好认识k个姑娘，而每个姑娘也恰好认识k个小伙子(k>0)，则每个小伙子都能与自己认识的姑娘结婚.（）

答案:对一棵树T可以有两个或者两个以上的完美匹配.（）

答案:错若图G没有偶圈,则G的每个块或是2个顶点的完全图或是奇圈.（）

答案:对设G是有n个顶点m条边的k-边连通图,则下列一定成立的是（）.

答案:若图G的每条边是割边,则G是森林.（）

答案:对若H是连通图G的子图,则H的连通度不超过G的连通度.（）

答案:错

答案:3,4,4边数比顶点数少1的简单图一定是树.（）

答案:错

答案:3个设G是五个顶点的标号完全图（即给G的每个顶点标号），则G的不同的生成树（注意“不同”是指标号不同，不是不同构）的个数等于（）.

答案:125六个顶点的非同构的树有（）.

答案:6个若G是单圈图（即G是仅含一个圈的连通图）,则G的边数一定等于它的顶点数.（）

答案:对设图G有21条边，12个3度顶点，其余顶点的度均为2，则图G的顶点数为（）.

答案:15

答案:

答案:错

答案:(6,6,5,4,3,3,1)###(7,6,5,4,3,2,2)四个顶点的非同构简单图有（）.

答案:11个在任意6个人的聚会上，总有3个人互相认识，或者3个人互不认识.（）

答案:对图论中著名的中国邮递员问题是由中国管梅谷教授