新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     >>计算机科学论坛<<     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [图论]一道课后题 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 36825 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [图论]一道课后题 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第31楼
    发贴心情 

    晕。
    不可能找到反例的啦。
    这个命题是四色定理的一个特殊情况啊。

    K_5不是平面图（所以K_5的对偶图也不是平面图），所以它不符合命题的前题条件，不是“反例”。：）

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/21 18:48:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第32楼
    发贴心情 
    我按照lalalala的提示和书上Heawood定理的证明过程证了这道题，大家瞅瞅：

    证明：因为一个地图是k-面可这色的当且仅当它的对偶图是k-可着色的，所以只需要证明G*是4-可着色的。

    下面证明G*是4-可着色的：
    若|V（G*）|<=4，显然G*是4-可着色的；
    当|V（G*）|>4时：
    G中存在次数小于等于4的内部面=>G*中存在顶点v，d(v)<=4，
    (1)若与v相邻的顶点色数小于4，则显然G*是4-可着色的；
    (2)若与v相邻的顶点色数等于4，则顺时针方向记这4种颜色为1，2，3，4，其分别对应的与v相邻的顶点记为v1，v2，v3，v4。取H={v1，v3}，然后作如下搜索：
    依次检查H中的顶点，若与其相邻的涂有1，3颜色的顶点不在H中，则将该顶点添加到H中，然后重新对H执行该搜索；直到所有与H中顶点相邻的涂有1，3颜色的顶点都在H中为止。
    则显然p(H)=1或2，
    (2_1)当P(H)=2时，对v1所在的H中的连通分支作如下调整：1换成3，3换成1，此时对v涂1，则G*是4-可着色的；
    (2_2)当p(H)=1时，则H并{v}中必有经过v的1，3组成的圈，且v2，v4必定一个在该圈外，一个在该圈内（由标记时的方法得）。
    设H’={v2，v4}，对H’作如下搜索：
    依次检查H’中的顶点，若与其相邻的涂有2，4颜色的顶点不在H’中，则将该顶点添加到H’中，然后重新对H’执行该搜索；直到所有与H’中顶点相邻的涂有2，4颜色的顶点都在H’中为止。
    则P(H’)=2（因为H’被1，3组成的圈割断了），对v2所在的H’中的连通分支作如下调整：2换成4，4换成2，此时对v涂2，则G*是4-可着色的。

    综上，G*是4-可着色的，故G是4-面可着色的。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/21 21:45:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第33楼
    发贴心情 
    你的证明仍然是基于“G*-v是4可着色的”这一归纳假设呀………
    你这句“若与v相邻的顶点色数等于4，则顺时针方向记这4种颜色为1，2，3，4”暗示除v外，其它顶点都已经完成4着色了。可它们是什么完成的？怎么知道它们必然可以被4着色？
    这又回到了前面讨论的问题………

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/21 22:20:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第34楼
    发贴心情 
    噢，上面的竟然忘了归纳了！再写个：

    证明：因为一个地图是k-面可这色的当且仅当它的对偶图是k-可着色的，所以只需要证明G*是4-可着色的。

    下面证明G*是4-可着色的：
    若|V（G*）|<=4，显然G*是4-可着色的；
    当|V（G*）|>4时：
    假设|V（G*）|=k时，G*是4-可着色的，现证明|V（G*）|=k+1时，G*是4-可着色的：
    G中存在次数小于等于4的内部面=>G*中存在顶点v，d(v)<=4，由于|V（G*-v）|=k，所以G*-v是4可这色的。现在讨论G*：
    (1)若与v相邻的顶点色数小于4，则显然G*是4-可着色的；
    (2)若与v相邻的顶点色数等于4，则顺时针方向记这4种颜色为1，2，3，4，其分别对应的与v相邻的顶点记为v1，v2，v3，v4。则只需要证明v可涂1，2，3，4中某一色即可。
    取H={v1，v3}，然后作如下搜索：
    依次检查H中的顶点，若与其相邻的涂有1，3颜色的顶点不在H中，则将该顶点添加到H中，然后重新对H执行该搜索；直到所有与H中顶点相邻的涂有1，3颜色的顶点都在H中为止。
    则显然p(H)=1或2，
    (2_1)当P(H)=2时，对v1所在的H中的连通分支作如下调整：1换成3，3换成1，此时对v涂1，则G*是4-可着色的；
    (2_2)当p(H)=1时，则H并{v}中必有经过v的1，3组成的圈，且v2，v4必定一个在该圈外，一个在该圈内（由标记时的方法得）。
    设H’={v2，v4}，对H’作如下搜索：
    依次检查H’中的顶点，若与其相邻的涂有2，4颜色的顶点不在H’中，则将该顶点添加到H’中，然后重新对H’执行该搜索；直到所有与H’中顶点相邻的涂有2，4颜色的顶点都在H’中为止。
    则P(H’)=2（因为H’被1，3组成的圈割断了），对v2所在的H’中的连通分支作如下调整：2换成4，4换成2，此时对v涂2，则G*是4-可着色的。

    综上，G*是4-可着色的，故G是4-面可着色的。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/21 22:33:00
     
     chyl 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：12
      积分：120
      门派：XML.ORG.CN
      注册：2006/8/2

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chyl发送一个短消息 把chyl加入好友 查看chyl的个人资料 搜索chyl在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chyl的博客第35楼
    发贴心情 
    啊。。。的确是这样！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/21 23:28:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第36楼
    发贴心情 
    你的证明和前面两位的证明有相同的问题。
    我实在不想说第三遍了。
    我只说一句：你证明中“由于|V（G*-v）|=k，所以G*-v是4可这色的。”不成立。因为无法根据归纳假设和“|V（G*-v）|=k”推出“G*-v是4可着色的”（因为归纳假设是“如果一个简单平面图中有4度以下的顶点，且这个图的阶为k，则这个图是4可着色的”，你现在只知道“G*-v是简单平面图，且阶为k”但不能证明“G*-v中有4度以下的顶点”，所以推不出“G*-v是4可着色的”）。
    具体的讨论见前面的帖子。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 3:09:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第37楼
    发贴心情 关于北大版《离散数学教程》课后习题12.6(2)、12.7(2)的不可证明性
    我今天想了一天这个题：

    首先，若4色猜想成立，则本题显然成立。
    其次，如果这道题的结论成立，对于任意一个图G，取其中某个内部面上的点v，在v所属的内部面内添加两点v1，v2，连接v和v1，v1和v2，v2和v，则vv1v2构成了次数为3的面，此时G是4-面可着色的，将G面着色后再删除v1，v3，则G还是4-面可着色的。

    就得到了下面这个结论：

    本题有解当且仅当4色猜想成立，教材上的习题12.6.(2)，12.7.(2)，小书习题5.1.4(2)，5.1.5(2)，5.1.12成立当且仅当4色猜想成立。且小书习题5.1.4(2)，5.1.5(2)，5.1.12的答案全部错误！

    然后我专门去书店看了下其它教材中关于4色猜想的讲解，很多说道：它在1976年被两个美国人用计算机算出，而其中一本这样说道：美国人计算的是1900种情况，究竟是否有其它情况尚在研究中。可见4色猜想的证明是不严格的，故北大老师在90年后的教材中仍然说4色猜想没被彻底解决。

    汗。。这么大一片错题居然这么多年没被改过来。。。
    发现的人强！


    [此贴子已经被Logician于2006-8-22 22:36:57编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 20:58:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第38楼
    发贴心情 
    嗯。很有道理。

    关于它与4CC等价性的证明，我觉得也可以用对偶图的方法：假如该命题成立，那么任何有度数不超过4的顶点的简单平面图都是4可着色的。对任意简单平面图G*，在任意某个内部面上加入一个新顶点v，把v与该内部面上任意两个顶点相连，则得到的新图H满足题设。从而H是4可着色的，且该着色方案对G同样适用。这就证明了4CC。

    我觉得你可以写信给刘田老师，说明你的发现！：）

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/22 22:35:00
     
     GoogleAdSense天蝎座1984-10-28
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Google AdSense  访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/4/25 0:30:32

    本主题贴数38，分页： [1] [2] [3] [4]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 5,113.037ms