网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
离散数学吧 关注：10,429贴子：29,617
  • 12回复贴，共1页

设G是有n个结点的简单图,其最小度大于等于（n+q)/2

证明：G中存在包含任意q条互不相邻边的哈密顿回路
答案是把q条边看作一个点得到G‘为哈密顿图，但是展开为什么还是哈密顿图啊？
万一合并点的相邻点只与展开后两点中的同一点相邻怎么办？求详细解释


这道题正确的做法是什么？不会。。。求教！


有没有大神帮忙证明一下


求答案


求教！


将原来q条边看成是q个点，加到G中
得到G‘，共有n+q个点
之后证明G’是H-图即可


给出一个解答
我们将 q 条互不相邻的边新建节点,将原图中那些边断开,每个端点连向对应的新建节点变成新图 G'
那么我们只需要证明 G' 有哈密顿回路即可
我们只需要证明 G' 的闭合图 C(G') 有哈密顿回路即可
而这个闭合图是由一个 V 的完全图加上新建节点对应的边够成的.
这个图上有哈密顿回路是显然的. 这也就证明了,对于任意 q 个互不相邻的边,总有一个 G 的哈密顿包含他们.
证明完毕.


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 12回复贴，共1页
分享到: