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

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

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

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

    （1）习题11.3：证明多面体图（柏拉图图）有且仅有5种。给点提示吧？
    （2）习题11.6：画出所有6阶连通的简单非同构的非平面图。我算25种，对下答案。
    （3）习题12.5：设G是n阶k-正则图，证明X(G)>=n/(n-k)。小书给出如下证明：
    证明：设v为G中任意一顶点，因为d（v）=k，因而至多有n-k个顶点可以与v涂相同颜色，于是至少需要[n/（n-k）]种颜色给G的顶点着色，所以X(G)>=[n/(n-k)]>=n/(n-k)。
    (其中[x]表示不小于x的最小整数）
    为啥：于是至少需要[n/（n-k）]种颜色给G的顶点着色？


    ps：我第2题的答案是：
    考虑K5：设其顶点顺时针方向依次为：v1，v2，v3，v4，v5
    1。在v1v5中加一点v
    2。在v1v5中加一点v，连接vv3
    3。在v1v5中加一点v，连接vv2
    4。在v1v5中加一点v，连接vv3，vv2
    5。在v1v5中加一点v，连接vv3，vv2，vv4

    6。在v5v2中加一点v
    7。在v5v2中加一点v，连接vv1
    8。在v5v2中加一点v，连接vv4
    9。在v5v2中加一点v，连接vv1，vv4
    10。在v5v2中加一点v，连接vv1，vv4，vv3

    11。在k5外取一点v，连接vv1
    12。在k5外取一点v，连接vv1，vv2
    13。在k5外取一点v，连接vv1，vv3
    14。在k5外取一点v，连接vv1，vv3，vv2
    15。在k5外取一点v，连接vv1，vv3，vv4
    16。在k5外取一点v，连接vv1，vv3，vv4，vv2
    17。在k5外取一点v，连接vv1，vv3，vv4，vv2，vv5，即K6

    考虑k3，3，设其顶点为a1,a2,a3,b1,b2,b3.其中ai与bi间有一条边
    18。K3，3
    19。K3，3，再连接a1a2
    20。K3，3，再连接a1a2，a1a3
    21。K3，3，再连接a1a2，a2a3
    22。K3，3，再连接a1a2，b2b3
    23。K3，3，再连接a1a2，a2a3，b1b2
    24。K3，3，再连接a1a2，a2a3，a1a3
    25。K3，3，再连接a1a2，a1a3，b2b3


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 14:57:00
     
     yangling_1985 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：63
      积分：507
      门派：XML.ORG.CN
      注册：2006/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yangling_1985发送一个短消息 把yangling_1985加入好友 查看yangling_1985的个人资料 搜索yangling_1985在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yangling_1985的博客第2楼
    发贴心情 
    设多面体G的顶点数为n,边数m,面数r，每个面的次数均l ,顶点度数为k.
    由题意，2m=l*r=k*n
    又由欧拉公式，n-m+r=2.代入得，
    2m/k-m+2m/l=2
    1/k+1/l=1/m+1/2
    利用k>=3,l>=3讨论易得l,k至少有一个等于3。(m>0)
    (1)
    若k=3,则
    1/l-1/m=1/6.由m>0.得1/l>1/6,所以l<6,所以3<=l<6,分别对l的取值讨论即可。
    (2)l=3时同理
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 16:02:00
     
     yangling_1985 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：63
      积分：507
      门派：XML.ORG.CN
      注册：2006/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yangling_1985发送一个短消息 把yangling_1985加入好友 查看yangling_1985的个人资料 搜索yangling_1985在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yangling_1985的博客第3楼
    发贴心情 
    （3）因为如果存在图G的k-着色（k<[n/(n-k)]），由于每种颜色至多可以对n-k个顶点着色，则（G中至多有n-k个顶点同色），故有k*(n-k)>=n,又k*(n-k)<[n/(n-k)]*(n-k)<=n。矛盾！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 16:15:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第4楼
    发贴心情 
    明白了。第2个方法真好！多谢杨兄！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 21:01:00
     
     yangling_1985 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：63
      积分：507
      门派：XML.ORG.CN
      注册：2006/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yangling_1985发送一个短消息 把yangling_1985加入好友 查看yangling_1985的个人资料 搜索yangling_1985在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yangling_1985的博客第5楼
    发贴心情 
    不客气！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/26 18:47:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第6楼
    发贴心情 
    第二个错了！答案是17：
    考虑K5：设其顶点顺时针方向依次为：v1，v2，v3，v4，v5
    1。在v1v5中加一点v
    2。在v1v5中加一点v，连接vv3
    3。在v1v5中加一点v，连接vv2
    4。在v1v5中加一点v，连接vv3，vv2
    5。在v1v5中加一点v，连接vv3，vv2，vv4

        在v5v2中加一点v，与1同构
        在v5v2中加一点v，连接vv1，与2同构
        在v5v2中加一点v，连接vv4，与3同构
        在v5v2中加一点v，连接vv1，vv4，与4同构
        在v5v2中加一点v，连接vv1，vv4，vv3，与5同构

    6。在k5外取一点v，连接vv1
    7。在k5外取一点v，连接vv1，vv2
    8。在k5外取一点v，连接vv1，vv3
    9。在k5外取一点v，连接vv1，vv3，vv2
    10。在k5外取一点v，连接vv1，vv3，vv4
    11。在k5外取一点v，连接vv1，vv3，vv4，vv2
    12。在k5外取一点v，连接vv1，vv3，vv4，vv2，vv5，即K6

    考虑k3，3，设其顶点为a1,a2,a3,b1,b2,b3.其中ai与bi间有一条边
    13。K3，3
    14。K3，3，再连接a1a2
    15。K3，3，再连接a1a2，a1a3
          K3，3，再连接a1a2，a2a3，与15同构
    16。K3，3，再连接a1a2，b2b3
           K3，3，再连接a1a2，a2a3，b1b2，与2同构
    17。K3，3，再连接a1a2，a2a3，a1a3
          K3，3，再连接a1a2，a1a3，b2b3，与2同构

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/31 18:36:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第7楼
    发贴心情 
    3楼的方法真妙！！！！这就是图论的精髓所在！！！！我的506577965，有空我们交流一下！ok?

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/19 16:25:00
     
     apolor 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：39
      积分：382
      门派：XML.ORG.CN
      注册：2006/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给apolor发送一个短消息 把apolor加入好友 查看apolor的个人资料 搜索apolor在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看apolor的博客第8楼
    发贴心情 
    （3）习题12.5：设G是n阶k-正则图，证明X(G)>=n/(n-k)。
    证明：因为G是n阶k-正则图，对任意v属于V(G)，d(v)=k，于是G中与v同色顶点至少只有n-k-1个，即G中同色顶点至多只有n-k个。所以(n-k)X(G)>=n。即X(G)>=n/(n-k)。#
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/21 23:31:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/13 8:51:52

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

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