首页 > 试题广场 >

设 G 是一个具有 6 个顶点, 11 条边的图，其每个顶点

[单选题]
设 G 是一个具有 6 个顶点, 11 条边的图，其每个顶点的度为 3 或 4 ，则图 G 是什么图？ 
  • G 是平面图；
  • G 不连通；
  • G 为偶图(也称二部图)；
  • G 不是哈密顿图。
查看正确选项
添加回答
xuyan111头像 xuyan111
图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图
发表于 2018-03-10 15:41:03 回复(0)
代家宠妻程序羊头像 代家宠妻程序羊
偶图（二部图/二分图）：顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。判断方法：用染色法，把图中的点染成黑色和白色。首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现有相邻且同色的点，那么就退出，可知这个图并非二分图（一次bfs，O（n））。
哈密尔顿图就是不重复过顶点但可一次过完所有顶点的图，判断方法：图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图
发表于 2018-03-18 15:50:21 回复(0)
0_0?头像 0_0?
平面图
  • 定义：在图论中，平面图是可以画在平面上并且使得不同的边可以互不交叠的图。一个平面图将平面分成若干个互不相通的封闭区域，以及图的外部的区域。
  • 面：图的外面的区域称为图的外部面，而图里面每个被顶点和边分割出来的封闭并连通的区域称为图的内部面。围成每个面图的每个面至少对应着三条边。
  • 计算公式：平面图的顶点个数、边数和面的个数之间有一个公式：V-E+F=C+1其中，V是顶点的数目，E是边的数目，F是面的数目，C是组成图形的连通部分的数目。当图是单连通图的时候，公式简化为：V-E+F=2
  • 下图来自百度百科

  • 由上图K4，可以画出题中给的平面图
  • 顶点数：V=6
  • 边数：E=11
  • 面数：F=7，内部面有6个（下图中1~6），外部面有1个（下图中7）
  • 连通部分数：C=1（该图可以一笔画完，是哈密顿图，所以连通部分数是1）
  • 公式成立，所以这是一个平面图。

发表于 2021-10-30 22:23:58 回复(0)
牛客161139872号头像 牛客161139872号
判断哈密尔顿图：图中任意两个点的度之和大于或等于定点的度数
发表于 2020-07-05 15:22:52 回复(0)
__pen头像 __pen

笔记：任意两点的度的和大于等于顶点数是哈密顿图

发表于 2019-11-11 09:11:56 回复(0)
菜鸡准备转岗头像 菜鸡准备转岗
做笔记： 图中任意两点度之和大于或等于顶点总数，那么这个图一定是哈密顿图。
发表于 2019-09-02 09:53:00 回复(0)
JCMaxwell头像 JCMaxwell
如果該圖是完全二分圖K3,3之上任意在不相鄰的頂點間補齊邊數，這圖顯然就不是平面圖，這道題有夠有問題的ho
发表于 2019-05-24 15:45:33 回复(0)
我是超越迷妹了😘头像 我是超越迷妹了😘
对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶点的路径称作哈密顿路径。
  1. 所以为什么不是哈密顿图？
发表于 2018-05-12 22:11:45 回复(4)
zurp头像 zurp
平面图是图中边不相交的图，6个点，11条边，度为3或4，那么2*11=3x + 4（6-x），即x=2，存在这样的平面图？
发表于 2018-04-09 21:28:23 回复(1)
simon_free头像 simon_free

平面图是指可以画在平面上的无向图，即它的所有边都不相交。在平面图中，我们可以将每个顶点看作一个点，并且用直线或折线表示边。

偶图是指具有以下性质的图：对于每一个顶点，其相邻的顶点个数都是偶数。换句话说，每条边都连接两个不同的顶点，并且这两个顶点的度（与之相邻的顶点的个数）都是偶数。

哈密顿图是指包含哈密顿回路的图。哈密顿回路是指从某一个顶点出发，经过所有的顶点一次且仅一次后回到起点的路径。

发表于 2023-11-16 15:10:04 回复(0)
牛客、芒果熊头像 牛客、芒果熊
当然选A了
发表于 2022-11-14 15:29:01 回复(0)
侯卿头像 侯卿
是任何一对不相邻的顶点的度数和不小于顶点总数。不过建议别记了，就算你知道是什么，又不知道***啥的，为什么存在，平时也用不着，那还记***嘛，公司也不至于单单考个定义。
编辑于 2018-04-19 09:49:09 回复(0)
提交观点

问题信息

图
上传者：赞花婆
难度：
12条回答 4555浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号