|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 请教两道图论的题，谢谢了！ (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=86500) |
|
-- 作者：jhzhpku1 -- 发布时间：8/29/2010 11:58:00 AM -- 请教两道图论的题，谢谢了！ 1、证明：如果正则简单图G 和补图G 都是连通图，则G 和G 中至少有一个是欧拉图。 2、证明：如果n 阶（n>2）简单图G 中，对于任何0<j<n/2，G 中度数不超过j 的顶点个数都小于j，则G 一定是哈密顿图。 |
|
-- 作者：lisheng -- 发布时间：8/31/2010 2:44:00 AM -- 第一题：不妨设G（n阶）不是欧拉图，那么图G的存在奇度顶点，又由于G为k-正则图，所以G的每个顶点的度数都为奇数，根据握手定理有2m=kn，所以n为偶数，所以G的补图就为n-1-k正则图，n-1-k为偶数，得到G的补图的所有顶点都为偶数的连通图，所以G的补图为欧拉图。 |
|
-- 作者：lisheng -- 发布时间：8/31/2010 2:56:00 AM -- 第二题：用归纳法，在加入新顶点的时候要用到鸽巢定理，这就是条件的利用点。 |
|
-- 作者：jhzhpku1 -- 发布时间：9/1/2010 6:08:00 PM -- 不胜感谢楼上的回复，请问第二题的思路能否在细化明确点？谢谢了！ |
|
-- 作者：lisheng -- 发布时间：9/1/2010 11:19:00 PM -- 你看看课本的哈密顿的的那节的定理证明应该就会了。 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
7,105.469ms |