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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [求助]抽象代数图论难题咨询（非课本上的习题） ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 11198 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [求助]抽象代数图论难题咨询（非课本上的习题） 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客楼主
    发贴心情 [求助]抽象代数图论难题咨询（非课本上的习题）

    抽象代数：

    1.设G为群，H是G的子群。定义H的正规化子N(H) = {g属于G|gHg^-1包含于H}，证明N(H)是G的子群。
    2.设R是一个无非零的幂零元的交换环，r,s属于R。
    证明：如果存在a,b属于N，(a,b) = 1，使得r^a=s^a，r^b=s^b，则r=s。
    3.证明：在一个无零因子环中所以非零元对于加法来说的阶都是一样的。


    图论：

    1.在2n(n>=2)个人的人群中，每人至少有n个朋友，则至少有四人，使得这四人围圆桌而坐时，每人身旁皆是他的两个朋友。
    2.一个旅行团（至少四人）中任4位中至少有一位旅客以前见过另外3个人。证明任意4人中有1人踏早就见过旅行团中其余的每个人。
    3.有14人打麻将，之前每个人都与其中5个人一起同桌打过；规定四人中必须任何两人皆未同桌打过麻将才准许在一起打一局，这样只打了三局即无法继续玩下去，这时进来一位新任，试证这时有了新任参加，一定可以再打一局。
    4.证明：在一群人中，每两个相识者皆无共同的熟人，每两个不相识者恰有两个共同的熟人，则每人都有相同数目的熟人。
    5.证明：直径为d,围长为2d+1的图示正则图。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/19 22:48:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第2楼
    发贴心情 
    大家都帮着看看吧，虽然不是北大课本上的习题，不过用来扩展思维也不错的~也帮我顶一下~拜托了
    抽象代数的题目是华东师大出的一本《近世代数》上的习题，图论是中科大的王树禾的《图论》的课后习题。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/19 22:51: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楼
    发贴心情 
    嗯。都是好题。
    我回头慢慢做。

    代数第1题是个很重要的结论，我记得不少教材上都有这个结论的证明。

    图论第1题比较简单（我记得我做过，好像是北大某年真题？）。
    大体思路如下：任取两个不相邻的顶点a,b，令X=N(a)∪{a}，Y=N(b)∪{b}，则|X|+|Y|≥2n+2，而|X∪Y|≤2n。由容斥定理可知|X∩Y|≥2。从X∩Y取两个顶点c,d。那么 a c b d 就是一个合理的安排。

    图论第5题很难。这个结论来自论文“There is No Irregular Moore Graph”[Robert Singleton, The American Mathematical Monthly, Vol. 75, No. 1. (Jan., 1968), pp. 42-43]，证明方法很巧妙。
    证明分几个小结论：
    1、G中任意一对“对角点”（antipodal vertices）都具有相同的度。即，对任意a,b属于V(G)，如果a与b的距离恰为d，那么a的度数等于b的度数。
    2、如果构造一张“对角点图”T，即，令V(T)=V(G)，对任意a,b属于V(G)，若a与b在G中的距离为d，则把边(a,b)加入E(T)中。那么这个对角点图中任意顶点的度数都不小于2。
    3、这个“对角点图”T是连通图。
    结合结论1和结论3，就可以得到原题的结论。（结论2用来帮助证明结论3）。

    ----------------------------------------------
    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：*.*.*.* 2007/12/20 8:56:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第4楼
    发贴心情 
    代数第1题不好证明gH(g^-1) = H，H非正规子群，也没说G是有限群。
    所以就是证明g^-1属于N(H)也有难度啊～可能我什么地方看漏了

    图论第2题我用归纳法证明了下，感觉可能有问题的。而且觉得有更简洁的方法
    图论第3题想过很久没思路，希望通过顶次数的限制在G的补图中找一个三角形，但没有成功

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第5楼
    发贴心情 
    嗯。是的。
    我翻了一下书，一般的书都是直接定义N(H)={g|gHg^{-1} = H}。这样证明N(H)是子群很容易。这道题把等号改成子集后，就变得麻烦了。需要利用某种性质来证明“gHg^{-1}是H的子集 --> gHg^{-1} = H”。
    我再想想……

    以下是引用chenminyi在2007-12-20 10:16:00的发言：
    代数第1题不好证明gH(g^-1) = H，H非正规子群，也没说G是有限群。
    所以就是证明g^-1属于N(H)也有难度啊～可能我什么地方看漏了

    图论第2题我用归纳法证明了下，感觉可能有问题的。而且觉得有更简洁的方法
    图论第3题想过很久没思路，希望通过顶次数的限制在G的补图中找一个三角形，但没有成功


    ----------------------------------------------
    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：*.*.*.* 2007/12/20 14:17:00
     
     hanshumin 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：37
      积分：238
      门派：XML.ORG.CN
      注册：2007/3/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给hanshumin发送一个短消息 把hanshumin加入好友 查看hanshumin的个人资料 搜索hanshumin在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看hanshumin的博客第6楼
    发贴心情 
    我试试抽象代数里面的第一题吧。
    我认为要证明gHg-1 = H ，只需要构造一个函数，证明这个函数是双射函数，然后根据
    |gHg-1| = |H| 且 gHg-1 属于H  即可得出  gHg-1 = H  ,然后可能按照常规的思路（子群的判定定理）就能证明了。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/20 23:21:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第7楼
    发贴心情 
    今天吃早饭的时候瞎想了第五题，帮看看能不能这样证明，如果可以第二题也可以用类似方法

    首先如意证明G中任意两点均在长度为2d+1的圈上，G中只含2d+1的圈，若u,v∈E(G)且u,w∈E(G)，u,v,w必在长度为2d+1的圈上等结论。
    令d(u)=Δ(G)，即u为度数最大的顶。由G的连通性可知存在v与u相邻。下证d(u)>=d(v)任意r1，r2属于u的邻域，r1与w共长度2d+1的圈C1，r2与w共长度2d+1的圈C2。证明C1与C2的交点不与v相邻，即不可能出现上图所示的情况。
    否则，在圈C1和C2上分别存在两顶t1和t2使得d(v,t1) = d+1 = d(v,t2)，故d(t1,t2) = 2d。所以t1和t2必然相邻。而此时存在圈u r1~t1 t2~r2 u长度 2d-1与围长为2d+1矛盾。所以若存在d(u)个与u相邻的顶就比存在d(u)条经过v的长度2d+1的圈，且任意两圈的交点不与v相邻，所以存在d(u)个点与d(v)相邻，d(v) >= d(u)。由G的连通性可知其它顶的度数也不小于顶u的度数，所以G中每顶度数相同，G为正则图。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/20 23:31:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第8楼
    发贴心情 
    图不知道怎么回事传不上来
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/20 23:34:00
     
     albani 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：89
      积分：500
      门派：XML.ORG.CN
      注册：2007/7/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给albani发送一个短消息 把albani加入好友 查看albani的个人资料 搜索albani在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看albani的博客第9楼
    发贴心情 
    图论第1题，貌似就是个哈密顿图？任意两点的度数之和>=2n

    图论第2题，假设有四个顶点{v1,v2,v3,v4}不存在有一个顶点与其它所有顶点相邻
                    (1)假设v1与其它三个顶点相邻，存在有两个顶点v2，v3不相邻，由假设得存在u与v1不相邻，取v1，v2，v3，u这四个顶点，则没有一个顶点与其它三个顶点相邻，矛盾
                     (2)假设这四个顶点是K4，由假设存在u1不与v1相邻，u2不与v2相邻，u3不与v3相邻，u4不与v4相邻，1）如果有ui全部相同，取v1，v2，v3，u这四个点，矛盾。2）如果ui中有两个不相同，取ui中两个不同的和对应的vi中的两个点，这四个点，矛盾。
                  由(1)(2)得证

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/20 23:48:00
     
     albani 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：89
      积分：500
      门派：XML.ORG.CN
      注册：2007/7/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给albani发送一个短消息 把albani加入好友 查看albani的个人资料 搜索albani在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看albani的博客第10楼
    发贴心情 
    图论第3题，剩下9个人可以打麻将，{1，2，3，4}，{1，5，6，7}，{2，5，8，9}打了三局后，来了个新人10，{3，6，8，10}可以再打一局。

    图论第4题，反证法，假设v,u的人数不相等分别是n,m(假设n>m)
                    （1）假设v,u认识（即相邻），v还与其它n-1个人认识，u还与其它m-1个人认识，n-1和m-1中无相同的人，由于u与n-1中的人都不认识，所以u与n-1中的任一人在m-1中有两个相同的熟人，又因为n-1中的人都与v相邻，所以任意两个n-1中的人在m-1中至少有一个人不同，得到n-1《m-1，矛盾。
                     （2）假设v,u不认识，类似可证

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

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

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