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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → 离散习题集P198解惑求教 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 6426 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 离散习题集P198解惑求教 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     yinwpnew 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：13
      积分：124
      门派：XML.ORG.CN
      注册：2009/11/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yinwpnew发送一个短消息 把yinwpnew加入好友 查看yinwpnew的个人资料 搜索yinwpnew在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yinwpnew的博客楼主
    发贴心情 离散习题集P198解惑求教

    离散习题集P198第二题的答案为什么说“这样构造的二部图每个顶点的度数都相等”呢，求教啊....

       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/11/24 22:41:00
     
     blueteaxk 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：6
      积分：97
      门派：XML.ORG.CN
      注册：2009/3/14

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给blueteaxk发送一个短消息 把blueteaxk加入好友 查看blueteaxk的个人资料 搜索blueteaxk在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看blueteaxk的博客第2楼
    发贴心情 
    我没有习题集
    说说是书上哪一题吧
    我应该做过的
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/11/25 14:08:00
     
     yinwpnew 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：13
      积分：124
      门派：XML.ORG.CN
      注册：2009/11/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yinwpnew发送一个短消息 把yinwpnew加入好友 查看yinwpnew的个人资料 搜索yinwpnew在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yinwpnew的博客第3楼
    发贴心情 
    题目是：k是正整数，I是kn个元素的集合，证明对于将集合I分成K等份的任何两种划分，一定可以找到一组公共的代表元素。
    后面解答是：设两种划分《A1，A2，A3...A k》、《B1，B2，B3.....Bk》，构造以这些子集为顶点的二部图，如果某元素同时属于Ai与Bj，则在他们之间连一条边。这样构造的二部图每个顶点度数都相等。由HALL定理可知存在完美匹配，也就是一组公共的代表元素。
    不解之处：为什么每个顶点一定是度数相等的泥呢？求教....
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/11/25 15:11:00
     
     blueteaxk 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：6
      积分：97
      门派：XML.ORG.CN
      注册：2009/3/14

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给blueteaxk发送一个短消息 把blueteaxk加入好友 查看blueteaxk的个人资料 搜索blueteaxk在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看blueteaxk的博客第4楼
    发贴心情 
    解答错了吧

    反例：
    设k=3，n=2，I={a,b,c,d,e,f}
    划分1为：A1={a,b}，A2={c,d}，A3={e,f}
    划分2为：B1={a,b}，B2={c,e}，B3={d,f}
    则按解答形成的二部图同时有度数为1和2的顶点

    事实上这题很好证明啊
    按解答构造二部图：
    划分中每个集合做顶点，划分1对应顶点集V1，划分2为顶点集V2，有相同元素则连1条边
    于是对V1的任何一个子集S，设含有x个顶点，即有x个划分1中的集合，共xn个I中元素
    由于V2中任意顶点对应集合只含有n个I中元素，因此xn个元素至少散布在划分2的x个集合中
    即S至少有x个邻居，满足相异性条件
    因此存在完美匹配，得证

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/11/25 22:35:00
     
     yinwpnew 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：13
      积分：124
      门派：XML.ORG.CN
      注册：2009/11/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yinwpnew发送一个短消息 把yinwpnew加入好友 查看yinwpnew的个人资料 搜索yinwpnew在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yinwpnew的博客第5楼
    发贴心情 
    嗯，拜读拜读！！阁下让我受益匪浅啊！！哈哈哈....多谢指教！！多谢指教！！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/11/26 7:15:00
     
     别开天地 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：8
      积分：87
      门派：XML.ORG.CN
      注册：2009/4/2

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给别开天地发送一个短消息 把别开天地加入好友 查看别开天地的个人资料 搜索别开天地在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看别开天地的博客第6楼
    发贴心情 
    看不明白阿
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/11/26 21:19:00
     
     lcswr1987 帅哥哟，离线，有人找我吗？射手座1987-12-10
      
      
      等级：大二(研究汇编)
      文章：31
      积分：214
      门派：XML.ORG.CN
      注册：2009/5/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给lcswr1987发送一个短消息 把lcswr1987加入好友 查看lcswr1987的个人资料 搜索lcswr1987在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看lcswr1987的博客第7楼
    发贴心情 
    书上的答案没有错误吧。。写的挺清楚啊，按照那中方法连边每个点的度数都是n，注意一点就是两个集合之间有几个公共元素就连几条边。得到二部图不一定是简单图。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2009/12/28 23:05:00
     
     sskged 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：55
      门派：XML.ORG.CN
      注册：2009/12/28

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给sskged发送一个短消息 把sskged加入好友 查看sskged的个人资料 搜索sskged在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看sskged的博客第8楼
    发贴心情 
    解答没有错，每个划分中的集合有且仅有k个元素，那么对于任意x属于Ai,必然存在j，使得x属于Bj
    这样，由于Ai中有k个这样的x,所以每个顶点的度数都是k。

    如果每个顶点的度数都一样，都为k，那么二部图必然满足相异性条件。
    否则存在一个顶点集A={A1, A2, A3.. Ap}所关联的的顶点集B={B1, B2, B3,..Bq}且p>q
    这样从A出发的总边数为pk条，由关联性可知，这pk条边都必然连到B上，
    于是pk <= qk,于是p <= q矛盾。
    故正则二部图必然满足婚姻定理。

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

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

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