提示:内容已经过期谨慎付费，点击上方查看最新答案
图论
- 设G是一个有n个顶点m条边的简单图，则下列一定成立的是（ ）.
- 设G是4个顶点的标号完全图（即给G的每个顶点标号），则G的不同的生成树（注意“不同”是指标号不同，不是不同构）的个数等于（ ）.
- 图G的围长定义为图G的最短圈的长度（若图G中无圈，则定义G的围长为无穷大）. Petersen图的围长等于（ ）.
- 设T是一棵最大度为
的森林，则T的边色数等于（ ）. - Petersen图的边连通度等于（ ）.
- Petersen图中长度等于6的圈的个数等于（ ）.
- 正六面体的顶点数、边数和面数分别为（ ）.
- 正十二面体的顶点数、边数和面数分别为（ ）.
本题中所示图的连通分支数等于（ ）.- 五个顶点的非同构的树有（ ）.
- 顶点数为6的非同构2-正则简单图共有（ ）.
- 设
是图G的所有连通分支，且
的色数分别等于2,3,5，则G的色数等于（ ）. - 设G =(X,Y) 是完全二部图，且X, Y中分别含有m,n个顶点，则G的边数等于（ ）.
- 设G是n个顶点的标号完全图（即给G的每个顶点标号），则G的不同的生成树（注意“不同”是指标号不同，不是不同构）的个数等于（ ）.
- 设G是一个有n个顶点、m条边的连通图，则下列一定成立的是（ ）.
- 正二十面体的顶点数、边数和面数分别为（ ）.
- 顶点标号完全二部图
的不同生成树（注意“不同”是指标号不同，不是不同构）的个数等于（ ）. - 设有平面上n（n大于等于3）个点构成的集合S，其中任两点之间的距离至少是1，则S中距离恰好等于1的点对至多有（ ）.
本题所给图的非同构生成树的个数等于（ ）.- Petersen图的最大匹配所含边的条数为（ ）.
完全二部图
(m,n均大于0)是Hamilton图的充分必要条件是（ ）.
该图的最小点覆盖集的个数等于（ ）.- 完全二部图
(m,n均大于0)是Euler图的充分必要条件是（ ）. - 设G是有n个顶点m条边的简单图，则下列哪些可以作为G是树的等价条件（ ）.
- 当k取下列哪些值时，k维立方体图是Euler图（ ）.
- 若图G与H同构，则下列正确的是（ ）.
- 简单图G的补图H是指和G有相同顶点集的一个简单图，在H中两顶点相邻当且仅当它们在G中不相邻. 则下列正确的是（ ）.
下列选项中，哪些是该图的极大独立集（ ）.
本题中所给图能一笔画成（即笔不离纸、线不重复）.（ ）
本题中所示图是Hamilton图.（ ）
本题中所示图没有完美匹配.（ ）- 对二部图G = (X,Y), X和Y都是控制集，也都是独立集.（ ）
- 一棵树T最多只有一个完美匹配.（ ）
- 不可平面图的每个子图也是不可平面图.（ ）
- Petersen图是Hamilton图.（ ）
本题中所示图是Hamilton图.（ ）- 任意图的边色数不超过它的最大度加1.（ ）
- 设G =(X,Y)是k -正则二部图，则X与Y所含顶点的个数可以不相等.（ ）
图G是不可平面图.（ ）- 任意两个顶点均由唯一的路所连接的简单图一定是树.（ ）
- 至少有两个顶点的树的最长路的起点和终点的度都等于1.（ ）
- 如果图G的任二奇圈都有公共顶点，则G的色数不超过5.（ ）
- 设G是简单图且其最小度至少为k，则G中一定有长为k的路.（ ）
- k(k > 0)正则二部图一定存在完美匹配.（ ）
- 图G是连通图当且仅当存在G的某个顶点与其它顶点都有边相连.（ ）
- 设G是连通图，则G的边数大于或等于G的顶点数减去1.（ ）
- 每个没有割边的3-正则图都有完美匹配.（ ）
本题中所给的两个图G与H同构.（ ）- 最大度大于或等于k的树中至少有k个度等于1的顶点.（ ）
- 如果图G的直径至少是3，则其补图的控制数不超过2.（ ）
是某个图的色多项式.（ ）- 若图G中存在从u到v的途径，则G中必存在从u到v的路.（ ）
- 设G是简单图且G的每个顶点的度等于2，则G是一个圈.（ ）
- 任意二部图的边色数等于它的最大度.（ ）
- 图G有完美匹配的充分必要条件是G有偶数个顶点.（ ）
- 5个顶点的完全图不是可平面图，但其删掉任一条边后所得之图是可平面图.（ ）
- 任意图的边色数大于或等于它的最大度.（ ）
- Petersen图是二部图.（ ）
- 恰有两个1度顶点的树一定是一条路.（ ）
- 任何k-边连通图都是k-连通图.（ ）
- 设G是简单图，则G的边色数满足
.（ ） 
本题中所示图是Hamilton图.（ ）- Petersen图删除任一顶点后所得之图是Hamilton图.（ ）
- 若G是n个顶点的连通图，则图G的色多项式满足
.（ ） - 若图G的最小度至少为2，则G中一定有圈.（ ）
- 不是块的连通图G至少有两个块，他们每个恰含有G的一个割点.（ ）
- 平面图G的顶点数等于它的对偶图的面数.（ ）
A: B: C: D:
答案:
A:16 B:32 C:4 D:8
答案:125
A:5 B:6 C:4 D:3
AI参考:答案：C推理过程：Petersen图是一个五元图，它有两个圈，一个圈的长度为5，另一个圈的长度为无穷大（因为无法构成封闭路径），所以围长为4。'
A: B: C: D:
AI参考:答案：A解析：由于树可以看成是一棵没有父节点的根节点和若干条有向边组成的森林，森林中每个树的度就是构成该树的边数。本题森林中的树的根节点数是4，即有向边的数目为4。因此选A。'
A:3 B:2 C:1 D:4
答案:3
A:7 B:10 C:8 D:9
答案:3
A:8,12,6 B:9,11,6 C:8,12,7 D:7,12,6
答案:6,12,8
A:18,30,12 B:20,30,12 C:18,28,12 D:20,30,11
A:1 B:2 C:4 D:3
AI参考:本题中所示图的连通分支数为3。这是一个由三个子图构成的图形，每个子图都可以单独成为一个连通分支。因此，正确选项为D：3。'
A:3个 B:5个 C:2个 D:4个
A:2个 B:0个 C:1个 D:3个
AI参考:正确答案是D：3个。非同构2-正则简单图即所有的顶点的度数都相同，并且所有的顶点的度数均为偶数。非同构意味着有相同的边的数目和种类，2-正则意味着所有顶点的度数为2，因此每张图的边的数目应该为奇数。同时，因为是简单图，即没有重边。根据以上的要求和限制，图的总数可以用下面的公式算出：N=C^3*(3^5) (C^3表示从3个顶点中选3个作为一组，共有C^3种选法；3^5表示从5个顶点的度数中选一个作为度数，共有3^5种选法)。因此，顶点数为6的非同构2-正则简单图共有3个。'
A:3 B:2 C:10 D:5
AI参考:答案：D解析：由于G是图，所以G的色数即为G中可能出现的着色数。题中要求判断色数大小，且图片展示两个颜色间隔对应点不在同一条边上，且两者与第一个颜色间隔对应的点不在同一条边上，所以G的色数等于5。故答案为D。'
A:m/n B:m - n C:m + n D:mn
AI参考:正确答案是C：m + n。完全二部图G =(X,Y)的边数等于X和Y中顶点的总数，即m+n。因为完全二部图中的每一条边都连接了一个X中的顶点和Y中的一个顶点。'
A: B: C: D:
A:G至少包含n -m +1个不同的圈 B:G至少包含n -m +3个不同的圈 C:G至少包含n -m +2个不同的圈 D:G至少包含n -m -1个不同的圈
A:13,31,20 B:13,30,20 C:12,30,20 D:12,31,20
A:3 B:6 C:9 D:81
AI参考:答案：B推理过程：由于图中含有8个顶点，每个顶点都有3种状态（0或1表示顶点处否以通过其它边与其它顶点连接），共有3的八次方个顶点数不同且非连通图。又因为对于同一张图可以转换不同边的连通关系（连接与否、顺序、数目不同，路径/权值任意大小可逆变换等）生成多种不同连通树。在全二部图中同一条边的边权可为任意非负实数。若一棵树的所有边权都为相同的非负实数，则存在无数种生成方式，所以不考虑该情况，因此，正确答案为B项。另外补充一点，因为题干要求是顶点标号完全二部图，所以在判断是否为连通时只需要判断是否任意两个顶点之间都存在路径即可，无需考虑边权值是否相同。所以不需要进行遍历或者DFS/BFS等操作。以上推理过程仅供参考，如果需要更详细的信息，建议咨询专业人士。'
A:3n-9对 B:3n-8对 C:3n-6对 D:3n-7对
AI参考:正确答案是D，3n-7对。根据题目条件，任意两点之间的距离至少是1，说明这些点之间最多只有两个点距离为1。因此，所有满足条件的点对数量最多为所有点对的三分之一减去距离为2及以上（即大于2）的点对数量。由于任意两点之间的距离至少是1，所以距离大于2的点对数量最多只有n-2个。因此，距离恰好等于1的点对数量最多为(n-2) × 3/2 - 1，即3n/2 - 7，其中1≤n≥3。所以选项D为正确答案。'
A:2 B:4 C:3 D:1
AI参考:正确答案是C：3。本题是一个二叉树的问题，根据二叉树的性质，非同构生成树的个数等于二叉树节点数减一，所以本题所给图的非同构生成树的个数为8-1=7，即3个。因此，正确答案为C。'
A:2 B:3 C:5 D:4
AI参考:单选题】Petersen图的最大匹配所含边的条数为（ ）。D: 4。在Petersen图中，使用最大匹配时，只有一个顶点会被分配到匹配中，因此匹配的边数为4。'
A:m > n，m < n，m = n都不对 B:m > n C:m = n D:m < n
AI参考:答案应该是B:m > n。完全二部图是所有顶点可以分为两个完全集合并允许一条边连接两个集合中不同的元素。为了图是Hamilton图，也就是可以画出一个闭环，也就是说如果集合一中的节点可以不断地从一个集合并到另一个集合并不断重回原来的节点（只返回）那图就可以形成闭环，那这样的话集合并的节点数就必须要大于二了，也就是m > n。注意，选项D的错误在于：虽然对于一些m < n的情况是完全二部图可能不是Hamilton图，但m < n并不一定是必要条件，也就是说，不完全符合问题的描述。因此D选项不正确。而A和C选项过于绝对化，并不符合问题的实际情况。因此只有B选项完全符合问题的描述。所以选择B。不过这是一个图像表示的数学问题，这种问题的文字解释可能会有点抽象和困难，但是基于题目的图像可以直接显示出该图的结构，因此通常还是直接从图像来考虑问题的。不过要注意，完全二部图的m和n并不能直接决定是否为Hamilton图，还需要考虑其他因素。'
A:1 B:3 C:4 D:2
AI参考:正确答案是D，即最小点覆盖集的个数为2。这个图是一个简单的点覆盖问题，其中包含了两个点，因此最小点覆盖集的个数为2。'
A:m,n均为偶数 B:m,n均为奇数 C:m为偶数, n为奇数 D:m为奇数, n为偶数
AI参考:正确答案是D：m为奇数, n为偶数。根据欧拉图的定义，如果一个图中所有顶点的度数均为偶数，那么这个图就是欧拉图。而在完全二部图中，所有顶点的度数可以都为奇数，也可以都为偶数，但不会既有奇数又有偶数。因此，如果一个完全二部图是Euler图，那么它的顶点数n一定是偶数，且阶数为m的边的度数必须为奇数。因此，选项D是正确答案。选项A和B都不正确，因为完全二部图的阶数m和n可以是奇数或偶数。选项C也不正确，因为如果阶数为m的边的度数为偶数，那么顶点数n可以为奇数或偶数。'
A:G连通且m = n-1 B:G无圈且m = n-1 C:G连通，且对G中的任意一条边e，G - e不连通 D:G连通，且对G的任意两个不相邻的顶点u与v，G + uv恰有1个圈
AI参考:正确答案是【B:G无圈且m = n-1】。树是无向连通图，且任意两个顶点之间只有一条边，因此B选项是正确的。A选项中，如果图不是连通的，那么它就不是树。C选项中，如果图中存在环，那么它就不是树。D选项中，如果图中存在不相邻的两个顶点之间有多条边相连，那么它就不是树。因此，只有B选项是正确的等价条件。'
A:4 B:3 C:2 D:1
AI参考:正确答案是B、D。在三维空间中，Euler图需要满足所有顶点、边和面数相等。对于k维立方体图，如果k=3，那么它的顶点数、边数和面数都是k^3，因此它是Euler图。因此选项B正确。对于选项A和C，k=4时，立方体图不是Euler图，因为它的边数比面数多一个。对于选项D，k=1时，1维立方体图只有一条边，它没有面，因此也不是Euler图。所以答案是B和D。'
A:G与H有相同的顶点数 B:G与H有相同的度序列 C:G与H有相同的边数 D:G与H所含三角形（即长度等于3的圈）个数相等
AI参考:正确选项为：A、C、D。根据题目描述，图G与H同构，说明它们具有相同的结构，因此它们有相同的顶点数、边数和所含三角形个数（即长度等于3的圈）相等。但是，度序列（即每个顶点的度数）可能会因为边的连接方式不同而不同。因此，选项B不正确。'
A:|V(G)| = |V(H)| B:|E(G)| = |E(H)| C:四个顶点的路的补图同构于它自身 D:
AI参考:正确答案是B和C。根据题目描述，补图H是指和G有相同顶点集的一个简单图，在H中两顶点相邻当且仅当它们在G中不相邻。因此，B选项正确，因为G和H有相同的顶点集，所以它们的边集也相同。对于C选项，由于四个顶点的路的补图是包含所有与原图不构成路的子图，因此它与原图具有相同的结构，所以C选项也正确。A选项不正确，因为G和H不一定有相同的顶点数。D选项也不正确，因为题目中没有给出其他条件。'
A: B: C: D:
AI参考:正确选项为“C: ”。该图是一个有向图，其中节点表示不同的元素，边表示元素之间的关系。极大独立集是指在一个图中，如果一个集合中的元素之间没有相互关联，那么这个集合就是一个极大独立集。根据该图的图形结构，可以发现节点C与其他节点之间没有相互关联，因此节点C是一个极大独立集。其他选项中的节点与其他节点之间存在相互关联，因此不是极大独立集。'
A:对 B:错
AI参考:正确答案是B：错。根据题目描述，需要判断给定的图形是否可以一笔画成。根据图形的特征，如果图形可以一笔画成，那么它一定是连通图，且图形中任意一条边都不包含在环中。从给定的图形中可以看出，它是由两个不连通的区域组成，因此无法一笔画成。所以，选项B是正确的，表示题目中的图形无法一笔画成。'
A:对 B:错
AI参考:答案是B：错。根据题目描述，给出的图片是一个图像文件，并且该图像中显示了一个图形，但并没有明确说明这个图形是Hamilton图。因此，无法确定该图是否是Hamilton图，所以答案为B，即“错”。'
A:错 B:对
AI参考:正确答案是B，对。从题目中给出的图片来看，没有完美匹配的元素或图像。'
A:对 B:错
AI参考:二部图是指图中的顶点可以划分为两个独立的集合，而二部图中的顶点则分别属于这两个集合。题目中给出的二部图G = (X,Y)，其中X和Y都是控制集，也就是说G中存在某种边使得X中的顶点能够控制Y中的顶点，同时X和Y都是独立集，即X中的顶点与Y中的顶点之间没有直接的联系。因此，这个判断题是正确的，选项A是正确答案。'
A:对 B:错
AI参考:答案是B：错。一棵树T最多可以有多个完美匹配。这意味着对于一个给定的树T，可能有多个不同的完美匹配存在。'
A:错 B:对
A:错 B:对
A:对 B:错
AI参考:正确答案是A，对。从题干中给出的图片，我们可以看到它是一张Hamilton图，所以答案是A，即“对”。'
A:对 B:错
AI参考:答案是B：错。任意图的边色数不可能超过它的度数加1，但是题目中使用了“任意图”，也就是说没有限制图的类型和性质，因此这个说法是错误的。'
A:对 B:错
AI参考:答案是B：错。根据二部图的定义，G=(X,Y)是一个k-正则二部图，其中X和Y分别表示顶点的两种类型，且X与Y所含顶点的个数必须相等。因此，该题判断是错误的。'
A:对 B:错
AI参考:答案是B:错。根据题目中的图片，图G不是不可平面图，而是可以平面表示的图。因此，该判断题是错误的。不可平面图是指无法用平面图来表示的图，而图G可以通过平移、旋转等方式表示。'
A:对 B:错
AI参考:答案：B。 题目描述不准确，简单图不一定是树，但需要分析简单图和树的定义和特征才能给出确切答案。'
A:对 B:错
AI参考:答案是B：错。至少有两个顶点的树的最长路的起点和终点的度都等于1是不正确的。在树中，树的每个顶点的度数可以有多种情况，除了度为1的情况，还有度为2的情况。因此，树的最长路的起点和终点的度数不一定都等于1。'
A:对 B:错
AI参考:答案是A：对。根据题目描述，如果图G的任二奇圈都有公共顶点，说明G的奇圈之间存在边，这些边可以将G的顶点分为几个部分，而这些部分的数量不会超过5个。因此，图G的色数不会超过5，答案是肯定的。所以答案是“对”。'
A:对 B:错
AI参考:答案：B。由题目所给条件可知，该图中包含的最小边的度数至少为k，但不代表每条边的度数都为k，因此不一定存在长为k的路。所以该题为错。'
A:对 B:错
AI参考:答案是B:错。正则二部图存在完美匹配的条件需要进一步分析，不能简单地根据题目给出的条件判断。因此，该判断题是错误的。'
A:错 B:对
AI参考:答案是B：对。根据连通图的定义，图G是连通图当且仅当存在G的某个顶点与其它顶点都有边相连。因此，这个判断题是正确的。'
A:对 B:错
AI参考:答案是B：错。因为连通图中可能存在回路，使得某些顶点与其他顶点之间有多条边相连，这种情况下边的数量可能小于顶点数减一。因此，该命题是错误的。'
A:对 B:错
AI参考:答案是B:错。每个没有割边的3-正则图都有完美匹配。这个说法是不正确的。完美匹配是指图中的每对节点之间都有一个边相连，而3-正则图是指所有顶点都属于一个阶数为3的子图。如果一个图没有割边，那么它可能存在完美匹配，也可能不存在完美匹配。因此，没有给出具体的图并不能确定是否有完美匹配。'
A:错 B:对
AI参考:正确答案是B：对。根据题目中的描述，两个图G与H被视为同构，这意味着它们具有相同的图形结构和相应的关系。因此，答案为B：对。'
A:错 B:对
AI参考:答案是B：对。在最大度大于或等于k的树中，树的所有顶点的度数之和至少为k+1，其中度为1的顶点个数至少为k，因此至少有k个度等于1的顶点。所以，判断题的说法是正确的，答案为B。'
A:对 B:错
AI参考:答案是B：错。因为如果图G的直径至少是3，则其补图的控制数可能超过2，因为补图的控制数不仅取决于原图的边数，还取决于原图的顶点数。因此，这个判断题是错误的。'
A:对 B:错
AI参考:题目中的图像没有提供足够的信息来判断它是否是某个图的色多项式。从题目描述中无法确定该图像的来源、对应的图的信息以及色多项式的定义等。因此，无法做出正确的判断。所以，答案是B：错。'
A:错 B:对
A:对 B:错
AI参考:答案是B:错。根据题目描述，G是一个简单图，且每个顶点的度等于2。但是，一个图是否是圈需要更多的信息才能确定，比如它的边数和节点数。因此，仅根据题目中的条件无法判断G是否是一个圈。所以，该判断题是错误的。'
A:错 B:对
AI参考:正确答案是B：对。因为任意二部图的边色数不会小于它的最大度，因此题干中的判断是正确的。'
A:对 B:错
AI参考:答案是B：错。图G有完美匹配的充分必要条件是G的顶点数为偶数。这是因为对于一个有偶数个顶点的图G，其所有顶点的度数都是偶数，因此可以找到一个完美匹配。但是，对于一个有奇数个顶点的图G，其顶点的度数可能为奇数或偶数，因此不一定能够找到完美匹配。因此，图G有完美匹配的充分必要条件是G有偶数个顶点是错误的。'
A:对 B:错
AI参考:答案：B：错。完全图是指每两个顶点之间都有一条边相连的图，因此完全图具有环路。对于一个有 n 个顶点的完全图，任意选取一条边，它必定会将图分为两个互不相交的部分，其中一个部分包含原完全图的某个顶点，另一个部分包含原完全图的另一个顶点。因此，删掉任一条边后所得之图一定是可平面图。但是，对于一个完全图来说，它包含了所有的环路，而这些环路在平面上可能会产生冲突，因此它不是可平面图。所以，判断题“5个顶点的完全图不是可平面图，但其删掉任一条边后所得之图是可平面图”是错误的。'
A:对 B:错
AI参考:答案：B：错。任意图的边色数不可能大于它的最大度，因为边色数是指图的颜色数，而颜色数不可能超过图中边的数量。因此，这个判断题是错误的。'
A:错 B:对
A:对 B:错
AI参考:答案是B:错。恰有两个1度顶点的树一定是一条路。这句话是错误的。因为一个树只有一个度为1的顶点，所以恰有两个度为1的顶点的树一定不是一条路。它可能是一个环，也可能是一个分支结构，不一定是一条路。'
A:对 B:错
AI参考:答案是B:错。虽然k-边连通图中的任意一条边都连接两个k-连通区域，但可能存在一些k-边不连通的情况，导致不是所有k-边连通图都是k-连通图。因此，该判断题是错误的。'
A:错 B:对
AI参考:从所给图谱来看，它表示的是二部图的概念，与边的颜色数无直接关系。所以这个判断题的正确答案是A：错。'
A:对 B:错
AI参考:正确答案是A。这是一个Hamilton图。在给定的图像中，我们看到的是一个环，这意味着该图是一个连通图，而Hamilton图是一种特殊的连通图，它的所有顶点都可以通过一条路径从一个顶点到另一个顶点。在这个图像中，我们看到的就是一条从顶点到顶点的路径，所以这个图像是一个Hamilton图。因此，答案为A，“对”。'
A:对 B:错
AI参考:答案：B：错。Petersen图是一个五阶无向图，删除任何一个顶点后都不会得到一个连通图，因此它不能是Hamilton图。所以，Petersen图删除任一顶点后所得之图不是Hamilton图。'
A:错 B:对
AI参考:B:对。根据题目描述，G是n个顶点的连通图，因此G的色多项式应该满足给定的公式。所以，正确答案是B：对。'
A:错 B:对
AI参考:B:对。根据题目描述，如果一个图的最小度至少为2，那么它可能是一个有向图或有环的无向图。如果是无向图，并且没有环，那么它的最小度将达不到2。而题目明确要求一定有圈，即图中存在一个循环结构，所以该判断为对。'
A:对 B:错
AI参考:答案是B：错。根据图的连通性，块连通图是指任何两个顶点都属于同一个块，也就是说，图的块是指若干个顶点构成的集合。对于一个图G，如果G至少有两个块，那么G一定包含至少两个顶点，因此每个块至少包含一个顶点。而题目中并没有提到G是否包含割点，因此无法确定答案。因此，答案是B：错。'
A:错 B:对
AI参考:B:对。根据图论的知识，一个图的顶点数和边数之间的关系称为原图的特征，而其面数和顶点数之间的关系则称为原图的配边数。对于一个平面图，其顶点数等于对偶图的面数，这是因为对偶图的面数是由原图的面数和边数相乘得到的，而顶点数和边数的关系是由原图的特征决定的。因此，这个判断题是正确的。'
温馨提示支付 ￥1.35 元后可查看付费内容,请先翻页预览!
