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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 计算机考研交流 』 → 06年图论的两个题 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 28571 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 06年图论的两个题 举报  打印  推荐  IE收藏夹 
       本主题类别: 试题    
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客楼主
    发贴心情 06年图论的两个题

    似乎很难说清道理，大家讨论一下：

    4.(10分)设k是给定正整数,由k个圈组成一个(有向或无向)图,要添加最少数量的边使之成为欧拉图,设这样添加的边数为t,问t的最大值是多少?为什么?

    5.(10分)给极小非平面图顶点着色，
    （1）至少需要几种颜色，为什么？
    （2）至多需要几种颜色，为什么？


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/19 19:04:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第2楼
    发贴心情 
    4.我觉得是就是k个吧,取到k得值时,k个圈不想连通.
    可以证明其他情况下添加边得数目可以较少.例如两个圈相交时.
    另外需要证明,对某种情况,添加得为一个圈,因为欧拉图是圈得并.

    5.最少情况为2,因为k3,3需要至少两种颜色.
    最多得情况最少应该是5,因为k5是极小,所有>=5
    同时因为极小非平面图去掉一条边为地图,可以4着色,设图G-{e}可以4着色,则给e得两个端点添加一种其他颜色,则可实现着色.

    又全部得题吗?共享一下吧,谢谢:)

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第3楼
    发贴心情 
    4. 首先，我不确定“由k个圈组成”，是否就是指“k个边不重的圈的并”。我认为是的，而且如果不是，这个题我就不知道该怎么做了。下面先在假定它是的情况下做：
        显然，如果图中有s个连通分支，则至少要s-1条边才能使之重新连通。但这时，必然存在奇数度顶点（这是因为，在加入这s-1条边前，G中所有顶点都是偶数度。新加入的这s-1条边会使总度数增加2s-2，而总共有s个连通分支，由鸽巢原理知，存在某个连通分支p_i，使得p_i的顶点度数和至多只增加1，另一方面，因为这s-1条边连接了所有连通分支，所以p_i的顶点度数至少增加1.这就是说，p_i中有一个顶点成为了奇数度），从而不会是欧拉图。
        另一方面，按如下方式向图中添加s个边：从s个连通分支中各取一个顶点，分别记为v_1,v_2,...,v_s，则加入边(v_1,v_2),(v_2,v_3),...,(v_{s-1},v_s),(v_s,v_1)。易见，加入的边构成一个圈，从而新图G'是若干个边不重的圈的并，且是连通的。
        这就是说，所需添加的边数t即为连通分支数，而有k个圈时，连通分支数至多为k，所以t的最大值是k。

    5.
    (1) 最少2种。因为：首先，1色图显然都是平面图，所以不可能有点色数为1的极小非平面图。另一方面，存在极小非平面的2部图（如K_{3,3}），而2部图是2-可着色的。从而存在2色的极小非平面图。这就是说，任意极小非平面图最少需要用2种颜色进行着色。
    (2) 最多5种。因为：首先，设G为任意极小非平面图，e=(u,v)为G的任意边，令H=G-e。由4色定理，可以对H进行4着色。此时，若u和v同色，则给u着第5种颜色。这样的着色方案显然是对G的一种可行的着色。从而任意极小非平面图都是5-可着色的。另一方面，K_5就是一个点色数为5的极小非平面图。从而“5”就是所求的最大值。


    [此贴子已经被作者于2006-7-20 20:30:09编辑过]

    ----------------------------------------------
    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/7/20 16:12:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第4楼
    发贴心情 
    感谢Supremgoooo的提醒，第5题可以不用4CC，而用教材上给出了证明的5色定理来做：
        设G为任意极小非平面图，e=(u,v)为G的任意边，令H=G-e。由教材定理11.10可知，|E(G)|=|E(H)|+1<=3n-5<3n。从而G中必然存在度数小于等于5的顶点v。
        令G_1=G-v，显然，G_1是平面图。由5色定理可知，它是5-可着色的。对G_1进行5着色，下面证明，把G_1还原成G时，v是可着色的。（下面照抄教材中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/7/20 16:58:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第5楼
    发贴心情 
    恩,有道理
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/20 18:32:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

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

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/27 18:39:00
     
     yourwk 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：5
      积分：134
      门派：XML.ORG.CN
      注册：2006/5/25

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第8楼
    发贴心情 
    其实已经证明了……
    不过因为北大的教材上没有，所以参加北大的考试时最好不用就是了。

    ----------------------------------------------
    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 23:09:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第9楼
    发贴心情 
    最少边的最大值？？？？这么绕口的命题怎么解释呀？？？通俗点，怎么说呢？

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/2 17:33:00
     
     lilylily 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：6
      积分：84
      门派：XML.ORG.CN
      注册：2006/9/1

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给lilylily发送一个短消息 把lilylily加入好友 查看lilylily的个人资料 搜索lilylily在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看lilylily的博客第10楼
    发贴心情 
    那楼主肯定有2006年数学基础的真题了？！
    能不能给我发一份
    油箱：lily830307@sina.com

    急需，谢谢

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

    本主题贴数14，分页： [1] [2]

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