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

    >> 研友的交流园地,讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛计算机理论与工程『 计算机考研交流 』 → 06年图论的两个题 查看新帖用户列表

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 27649 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子 浏览下一篇主题
     * 贴子主题: 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/3/28 14:07:20

    本主题贴数14,分页: [1] [2]

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