离散数学，判断哈密顿通路的问题
图论中有一条定理如下：设G是n阶无向简单图，若对于G中任意不相邻的顶点u、v，均有d(u)+d(v)>=n-1则G中存在哈密顿通路。可是图中的这个哈密顿图明显就不满足上面...
图论中有一条定理如下：设G是n阶无向简单图，若对于G中任意不相邻的顶点u、v，均有 d(u)+d(v)>=n-1则G中存在哈密顿通路。可是图中的这个哈密顿图明显就不满足上面的公式啊？还是我哪里理解错了？
展开
展开全部
设G是n阶无向简单图，若对于G中任意不相邻的顶点u、v，均有
d(u)+d(v)>=n-1
则G中存在哈密顿通路
这个没错，但请注意：
这个条件只是充分条件
不是必要条件
也就是说
满足该条件一定存在哈密顿通路
但不满足该条件不一定不存在哈密顿通路
d(u)+d(v)>=n-1
则G中存在哈密顿通路
这个没错，但请注意：
这个条件只是充分条件
不是必要条件
也就是说
满足该条件一定存在哈密顿通路
但不满足该条件不一定不存在哈密顿通路
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
