计算机科学论坛--06北大曾考题，欧拉图解法中的迷惑和有趣。。。

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → 06北大曾考题，欧拉图解法中的迷惑和有趣。。。

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 37868 个阅读者　　

*	贴子主题： 06北大曾考题，欧拉图解法中的迷惑和有趣。。。	举报打印推荐 IE收藏夹
	本主题类别:

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第11楼

dear logician, 明白了！！！哈哈。。。这样的感觉真好！！！
说实话，这些题目压抑在心头有7、8个月了。
我解释它，可是总会觉得有些不妥。不像高等数学题目！我所做的就是答案！
离散阿，也许是我接触时间不长吧？ :P，我会接受您的建议，仔仔细细的
看书，把书上的每一个定理和习题的证明弄得条理清晰！泾渭分明！
啊，如果我有您的离散水平，那么该有多好啊！！！嘿嘿。。。
对我来说，离散里面最有些隐患的就是用“文字”证明题。
我的第六感觉总以为有些地方出错了。。。可是我无法检测出来，
就像我的pv程序设计。。。:P,
而这些都是考研获得高分的最大的障碍！！！
还有一道关于二部图的问题。。。
题：
在1群人中，说同一方言的人可以直接对话，不说同一方言的人
也可能通过其他人的翻译来间接对话。
下面2个条件等价吗？为什么？
条件1：这群人中任何2人都能直接或间接对话。
条件2：无论怎么样把这群人分成2组，总能在2组中各找出1人，
       这2人能直接对话。
我的思路：(我喜欢将一些抽象的题目，转化为具体的。。:P)
等价意味着，条件1和条件2 可以相互推出。
（a）证明条件1 =〉条件2 。
     条件1，具体点，就是说：不妨设x1,x2,x3...会说l1方言，
     y1,y2,y3...会说l2方言。
     而还有一些人会同时说这2种方言，这些人是：z1,z2,23...
     那么xi  yi 和zi(i=1,2,3...)的在“各自群体中”可以直接对话!!
     xi和yi虽然不能直接对话，根据题意，可以通过zi来间接对话。
     当然，zi可以和xi,yi直接对话，因为他们是翻译（***）。
     下面考虑条件2，主要的是对这个3群人进行分组！分成2组！
     如果zi不存在，即翻译不存在。那么将xi和yi给归1组，
     当然这是最坏的情况，那么条件2就不成立了！
     现在面临的问题就是zi分配在哪1组中？
     现在来考虑上述最坏的情况。
     即：将xi和yi给归1组。
     这样就成了“鸽巢原理”的应用了。
     即zi必须分配给这2个组（巢）中的1个了！
     那么无论怎么分，不妨设将zi分到xi中去，那么zi中任何一个
     都可以和yi中直接对话，因为这是条件1中（***）处的内容！
     当然如果把zi中元素（>=2）分开分配到xi或者yi中去，
     那么条件2当然会成立了，因为就拿zi中元素的来说就可以直接对话了。
     于是条件1 =〉条件2 得证！
（b）证明条件2 =〉条件1 。
     条件2说：无论怎么样把这群人分成2组，总能在2组中各找出1人，
              这2人能直接对话。
     那么在这里，把2组人当作“一个群体”！！
     这样，在这个“一个群体”中，当然就有2人可以直接对话了！
     因为条件2说“总能”在2组中各找出1人，这2人能直接对话。
     于是条件2 =〉条件1 得证！
综上所述，此题的证。
可是我隐隐觉得有些地方似乎不妥，还是我的第六感觉正确呢？
还是我对自己不够自信呢？
还请牛人来指点一二！小弟我怀着尊敬和焦急的心情来等待着。。。:P
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/27 8:36:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第12楼

以下是引用borlong在2006-9-27 8:36:00的发言：
题：
在1群人中，说同一方言的人可以直接对话，不说同一方言的人
也可能通过其他人的翻译来间接对话。
下面2个条件等价吗？为什么？
条件1：这群人中任何2人都能直接或间接对话。
条件2：无论怎么样把这群人分成2组，总能在2组中各找出1人，
        这2人能直接对话。
我的思路：(我喜欢将一些抽象的题目，转化为具体的。。:P)
等价意味着，条件1和条件2 可以相互推出。
（a）证明条件1 =〉条件2 。
      条件1，具体点，就是说：不妨设x1,x2,x3...会说l1方言，
      y1,y2,y3...会说l2方言。
      而还有一些人会同时说这2种方言，这些人是：z1,z2,23...
      那么xi  yi 和zi(i=1,2,3...)的在“各自群体中”可以直接对话!!
      xi和yi虽然不能直接对话，根据题意，可以通过zi来间接对话。
      当然，zi可以和xi,yi直接对话，因为他们是翻译（***）。
      下面考虑条件2，主要的是对这个3群人进行分组！分成2组！
      如果zi不存在，即翻译不存在。那么将xi和yi给归1组，
      当然这是最坏的情况，那么条件2就不成立了！
      现在面临的问题就是zi分配在哪1组中？
      现在来考虑上述最坏的情况。
      即：将xi和yi给归1组。
      这样就成了“鸽巢原理”的应用了。
      即zi必须分配给这2个组（巢）中的1个了！
      那么无论怎么分，不妨设将zi分到xi中去，那么zi中任何一个
      都可以和yi中直接对话，因为这是条件1中（***）处的内容！
      当然如果把zi中元素（>=2）分开分配到xi或者yi中去，
      那么条件2当然会成立了，因为就拿zi中元素的来说就可以直接对话了。
      于是条件1 =〉条件2 得证！
（b）证明条件2 =〉条件1 。
      条件2说：无论怎么样把这群人分成2组，总能在2组中各找出1人，
               这2人能直接对话。
      那么在这里，把2组人当作“一个群体”！！
      这样，在这个“一个群体”中，当然就有2人可以直接对话了！
      因为条件2说“总能”在2组中各找出1人，这2人能直接对话。
      于是条件2 =〉条件1 得证！
综上所述，此题的证。

呵呵。加油！
关于你的证明：
先说（b）部分，什么叫“当作一个群体”？为什么“当然就有2人可以直接对话了”？
我认为你（b）部分的论证非常不充分。
注意（b）部分是要论证：如果已知条件2成立，那么我们可以推知条件1成立。
我看不出你的证明如何能保证这一点。
再来说（a）部分。间接不一定是只经过1个人转译。说不定要由A把语言1译成语言2，B把语言2译成语言3，C把语言3译成语言4，………，对话的另一方只能听语言N……
所以你的证明假定只最多经过一种中间语言的转换，这是不符合题意的。
图论的题，老师总希望你把实际问题转换成图论问题来做，以考察你的图论知识的运用能力。这道题自然也不例外。你可以考虑一下，如何把本题所述的命题“翻译”成图论语言，并用图论的知识和结论去解决它。
关于举例。在证明中举例一定要慎重。除非你能证明你举的例子是具有普遍性的，是适用于所有可能的实例的。否则举例法是不能作为证明方法的。
----------------------------------------------
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

2006/9/27 9:46:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第13楼

在dear logician的精妙的提醒下-----将题目翻译成“图论”来做！
我忽然茅塞顿开！！！我想到了数学建模！哈哈。。。心情真好！
题：
在1群人中，说同一方言的人可以直接对话，不说同一方言的人
也可能通过其他人的翻译来间接对话。
下面2个条件等价吗？为什么？
条件1：这群人中任何2人都能直接或间接对话。
条件2：无论怎么样把这群人分成2组，总能在2组中各找出1人，
       这2人能直接对话。
在dear logician的提醒后。。。
我的思路是：
该题可以等价为：
这1群人当作1些结点，如果可以直接对话，那么在结点之间用线直接相连。
至于间接对话，是通过其他结点相连，即并非直接相连，而是间接相连。
条件1等价为：这些结点组成的图是连通的。因为结点之间若并非直接相连，
             便是间接相连。即结点之间都是可达的。
条件2等价为：无论将该图划分为哪2个区域，这两个区域中至少各自有1个结点
             直接相连。
（a）证明条件1 =〉条件2 。
将该图划分为2个区域，假设这2个区域：G_1,G_2,（G=G_1并G_2）是相互独立的，
即不连通的。则可得出，G不是连通的。与条件1相矛盾。于是得出G_1与G_2至少
至少各自有1个结点直接相连。
于是条件1 =〉条件2 得证！
（b）证明条件2 =〉条件1 。
有条件2知，无论怎么划分为2个区域，不妨设2个区域为：G_1,G_2。
设为G_2={v1}。则|G_2|=1，|G_1|=|G|-1。
根据条件2，G_1中至少有1个结点与v1直接相连。
不妨设与v1直接相连的是G_1中的t1。
那么进行第2次划分，即G_2={v1，t1}，此时，|G_2|=2，|G_1|=|G|-2。
根据条件2，于是在G_1中又存在结点t2与G_2={v1，t1}中的一个结点直接相连。
设为t2，那么按照同样方法，将t2也扩充到G_2中来。。。。依次类推，
直到|G_2|=|G|-1,|G_1|=1 时为止。
于是得出结论，无论怎么划分，这G_1,G_2总是连通的。
即G（G=G_1并G_2）是连通的。即结点之间不是直接相连，就是间接相连。
于是条件2 =〉条件1 得证！
================================
啊！！终于可以暂时的松一口气啦！！
哈哈哈。。。我心情好多了。
dear logician, 如果我的思路没有错，给我1些表扬吧？^__^
在你的提醒下，我好不容易才想到这样的妙招！！

不知道正确与否啊？？？
等待您的指点。。。。。。:p
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/27 16:45:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第14楼

dear logician:您的这些话，我会铭记于心！
================
图论的题，老师总希望你把实际问题转换成图论问题来做，以考察你的图论知识的运用能力。这道题自然也不例外。你可以考虑一下，如何把本题所述的命题“翻译”成图论语言，并用图论的知识和结论去解决它。
关于举例。在证明中举例一定要慎重。除非你能证明你举的例子是具有普遍性的，是适用于所有可能的实例的。否则举例法是不能作为证明方法的。
=====================
希望那么被图论所困惑的brothers，也能好好体会这番话！^___^
对dear logician,感激涕零啊！！！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/27 16:48:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第15楼

你这次的证法很好啊。
思路和表述都很不错的说。
我觉得证明中还有一点小问题：（b）部分的结尾有些奇怪。你说：“于是得出结论，无论怎么划分，这G_1,G_2总是连通的。”这里，“G_1,G_2总是连通的”是什么意思？是说“G_1与G_2间有边”（这本来就是前提，不用证）？还是说“G_1内部和G_2内部都是连通的”（这一结论你并没有清楚地证明出来）？还是说“G_1和G_2的并（即G）是连通的”（这一点你更没有清楚地证明出来）？
你清楚（b）部分要论证的目标吗？要论证的是，如果已知“{V_1,V_2}是V(G)的一个划分，则V_1与V_2间必有边”，那么必有“G连通”。要说明“G连通”，就要按“连通”的定义，证明“G中任何两个顶点间都有通路”。这才是构成V_1和V_2的目的。你试着改改（b）部分，清楚地表明“G中任何两个顶点间都有通路”？
另外想说一下，注意这种“每次加1，最后必将加到|V(G)|”的思路只对V(G)为有限集时有效。在图论题里中，由于教材中只讨论有限图，所以这样用没有问题。但在做集合论和抽代题时就要注意，如果不是已知目标集合“有限”的话，是不可以这样“加”的。

以下是引用borlong在2006-9-27 16:45:00的发言：
在dear logician的精妙的提醒下-----将题目翻译成“图论”来做！
我忽然茅塞顿开！！！我想到了数学建模！哈哈。。。心情真好！
题：
在1群人中，说同一方言的人可以直接对话，不说同一方言的人
也可能通过其他人的翻译来间接对话。
下面2个条件等价吗？为什么？
条件1：这群人中任何2人都能直接或间接对话。
条件2：无论怎么样把这群人分成2组，总能在2组中各找出1人，
        这2人能直接对话。
在dear logician的提醒后。。。
我的思路是：
该题可以等价为：
这1群人当作1些结点，如果可以直接对话，那么在结点之间用线直接相连。
至于间接对话，是通过其他结点相连，即并非直接相连，而是间接相连。
条件1等价为：这些结点组成的图是连通的。因为结点之间若并非直接相连，
              便是间接相连。即结点之间都是可达的。
条件2等价为：无论将该图划分为哪2个区域，这两个区域中至少各自有1个结点
              直接相连。
（a）证明条件1 =〉条件2 。
将该图划分为2个区域，假设这2个区域：G_1,G_2,（G=G_1并G_2）是相互独立的，
即不连通的。则可得出，G不是连通的。与条件1相矛盾。于是得出G_1与G_2至少
至少各自有1个结点直接相连。
于是条件1 =〉条件2 得证！
（b）证明条件2 =〉条件1 。
有条件2知，无论怎么划分为2个区域，不妨设2个区域为：G_1,G_2。
设为G_2={v1}。则|G_2|=1，|G_1|=|G|-1。
根据条件2，G_1中至少有1个结点与v1直接相连。
不妨设与v1直接相连的是G_1中的t1。
那么进行第2次划分，即G_2={v1，t1}，此时，|G_2|=2，|G_1|=|G|-2。
根据条件2，于是在G_1中又存在结点t2与G_2={v1，t1}中的一个结点直接相连。
设为t2，那么按照同样方法，将t2也扩充到G_2中来。。。。依次类推，
直到|G_2|=|G|-1,|G_1|=1 时为止。
于是得出结论，无论怎么划分，这G_1,G_2总是连通的。
即G（G=G_1并G_2）是连通的。即结点之间不是直接相连，就是间接相连。
于是条件2 =〉条件1 得证！
================================
啊！！终于可以暂时的松一口气啦！！
哈哈哈。。。我心情好多了。
dear logician, 如果我的思路没有错，给我1些表扬吧？^__^
在你的提醒下，我好不容易才想到这样的妙招！！

不知道正确与否啊？？？
等待您的指点。。。。。。:p

----------------------------------------------
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

2006/9/28 2:58:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第16楼

dear logician,听你这么说，就表示我的（a），部分正确了阿！
哈哈。。。我太开心了。。。
好的！关于（b）,我来重新证明！
对我来说，文字叙述证明题目还真的很难表达呢！！！ ^___^
==========================
重新证明条件2：
（b）证明条件2 =〉条件1 。
     第一步，将G划分为{V_1,V_2},且V_2={t1},则|V_2|=1，|V_1|=|G|-1。
     根据条件2，于是在V_1中必然存在一结点与V_2中结点直接相连，
     而V_2中只有结点t1，所以，V_1中必然存在一结点（设为u1）与t1相连。
     第二步：在第一步的基础上，扩充V_2={u1,t1},则|V_2|=2，|V_1|=|G|-2。
     于是u1，t1是直接相连的，即V_2中2个结点是连通的。
     根据条件2，于是在V_1中必然存在一结点与V_2中结点直接相连，
     则设V_1中必然存在一结点（设为u2）与V_2中某结点相连。
     于是，V_1中的u2与V_2也是连通的。
     第三步，在第二步的基础上，进一步扩充V_2={u2,u1,t1},
     则|V_2|=3，|V_1|=|G|-3。
     总能在V_1中找到一结点与V_2连通，那么也将其
     扩充到V_2中来，这时， V_2中结点是连通的。
     依次类推，直到|V_2|=|G|-1，|V_1|=1，即直到把|G|-1个结点全都扩充到
     V_2中来，而且V_2中的结点又是连通的，即每个结点都是可达的。
     而此刻V_1中仅存的最后一个结点un,根据条件2，也必然与V_2中的某个
     结点相连。即un与V_2也是连通的。
     此时，也将un扩充到V_2中来，那么{un...u2,u1,t1}=V_2=G.
     而V_2是连通的，则G是连通的。
     即G中每个结点都是可达的，要么直接相连，要么间接相连。
于是条件2 =〉条件1 得证！
=================================
啊！感觉好极了！！！
在dear logician的指点下，感觉自己的思路越来越清晰！！！
哈哈，不知道这次证明结果如何？
还请指点哦。。。。。^______^

以下是引用Logician在2006-9-28 2:58:00的发言：
我觉得证明中还有一点小问题：（b）部分的结尾有些奇怪。你说：“于是得出结论，无论怎么划分，这G_1,G_2总是连通的。”这里，“G_1,G_2总是连通的”是什么意思？是说“G_1与G_2间有边”（这本来就是前提，不用证）？还是说“G_1内部和G_2内部都是连通的”（这一结论你并没有清楚地证明出来）？还是说“G_1和G_2的并（即G）是连通的”（这一点你更没有清楚地证明出来）？
你清楚（b）部分要论证的目标吗？要论证的是，如果已知“{V_1,V_2}是V(G)的一个划分，则V_1与V_2间必有边”，那么必有“G连通”。要说明“G连通”，就要按“连通”的定义，证明“G中任何两个顶点间都有通路”。这才是构成V_1和V_2的目的。你试着改改（b）部分，清楚地表明“G中任何两个顶点间都有通路”？
另外想说一下，注意这种“每次加1，最后必将加到|V(G)|”的思路只对V(G)为有限集时有效。在图论题里中，由于教材中只讨论有限图，所以这样用没有问题。但在做集合论和抽代题时就要注意，如果不是已知目标集合“有限”的话，是不可以这样“加”的。
  [/quote]

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

2006/9/28 12:49:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第17楼

以下是引用borlong在2006-9-28 12:49:00的发言：
（b）证明条件2 =〉条件1 。
      第一步，将G划分为{V_1,V_2},且V_2={t1},则|V_2|=1，|V_1|=|G|-1。
      根据条件2，于是在V_1中必然存在一结点与V_2中结点直接相连，
      而V_2中只有结点t1，所以，V_1中必然存在一结点（设为u1）与t1相连。
      第二步：在第一步的基础上，扩充V_2={u1,t1},则|V_2|=2，|V_1|=|G|-2。
      于是u1，t1是直接相连的，即V_2中2个结点是连通的。
      根据条件2，于是在V_1中必然存在一结点与V_2中结点直接相连，
      则设V_1中必然存在一结点（设为u2）与V_2中某结点相连。
      于是，V_1中的u2与V_2也是连通的。
      第三步，在第二步的基础上，进一步扩充V_2={u2,u1,t1},
      则|V_2|=3，|V_1|=|G|-3。
      总能在V_1中找到一结点与V_2连通，那么也将其
      扩充到V_2中来，这时， V_2中结点是连通的。
      依次类推，直到|V_2|=|G|-1，|V_1|=1，即直到把|G|-1个结点全都扩充到
      V_2中来，而且V_2中的结点又是连通的，即每个结点都是可达的。
      而此刻V_1中仅存的最后一个结点un,根据条件2，也必然与V_2中的某个
      结点相连。即un与V_2也是连通的。
      此时，也将un扩充到V_2中来，那么{un...u2,u1,t1}=V_2=G.
      而V_2是连通的，则G是连通的。
      即G中每个结点都是可达的，要么直接相连，要么间接相连。
于是条件2 =〉条件1 得证！
=================================

思路是对的。
但表述上还有点问题。
首先，术语要按照定义去使用。术语使用上的混乱会导致思维的混乱。“连通”一词是用于一个图的，是说一个图中任意两个顶点之间都有通路。如果你要表示其它与“相连”“连接”有关的意思，就要换一个词，以免产生歧义。
你的证明中提到“u2与V_2也是连通的”，“un与V_2也是连通的”。这里的“连通”就已经造成了混乱。一方面，如果把这个“连通”解释成“u2与V_2中的某个顶点有边”，那么这话没有问题（但不应使用“连通”这个词）。另一方面，如果把这个“连通”解释成“由{u2}∪V_2生成的子图是连通图”（这正是需要证明的结论），那么你的论证又不充分（要证明{u2}∪V_2生成的子图是连通的，就要说明{u2}∪V_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

2006/9/28 14:03:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第18楼

dear logician, 你真的好厉害阿！一眼就看出了我的问题所在！！
实不相瞒，我对离散的强行定义的概念，天生就有反感！
所以，学离散的时候都是根据自己的思路去学习的。
现在我一定要好好的改掉这个坏习惯！！ ^___^
我会多多练习文字证明题的。
==========================
证明条件2：

（用严格的离散概念：可“可达”“有通路”来替代上述混乱的“连通”概念，
  直到V_2扩充到全部结点时候，才将可达换成了连通。
  因为如您所说，连通是用于一个图的术语。^___^）
（b）证明条件2 =〉条件1 。
     将一群人当作一些结点的集合，设为G={u1,u2,u3...un}
     第一步，将G划分为{V_1,V_2},且V_2={u1},则|V_2|=1，|V_1|=|G|-1。
     根据条件2，于是在V_1中必然存在一结点与V_2中某结点之间有边，
     而V_2中只有结点u1，所以，V_1中必然存在一结点（设为u2）与u1有边。
     则u2与u1两结点是可达，即该两结之间有通路。
     第二步：在第一步的基础上，扩充V_2={u2,u1},则|V_2|=2，|V_1|=|G|-2。
     根据第一步可知，V_2的结点之间是可达的。
     根据条件2，于是在V_1中必然存在一结点（设为u3）与V_2中某结点之间有边，
     则u3与V_2中某一结点之间有通路，即可达。

     第三步，在第二步的基础上，进一步扩充V_2={u3,u2,u1},
     根据第二步可知，V_2的结点之间是可达的。
     则|V_2|=3，|V_1|=|G|-3。
     总能在V_1中找到一结点与V_2中某结点之间有边，那么也将其
     扩充到V_2中来，这时， V_2中结点之间亦是可达的。
     依次类推，直到|V_2|=|G|-1，|V_1|=1，即直到把|G|-1个结点全都扩充到
     V_2中来，而且V_2中的结点又是可达的，即V_2中每个结点之间都有通路。
     而此刻V_1中仅存的最后一个结点un,根据条件2，un也必然与V_2中的某个
     结点有边。即un与V_2中某结点之间有通路。
     此时，也将un扩充到V_2中来，那么{un...u2,u1}=V_2=G.
     而V_2中每个结点之间是可达的，即G中每个结点都是可达的，则G是连通的。

    于是条件2 =〉条件1 得证！
=================================
哈哈，不知道这次证明结果如何？
dear logician，感谢您一直的悉心指点啊！！！！  ^____^
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/29 9:52:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第19楼

又是一题文字叙述证明题。
题：
G是有限的Abel群。
若G中除了两个平凡群外，不再含有其他的正规子群，则称G为单群。
证明：G为单群的充要条件是G的阶为质数。
我的思路（好像有些循环论证的味道。。。^__^）：
本题证明： G为单群  <==>  G的阶为质数。
------------------------------------------
(a),证明 G的阶为质数 ==> G为单群 .
G的阶为质数,根据拉格朗日定理，则G不含有子群。（除两个平凡子群）
当然，不含其他的正规子群。
所以，G是单群。
G的阶为质数 ==> G为单群  获证。
------------------------------------------
（这部分证明，我不敢确定。因为正规子群和Abel群的规则都没有用上。心虚阿。。^__^）
（b）,  G为单群 ==> G的阶为质数
因为是单群，没有其他任何正规子群，所以G的阶为质数，否则。。。

实在证不下去了！
因为正规子群和Abel群的规则都没有用上啊！！！
天啊！！！
是我没有领悟到题意，还是这道题有问题啊？？？
请牛人给点建议！！！！ ^____^
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/29 17:34:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第20楼

以下是引用borlong在2006-9-29 17:34:00的发言：
又是一题文字叙述证明题。
题：
G是有限的Abel群。
若G中除了两个平凡群外，不再含有其他的正规子群，则称G为单群。
证明：G为单群的充要条件是G的阶为质数。
我的思路（好像有些循环论证的味道。。。^__^）：
本题证明： G为单群  <==>  G的阶为质数。
------------------------------------------
(a),证明 G的阶为质数 ==> G为单群 .
G的阶为质数,根据拉格朗日定理，则G不含有子群。（除两个平凡子群）
当然，不含其他的正规子群。
所以，G是单群。
G的阶为质数 ==> G为单群  获证。
------------------------------------------
（这部分证明，我不敢确定。因为正规子群和Abel群的规则都没有用上。心虚阿。。^__^）
（b）,  G为单群 ==> G的阶为质数
因为是单群，没有其他任何正规子群，所以G的阶为质数，否则。。。

（a）部分是对的。但表述不对。平凡子群也是子群啊。怎么能说“G不含有子群”？只能说“G不含非平凡的子群”或者说“G只有平凡的子群”。
（b）部分。看这里吧 http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=29548
离散真题和大部分教材习题这里都有解答。你不会做的先看看这个，还有疑问的再来问。
----------------------------------------------
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

2006/9/29 21:15:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2026/3/29 14:23:33

本主题贴数50，分页： [1] [2] [3] [4] [5]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	156.250ms