题：设k是给定正整数,由k个圈组成一个(有向或无向)图,要添加最少数量的边使之成为欧拉图,设这样添加的边数为t,问t的最大值是多少?为什么?

我的思路：假设如果有2个圈，不重合，加上最少的边成为欧拉图，即在这2个圈中的每个圈的某同一个点上加2条“平行边”。因为圈中每个点的度数是2，已经符合欧拉图的条件，
必须加上2条平行边，这样才能使之符合欧拉图的条件。

于是，可以想象,k个圈可以假设成k个点，要是k个独立点成为图！那么“最少”必须加上(k-1)条边才能使之连通，可是！！！还要补上“平行边”，使之满足欧拉图条件，于是加上了2*（k-1）条边！！！

即 添加最少的2*（k-1）条边，可以成为欧拉图！！！

但是！！！为什么题目要问：最少边的最大值呢？？？！！！
最大值指的到底是什么意思啊？？？
我非常不理解！
难道是小弟对题目的意思没有弄明白？还是我的知识不够呢？

还请牛人给小弟指点指点！不胜感激！

但是！
该题目中， 所谓的“最小值”，“最大值”指的是到底是什么？？？

我的理解：最小值，即要求在k个圈中加上最少的边！
既然如此，最小边最大值应该是没有意义的啊！！！
因为假设正确答案是k，那么还有比k更大的值啊！！！不是吗？
那么最大值又该作何理解呢？？？

看来小弟的语文还要好好的学学吧？ ：P

例1 对某个特定的国家G，令t(G)为该国家收入最高的人的月收入。问，在全世界（或全亚洲）所有的国家G_1,G_2,...,G_n中，哪个国家对应的t(G_i)最小。
例2  令S={X | X∈P(N)，即，X为自然数集N的一个子集}，定义函数f:P(N) -> N，对任意X∈P(N)，f(X)为X中最大的数，问，S中哪个元素X_i使f(X_i)最小？
例3 你每天上班，都选择最省时间的交通方式。但由于一些不确定因素（堵车、班车发车间隔、红绿灯等），使得每天上班的实际耗时有所不同。问，在最坏情况下（最倒霉的一天），耗时会是多少？
例4 某班有50个学生，对每个学生X_i，以其历史成绩中的最低分作为该学生的“有效分”。问哪位学生的“有效分”最高？

核心观点是：S是集合的集合，X_i是S的元素，但X_i也是集合。用X_i中的最小元素来给这个X_i“打分”，问S哪个X_i的分最高？

尤其是这个例3，通俗易懂！

那么在本题目中，最小值是指加上最少的边！  即，可以有很多种方法加上最少的边！！而在这些方法中又一个是边数最多的！！即最大值！！

我的理解正确不？？？？    ：P

还有这道题：

给极小非平面图顶点着色，
（1）至少需要几种颜色，为什么？
（2）至多需要几种颜色，为什么？

我的解法：

极小非平面图最大指平面图上加上1条边，使之成为极小非平面！
由于极小非平面的定点数目〉=5，（因为<=4均是平面图，而k5是非平面图）
立刻联想到k3,3是极小非平面图，可以用2-色。
那么还有1-色的极小非平面图吗？
没有了！否则，该图不是连通的！
于是得出结论，最小的色数是2！！！！
即，至少用2种颜色！！！
呜呜----可是这个证明我总觉得有点问题！也许是来自于文字的叙述吧！毕竟
不是数学表达式的严格证明！！！

然而更可怕是下面的：至多需要几种颜色？
因为有平面图的四色定理的存在和五色定理的存在！
这些定理将直接影响到本题的证明！
（a）因为如果四色定理可以用！那么至多是五色！因为将极小非平面图中
暂且拿掉一个点，变成平面图，用四色，然后再补上刚才拿掉的那点用
另外一种颜色！即五色！！！！
(b),如果五色定理可以用！那么至多是六色!!!证明如上！
呜呜-----到底该选择哪个定理呢？？？？
郁闷！无奈！！

请牛人来指点小弟啊！！！急切期待！！！
：P

不正确……
对于一个给定的图、确定的图，假设有一种方法能加3条边使它变成欧拉图，而不存在哪种方法能只加1条、2条或不加边就使它变成欧拉图，那么对这个图，t就是3。
注意，要把t看成是图G的“函数”。对不同的G，t的取值不同，但对同一个G，t的取值是一定的，这个值就是最少需要添加的边数（无论你用什么方法都不可能更少了）。
这就是“最少”的概念。
那么最多呢？因为“由k条个圈组成的图”不是一个图，而是一类图。对任何给定的k，你都可以写成无数个不同的图G_1,G_2,G_3,...它们都是由k个圈组成的。比如，G_1可能是k个圈连在一起的，是个连通图，那么对于G_1来说，t的值（不妨写成t(G_1)）就是0，因为G_1本来就是连通图。而G_2可能是k个两两不相交的圈构成的，它有k个连通分支。前面已经论证了，对这种情况t(G_2)=k，必须加k条边才行。
问的问题是：对于一个给定的k，设S={G_1,G_2,G_3,....}是那些由k个圈组成的图的集合（注意，S里有无数个图！每个图都是不同的，但每个图都可以表成某k个不相交的圈的并！），令T={t(G_1),t(G_2),t(G_3),...}，那么T是自然数的一个子集，问T中最大的自然数是什么。

要证完这道题，必须证明两件事，对每一个自然数k：
1、设G为任意一个由k个圈组成的图（再次强调：“由k个圈组成的图”可以有无数个！每个图对应的t是不同的！），无论G是什么样的结构，把G变成欧拉图的最佳方案（边数最少的方案）所添加的边都不超过k条（如果你非要使用“烂方案”，当然可以加任意多条边，而不止k条）。
2、确实存在某个由k个圈组成的图H，使得t(H)=k。即，必须在H中加上k条边才能使H变成欧拉图，少加一条都不可能成功。

与“例3”类比，对每一个月份M：
1、设D为M月的一个工作日（M月当然有不只一个工作日，每个工作日的交通情况不同），你需要证明，无论这一天你的运气有多差，你去公司的最佳方案耗时都不超过X分钟（前提是你已经根据D这一天的条件，选择了最佳方案，如果你非要在路上闲逛，你当然有可能一辈子也到不了公司）。
2、M月确实存在某个工作日N，使得在M月N日，即便是最佳方案，也得花去X分钟，想找到比X分钟更快的方案是不可能的。

明白了吗？核心内容：集合的集合（即，大集合）是“所有能表示成k个边不重的圈的并的图”（“由k个圈组成”和“能表示成k个边不重的圈的并”是同一个意思，重点是：没有指明是哪k个圈，不同的k个圈拼出来的图当然可以有很大的不同），大集合的元素（小集合）是对某一个特定的图G，把G变成欧拉图的各种不同方案所需添加的不同边数。

参见 http://www.ieee.org.cn/dispbbs.asp?BoardID=67&replyID=52401&id=35822&star=1&skin=0

关于最少几色，你的论证没有问题。
你两个方面都考虑到了：
1、不可能是1色（因为1色图无边，肯定是平面图），从而下限至少是2。
2、确实有2色的极小非平面图K_{3,3,}。从而下限至多是2。
这就得到了“下限等于2”的结论。

关于最多几色，我前面给你的链接中已经给出了用五色定理证明上限不超过5的证法。
但你的论述中少了“上限最少是5”的论证（即，没有给出色数为5的极小非平面图的例子），从而即便说明了“上限不超过5”，也没有排除“上限是4”这样的可能性。所以论证不完整。

讨论上下限的题，如果可能，都要论证两方面，一方面是这个限制确实是有效的（没有例子能突破它），另一方面是这个限制确实是“最优的”（不可能有比它更“紧”的限制了）。

比如这道考题，如果我宣称：极小非平图图色数不可能小于0，也不可能大于100。那么我的宣称也是成立的，0和100也确实分别是极小非平图的色数下界和上界，但它们不是“紧”下/上界。用集合论的话说，它们是下界和上界，但不是下确界和上确界。所以这种结果是不够好的。

仔仔细细、反反复复阅读了你的贴后，我的理解是：
K个圈可以组成1类图，这类图中，每个图都可以加上“最少”的边
使之成为欧拉图！！！假设每个图加上“最少”的边数是X1,X2,X3...
然而，在这些X1,X2,X3...“最少”边数中，必有一个是“最大”的值！
而我们求得就是这个最大值！！！

我的理解正确吗？？
我是否很可爱啊？不好意思，我的图论部分的确很薄弱！！！
让Dear Logician ,见笑啦啊！

==================================================

“由k条个圈组成的图”不是一个图，而是一类图。
---------------------------------------------我懂了！！！
每个图都可以表成某k个不相交的圈的并！
---------------------------------------------不怎么懂！！！
假设有3=k个圈，那么你的G_1,G_2等等所指的是什么图呢？能否具体点。
因为这里实在是太抽象了，我无法“画”一些图来模拟啊！
我想着在考试中应该是个不小的困境吧！！！

============================
dear logician 国庆和中秋快来了，望你一切顺心哦！！
非常感谢！！

==================================================
“每个图都可以表成某k个不相交的圈的并！”
这是解释前一句话啊。
我说“G是3个圈组成的”和我说“G可以表成3个不相交的圈的并”，不是一回事吗？
要不你怎么理解“组成”二字？

要举例子吗？
例1  令C_1=v_1v_2v_3v_1，C_2=v_4v_5v_6v_4，C_3=v_7v_8v_9v_7。
那么C_1,C_2,C_3是三个不相交（没有公共顶点）的圈。它们的并就是一个9顶点的图，这个图不就是“由3个圈组成的图”吗？同样结构的图有无数个（我让其中某个或某几个圈“大”一些，即，含有更多的顶点，但仍不相交，即可）。
例2  令C_1=v_1v_2v_3v_1，C_2=v_1v_4v_5v_6v_1，C_3=v_7v_8v_9v_7。
那么C_1和C_2是相交的圈。C_3与C_1,C_2不相交。它们的并也是一个9顶点的图。但这个图只有两个连通支。

还需要我接着举吗？

建议多看看书上的例子，做一些习题，培养一下对图论的感觉。

啊，如果我有您的离散水平，那么该有多好啊！！！嘿嘿。。。

对我来说，离散里面最有些隐患的就是用“文字”证明题。
我的第六感觉总以为有些地方出错了。。。可是我无法检测出来，
就像我的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

呵呵。加油！

关于你的证明：

先说（b）部分，什么叫“当作一个群体”？为什么“当然就有2人可以直接对话了”？
我认为你（b）部分的论证非常不充分。
注意（b）部分是要论证：如果已知条件2成立，那么我们可以推知条件1成立。
我看不出你的证明如何能保证这一点。

再来说（a）部分。间接不一定是只经过1个人转译。说不定要由A把语言1译成语言2，B把语言2译成语言3，C把语言3译成语言4，………，对话的另一方只能听语言N……
所以你的证明假定只最多经过一种中间语言的转换，这是不符合题意的。

图论的题，老师总希望你把实际问题转换成图论问题来做，以考察你的图论知识的运用能力。这道题自然也不例外。你可以考虑一下，如何把本题所述的命题“翻译”成图论语言，并用图论的知识和结论去解决它。

关于举例。在证明中举例一定要慎重。除非你能证明你举的例子是具有普遍性的，是适用于所有可能的实例的。否则举例法是不能作为证明方法的。

题：
在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

================
图论的题，老师总希望你把实际问题转换成图论问题来做，以考察你的图论知识的运用能力。这道题自然也不例外。你可以考虑一下，如何把本题所述的命题“翻译”成图论语言，并用图论的知识和结论去解决它。

关于举例。在证明中举例一定要慎重。除非你能证明你举的例子是具有普遍性的，是适用于所有可能的实例的。否则举例法是不能作为证明方法的。
=====================

希望那么被图论所困惑的brothers，也能好好体会这番话！^___^
对dear logician,感激涕零啊！！！

我觉得证明中还有一点小问题：（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

好的！关于（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]

思路是对的。
但表述上还有点问题。

首先，术语要按照定义去使用。术语使用上的混乱会导致思维的混乱。“连通”一词是用于一个图的，是说一个图中任意两个顶点之间都有通路。如果你要表示其它与“相连”“连接”有关的意思，就要换一个词，以免产生歧义。

你的证明中提到“u2与V_2也是连通的”，“un与V_2也是连通的”。这里的“连通”就已经造成了混乱。一方面，如果把这个“连通”解释成“u2与V_2中的某个顶点有边”，那么这话没有问题（但不应使用“连通”这个词）。另一方面，如果把这个“连通”解释成“由{u2}∪V_2生成的子图是连通图”（这正是需要证明的结论），那么你的论证又不充分（要证明{u2}∪V_2生成的子图是连通的，就要说明{u2}∪V_2中任意两个顶点间都有通路，我在你的证明中仍然没有看到这样的论述，你只是用一个模糊的“连通”概念把两件事情弄成一件了）。

现在我一定要好好的改掉这个坏习惯！！ ^___^
我会多多练习文字证明题的。

==========================
证明条件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，感谢您一直的悉心指点啊！！！！  ^____^

题：

G是有限的Abel群。
若G中除了两个平凡群外，不再含有其他的正规子群，则称G为单群。
证明：G为单群的充要条件是G的阶为质数。

我的思路（好像有些循环论证的味道。。。^__^）：

本题证明： G为单群  <==>  G的阶为质数。

------------------------------------------
(a),证明 G的阶为质数 ==> G为单群 .

G的阶为质数,根据拉格朗日定理，则G不含有子群。（除两个平凡子群）
当然，不含其他的正规子群。
所以，G是单群。

G的阶为质数 ==> G为单群  获证。
------------------------------------------

（这部分证明，我不敢确定。因为正规子群和Abel群的规则都没有用上。心虚阿。。^__^）

（b）,  G为单群 ==> G的阶为质数

因为是单群，没有其他任何正规子群，所以G的阶为质数，否则。。。

实在证不下去了！
因为正规子群和Abel群的规则都没有用上啊！！！
天啊！！！
是我没有领悟到题意，还是这道题有问题啊？？？
请牛人给点建议！！！！ ^____^

（a）部分是对的。但表述不对。平凡子群也是子群啊。怎么能说“G不含有子群”？只能说“G不含非平凡的子群”或者说“G只有平凡的子群”。

（b）部分。看这里吧 http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=29548

离散真题和大部分教材习题这里都有解答。你不会做的先看看这个，还有疑问的再来问。

dear logician，您是否经常熬夜啊？ 很伤身体的哦。。。 ^____^

=======================
，dear logician 这道题是06年真题，昨晚上我没有在 http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=29548
找到呀！

那么您能否给点提示，怎么才能运到  Abel群 和 正规子群的 条件啊？？？
，小弟实在是束手无策！ 因为小弟这一阵子闭关修炼离散呀！！

我对离散题目的条件把握没有高数那么灵敏！
难道也只有通过做题来把握？

上次关于图论的题目把它翻译成图论来做！让我受益匪浅！总算让我找到着陆点阿！！

呵呵，我花在离散上的时间比较多而已吧。
如果你有足够多的时间，读足够多的书，做足够多的题，肯定就能比我学得还好。
我很早就开始学离散，离散的教材和各分支的教材都看了不少。
题看多了，做多了，自然就有感觉了。

授人以鱼不如授人以渔，我自然更愿意告诉你复习方法了。：）

北大考试出的代数题实际上非常非常的“正统”，也就是说，都是“经典”题目，多看几本代数书的话，基本上都能看到原题。
图论的题要活一点，只有在深入理解教材内容的情况下，多思考、多练习了。
集合论出的题都很基础，把概念弄清楚基本上没有问题（对于集合论中的那些定理，要多找一些的例子，能用文氏图画的要画一下，有了直观感觉才会有思路）。

离散数学我觉得是难以速成的，尤其是在你不熟悉它的基本思路的情况下。
多看看书上的例题和定理的证明，体会一下思路，这样提高会比较快。

以下是引用Logician在2006-9-30 11:30:00的发言： 北大考试出的代数题实际上非常非常的“正统”，也就是说，都是“经典”题目，多看几本代数书的话，基本上都能看到原题。 图论的题要活一点，只有在深入理解教材内容的情况下，多思考、多练习了。 集合论出的题都很基础，把概念弄清楚基本上没有问题（对于集合论中的那些定理，要多找一些的例子，能用文氏图画的要画一下，有了直观感觉才会有思路）。 离散数学我觉得是难以速成的，尤其是在你不熟悉它的基本思路的情况下。 多看看书上的例题和定理的证明，体会一下思路，这样提高会比较快。

DEAR Logician ,您说的太有道理了！！！！
我会多看些书来让自己成为离散高手！！ ^___^
=============================
dear logician 国庆愉快！！！！！

G/K中的单位元就是K。
注意，G/K是这样一个“集合的集合”，G/K={K,Ka,Kb,...}
其中Ka，Kb等是K的不同的陪集。单位元是集合K。
这一部分你再仔细看看书。

ker f是“那些使得f(x)=K的元素（在这里，这些元素也是集合，它们是形入H,Ha,Hb...的集合）所构成的集合”。你没告诉我你的f是怎么定义的，怎么算呢？

^____^,想不到，dear logician 也有点粗心哦。。。。。^_____^
（我写了定义哦。。。。对了，既然G/K中单位元是K，而肯定G/H={H,Ha,Hb,Hc...}，于是定义映射 f :  G/H ---> G/K，求 ker f={ ？ } ,我总是无法想象过程。。。特闷。。）

G是群，H是G正规子群，K是G的正规子群，H是K的子集。
若定义映射 f :  G/H ---> G/K .

G是群，H是G正规子群，K是G的正规子群，H是K的子集。
证明： G/K 与 (G/H)(K/H) 同构。

==================
因为这道题，要求出某个核，所以我才将其抽出来，向dear logician 请教的！
不好意思，给您带来麻烦了啊！！！
^____^

如果定义另一个函数g:G/H->G/K，g(Ha)=K,对所有Ha∈G/H，那么g是零同态，ker g=G/H。
显然，一个函数的性质（包括同态核）与它的对应法则有很大的关系。

对于这道题，我们知道，对任意Ha，我们要判定Ha是属于kerφ就是要判定φ(Ha)是否等于K。而φ(Ha)=Ka（这是φ的定义），所以Ha属于kerφ当且仅当Ka=K。根据教材定理17.22，Ka=K当且仅当a∈K。这就是说，kerφ就是所有由K中的元素与H相乘得到的陪集。即，kerφ={Hx|x∈K}。

明白了！！！啊！！！！豁然开朗！！！！
太厉害了！！！^____^

设G是有11个或更多的结点的图，证明：G或G'是平面图。（G'是G的补）
=================================

我的临乱、纷杂、沉重的思路：
（预测：为什么会选择11个结点，也许这个数字可以算出矛盾！）
（怎样推广到更多的结点，也许会涉及到一个不等式！）

G或G'的证明是互补的。可以只选择一个。如下：

（a）最简单的情况，即只有11个结点。
设|G|=11=n.
边数=m,
如果是G是非平面图，那么m>3*n-6=27.
而G的最多边数是：11*（11-1）/2=55。
则G'的边数是m'<28.
即：m'最大值是27。
而n'=n=11.
则27=m'<=3*n'-6=33-6=27.
（不违背平面图的必要条件。即：此时G'至少有平面图的可能）

接下来，证明G'为平面图。
即：n'=11,m'=27的图平面图。
反证：
设含有k5图，那么必有5个结点，连接10条边。
那么剩下的6个结点和17条边。。。。。。。

(b)推广的情况.......

我的思维到此冻结！！！虽然我继续思考，可以举步维艰啊！！
==============================

请求大牛们，给点提示。。。拜谢！

你看错题了吧？
是说G或G补中必有一个是非平面图吧？
你的那个命题应该是不成立的。
令G是3个K_5的并（如果要让它连通的话，随便再加两条边就可以了），那么G中含K_5，所以不是平面图，而G补中一样有K_5（因为G中很容易找到5个相互间都没有边的顶点），所以G补也不是平面图。

唉。。的确是我看错了。

dear logician 的反例无懈可击！！ ^___^

关于这道题的证明：我昨夜在床上翻来覆去的想出来了。。。
我用的反证法！假设都是平面图，然后解出 v<11.....
========================

哦，对了，关于你的。。。。。一道南大CS考研复试题（抽象代数）
设G_1和G_2分别是群G的两个子群，其中G_2是正规子群，且|G_1|与[G:G_2]互质，证明：G_1是G_2的子群。

你怎么就想出来用同态的方法呢？？？？
难道是第一敏感。。。我的高数也是这样.....^__^

说实话，我第一眼看到这题目：首先想到是如何用 子群的判定 去证明！！！
可是当我设出很多属于每个群的元素的时候，我就没有办法去将他们归属到证明的方向。
而且，对于互质概念也无法用出来！！

所以，我想问的是：你是否看到了这题的互质想到了用“同态”呢？？？
这就是对题设的敏感度阿！！
还是。。。也先是用到了 子群的判定，然后发现此路不通，于是改变了方法呢？？？？

当你第一次面对此题目的时候，你的反应是什么？？？？？？？
具体思路就出来了吗？？？？

-这就是我10月份拼命培养的灵敏离散触觉！！！！当然我也会看很多的题目。。^___^

嗯，我会仔细体会您说的话的！！！

其实，北大离散教材上的习题，我在练习的时候，总觉得和北大最近几年的试题，感觉不一样！！！！！
总觉得没有试题的韵味和灵气！！！

所以，我在做习题的时候，只是略微的看一下，只是体会书本上的定理的运用而已！
无法去猜测北大的07的试题！！

不知道我这番感受是否太天真和可爱？？？？？

不知道，dear logician 对教材上的习题有何看法，对北大考研试题有何导向作用呢？
还是只是练习基础而已！！！！！

中秋回家了！感觉真好！！！！^__^

不过也有些题目，我总是不能很容易找到思路。。

如：
============
证明： p^2（素数p的2次方)阶的群为Abel群。

===============
我的思路： 取出a, 则 |a|=p  or  p^2   .
..............

^___^ ,dear logician 我的思路到此，有些迷糊了。。。

能够给点提示呢？？？？
等待着哦。。。。。 。。。谢谢啦。。。。。拜谢。。。

我是报考北大计算机软件与理论的 操作系统 方向的。
这个专业难考吧？ dear logician 能否给点建议呢？？？
^____^ 拜谢！！！

那就让我自己一个人来体会吧？ 呵呵。。。
=============================
设群<G,.。> ,|G|=4，证明：<G,.。> 是交换群。

我的思路：证明交换群本题根据定义来证明。（对吗？）
              可是条件|G|=4 里面，当然里面只有4个元素，一个是单位元。
              我立刻想到了该4个元素的群会不会是Klein群呢？
               这样列举出运算法则，便可知道满足交换群的定义啦！

            难道我的思路正确吗？不过我觉得有些牵强，是我错了？还是我不够自信呢？

              我要请教dear logician的是：题设中隐含着什么呢？
             我对条件的反应还是不够不敏感，我会强加练习的哦。。。
              dear logician，第一眼看到这个题目，
            你想到了什么呢？

           ^__^,感觉像破案，刺激！

一种麻烦的办法就是去证那个“p^2阶都是Abel群”。
简单一点的就是利用2阶元的性质（教材上有很简单的一道习题：“设G是群，若对G中所有元素x，都满足x^2=x，则G是交换群”），考虑4阶群中最高阶元的阶数。如果最高阶为4，那么G是循环群，如果最高阶为2，就可以用那道习题的结果，证明它是交换群。

好的
dear logician,如果是4阶，那么只要说明它是循环群了吧？即点出是循环群就行了吧？ 对吗？
==================
题：设G为有限Abel群，且|G|为奇数，证明G中全体元素之积等于单位元e.

我的思路：除了单位元e外,其他元素和其逆元(共偶数个)是成对的出现。
               即：若存在x_i，必定存在x_j，互逆。使x_ i*x_ j=e.
              且x_ i <> x_ j。 否则x_ i 的逆元= x_ j, 则有 x_ i^2=e,
              即：x_ i 为 2 阶元。这与|G|为奇数矛盾！！！

              于是除单位元外，剩下的偶数个元素，都能找到自己的逆元。
              即：所有元素之积等于单位元e.

这样的证明，我觉得也有牵强！ 因为Abel群的信息我没有用上，难道是冗余的？？？

请dear logician 提示。。 ^___^

第二个问题：基本正确。Abel群的条件很重要。因为题目没说按什么顺序把所有的元素乘起来。如果不是Abel群，而元素又不一定是以“a*a逆”这样的形式成对出现，那么你就无法推出乘积一定为e了（因为由“a*b=e，c*d=e”推不出“a*c*b*d=e”，除非已知“c*b=b*c”）。