-- 发布时间：11/21/2007 5:44:00 PM
-- 习题12.10 图 4-面可着色问题
此主题相关图片如下：
然后用归纳法证明G*是4-可着色的
请问怎么用归纳法证明..
|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 习题12.10 图 4-面可着色问题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=55780) |
|
-- 作者：gradxixi -- 发布时间：11/21/2007 5:44:00 PM -- 习题12.10 图 4-面可着色问题 此主题相关图片如下：然后用归纳法证明G*是4-可着色的 请问怎么用归纳法证明..
|
|
-- 作者：Logician -- 发布时间：11/21/2007 6:05:00 PM -- 这道题以前版上讨论过很长时间，没有的得出答案 有人甚至给出了“该题等价于4色猜想”的证明 我们去问北大的刘田教授，他说这题是可以证的，但是证明过程很难，他们决定在新版中简化这道题。 到目前为止，我没有看到或想到这题的正确证明，同时建议你先不要管这道题了（因为太难了）…… |
|
-- 作者：gradxixi -- 发布时间：11/21/2007 11:19:00 PM -- 谢谢Logician版主 我昨天的那思路最后发现如果正确则也是可以用来证四色定理.主要是归纳时没有细想.今天发现原来在d(v)=5时就已经有问题了.最后发现如果能够证明同色的必属于同一连通分支则没有问题.. 嗯,我现在决定不管了.. |
|
-- 作者：蝶影 -- 发布时间：11/22/2007 10:54:00 PM --
我证了一下,大概我也没证对吧,那就问一下错在哪好了... 用归纳法证明G是4-面可着色的:设r为G中面数 1.当r=1时,显然G是4-面可着色的. 2.设当r=k时结论成立,即G是4-面可着色的,可以推出G*是4-可着色的 当n=k+1时,G中含有小于等于4的内部面知存在v属于V(G*)中有d(v)<=4,则与v相邻的顶点至多用了3种颜色,因此在四种颜色中总能找到一种给v着色,又V(G*-v)=k,由归纳假设知G*-v是4-可着色的,因此G*是4-可着色的,因为G是简单连通图,G中无环,则G*是连通无桥图,即G*是地图,由定理12.13,得到G**是4-面可着色的.又G连通,由定理11.17知,G**同构于G,因此G是4-面可着色的.
|
|
-- 作者：Logician -- 发布时间：11/23/2007 12:03:00 AM -- "由归纳假设知G*-v是4-可着色的" 这句不对，因为G*-v中未必还有小于等于4的内部面，所以归纳假设没法之间用…… |
|
-- 作者：蝶影 -- 发布时间：11/23/2007 7:14:00 AM --
不是内部面,是顶点啊,因为是相对于G*说的... 当r=k时即n*=k,有G*是4-可着色的 然后当r=k+1时,即n*=k+1时,|V(G*-v)|=k+1-1=k,那么G*-v就是4-可着色的... |
|
-- 作者：Logician -- 发布时间：11/23/2007 11:33:00 AM -- 归纳假设是“若H*为k阶平面图，且H*中有度数小于等于4的顶点，则H*是4-可着色的” 当你从G*中删去了一个度数小于等于4的顶点v后，能否保证G*-v中还有这样的顶点（从而能够使用你的归纳假设）呢？ |
|
-- 作者：蝶影 -- 发布时间：11/23/2007 4:35:00 PM -- 恩,我已经知道错在哪里了.也有人跟我说过了. 谢谢了哦~ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
375.000ms |