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

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

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

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

    图论第3题的证明不能让人信服，你只是举出了一个例子，没有证明必然性～
    而且我觉得14人能够打三局这个也是题目要求你证明的～
    即图的补图存在3个K4
    第4题我昨天想到的证明思路和你的一样～
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/21 15:09:00
     
     albani 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：89
      积分：500
      门派：XML.ORG.CN
      注册：2007/7/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给albani发送一个短消息 把albani加入好友 查看albani的个人资料 搜索albani在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看albani的博客第12楼
    发贴心情 
    图论第3题得再好好看看，我也只能举个例子。

    抽象代数第3题，（1）如果G中的元素关于加法都是无限阶肯定都相等。
                           （2）如果G中有关于加法非无限阶的非零元素，任意非零x,y，假设它们的阶分别是n,m，则0=nxy=x(ny)，由无零因子得到ny=0，m|n，同理得0=x(my)=mxy,得mx=0，m|n,所以m=n。

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第13楼
    发贴心情 
    对于无限集，无法由“|gHg-1| = |H| 且 gHg-1 属于H”推出gHg-1 = H

    以下是引用hanshumin在2007-12-20 23:21:00的发言：
    我试试抽象代数里面的第一题吧。
    我认为要证明gHg-1 = H ，只需要构造一个函数，证明这个函数是双射函数，然后根据
    |gHg-1| = |H| 且 gHg-1 属于H  即可得出  gHg-1 = H  ,然后可能按照常规的思路（子群的判定定理）就能证明了。


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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第14楼
    发贴心情 
    “首先如意证明G中任意两点均在长度为2d+1的圈上，G中只含2d+1的圈，若u,v∈E(G)且u,w∈E(G)，u,v,w必在长度为2d+1的圈上等结论。”
    这几个结论你怎么证的？“如意证明”是什么意思？

    以下是引用chenminyi在2007-12-20 23:31:00的发言：
    今天吃早饭的时候瞎想了第五题，帮看看能不能这样证明，如果可以第二题也可以用类似方法

    首先如意证明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为正则图。



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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第15楼
    发贴心情 
    图论第1题，是哈密顿图也不能证明题目所要求的情况成立。题目要证“存在长为4的圈”。G是哈密顿图只表明“存在长为2n的圈”。当n>2时，后者不能推出前者。

    以下是引用albani在2007-12-20 23:48:00的发言：
    图论第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)得证


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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第16楼
    发贴心情 
    以下是引用albani在2007-12-21 18:37:00的发言：
    图论第3题得再好好看看，我也只能举个例子。

    抽象代数第3题，（1）如果G中的元素关于加法都是无限阶肯定都相等。
                            （2）如果G中有关于加法非无限阶的非零元素，任意非零x,y，假设它们的阶分别是n,m，则0=nxy=x(ny)，由无零因子得到ny=0，m|n，同理得0=x(my)=mxy,得mx=0，m|n,所以m=n。


    我当时主要的问题就是nxy = x(ny),因为n是自然数因此不是环中元素不能用交换律，现在看来没问题的，可以用分配率，呵呵～谢谢albani

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第17楼
    发贴心情 
    以下是引用Logician在2007-12-22 11:39:00的发言：
    “首先如意证明G中任意两点均在长度为2d+1的圈上，G中只含2d+1的圈，若u,v∈E(G)且u,w∈E(G)，u,v,w必在长度为2d+1的圈上等结论。”
    这几个结论你怎么证的？“如意证明”是什么意思？

    不好意思，字打错了。是“容易证明”证明如下：

    命题1：任意G上的圈，此圈长度一定是2d+1
         这个不难证明。（圈长大于等于围长，对角点的距离小于等于直径）

    命题2：任意顶u,v属于G，u,v必在长度为2d+1的圈上。
         因为G围长为2d+1，故G至少存在一个2d+1的圈C1。又G直径为d，故G是连通的，任意顶u不属于C1，存在到C1上某顶v的路径。在C1中，与v相对的顶w，满足d(v,w) = d，另一条从v到w的路径长d+1，如此可证明d(u,w)>d，因此由直径为d可知必存在从u到w的另一条路径，这样就又构成了一个圈C2，由命题1可知C2的长度也是2d+1。如此这般，不断构造新的圈将不在圈上的顶包含进来，故所有顶都在长度为2d+1的圈上。
          因此对于G中任意两点v1,v2。v1必在长2d+1的某圈Cx上，又由G的连通性可知必存在从v2到Cx上某顶的路径。可按照上面的方法构造出新的圈Cy。这样一来v1,v2就在一个由Cx的一部分和Cy的一部分构成的另一个圈上Cz。由命题1可知Cz长度为2d+1。

    命题3：任意u,v,w属于G，若(v,w)属于E(G)且(w,u)属于E(G)，则e(v,w)和e(w,u)在长度为2d+1的圈上。
         由命题2可知G中无桥，所以对于任意(v,w)属于E(G)且(w,u)属于E(G)，必存在另一条u到v的路径，这样e(v,w)和e(w,u)必在某圈上Ct上，由命题1可知Ct的长度为2d+1

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

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

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