中文XML论坛--06北大曾考题，欧拉图解法中的迷惑和有趣。。。

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

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

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

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『计算机考研交流』 → 06北大曾考题，欧拉图解法中的迷惑和有趣。。。

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 33447 个阅读者　　

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

borlong

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

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

	楼主

06北大曾考题，欧拉图解法中的迷惑和有趣。。。

下面是小弟的解法，颇为有趣和迷惑。。。: P
题：设k是给定正整数,由k个圈组成一个(有向或无向)图,要添加最少数量的边使之成为欧拉图,设这样添加的边数为t,问t的最大值是多少?为什么?
我的思路：假设如果有2个圈，不重合，加上最少的边成为欧拉图，即在这2个圈中的每个圈的某同一个点上加2条“平行边”。因为圈中每个点的度数是2，已经符合欧拉图的条件，
必须加上2条平行边，这样才能使之符合欧拉图的条件。
于是，可以想象,k个圈可以假设成k个点，要是k个独立点成为图！那么“最少”必须加上(k-1)条边才能使之连通，可是！！！还要补上“平行边”，使之满足欧拉图条件，于是加上了2*（k-1）条边！！！
即添加最少的2*（k-1）条边，可以成为欧拉图！！！
但是！！！为什么题目要问：最少边的最大值呢？？？！！！
最大值指的到底是什么意思啊？？？
我非常不理解！
难道是小弟对题目的意思没有弄明白？还是我的知识不够呢？
还请牛人给小弟指点指点！不胜感激！

收藏分享
顶(0)

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

2006/9/25 7:30:00

Logician

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

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

	第2楼

给定一个图G，我们要力求添加最少的边，使它成为欧拉图。记这个边数的最小值为t。
显然，t的值与G有关。所以，我们要问：对于给定的一类图（在题中就是由k个圈组成的图），在“最坏情况”下，t会是多少。
从你的解法看，你对题目的理解没有问题，但你给的解不是最优的。为什么要加那么多平行边呢？只需要在k-1的基础上，再加一条边，把它连成一个圈，就不行了吗？所以t的最大值应该是k。
----------------------------------------------
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/25 9:50:00

borlong

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

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

	第3楼

谢谢！
唉。。。原来是这样！我陷入了一个致命的思维障碍中！
但是！
该题目中，所谓的“最小值”，“最大值”指的是到底是什么？？？
我的理解：最小值，即要求在k个圈中加上最少的边！
既然如此，最小边最大值应该是没有意义的啊！！！
因为假设正确答案是k，那么还有比k更大的值啊！！！不是吗？
那么最大值又该作何理解呢？？？
看来小弟的语文还要好好的学学吧？：P
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/25 16:57:00

Logician

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

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

	第4楼

怎么会没有意义呢？
例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的分最高？
----------------------------------------------
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/25 18:59:00

borlong

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

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

	第5楼

哈哈哈。。。我太开心了拉！！终于明白什么是豁然开朗啊！！谢谢！！！
这些这个例子！美妙极了！！！
尤其是这个例3，通俗易懂！
那么在本题目中，最小值是指加上最少的边！即，可以有很多种方法加上最少的边！！而在这些方法中又一个是边数最多的！！即最大值！！
我的理解正确不？？？？：P
还有这道题：
给极小非平面图顶点着色，
（1）至少需要几种颜色，为什么？
（2）至多需要几种颜色，为什么？
我的解法：
极小非平面图最大指平面图上加上1条边，使之成为极小非平面！
由于极小非平面的定点数目〉=5，（因为<=4均是平面图，而k5是非平面图）
立刻联想到k3,3是极小非平面图，可以用2-色。
那么还有1-色的极小非平面图吗？
没有了！否则，该图不是连通的！
于是得出结论，最小的色数是2！！！！
即，至少用2种颜色！！！
呜呜----可是这个证明我总觉得有点问题！也许是来自于文字的叙述吧！毕竟
不是数学表达式的严格证明！！！
然而更可怕是下面的：至多需要几种颜色？
因为有平面图的四色定理的存在和五色定理的存在！
这些定理将直接影响到本题的证明！
（a）因为如果四色定理可以用！那么至多是五色！因为将极小非平面图中
暂且拿掉一个点，变成平面图，用四色，然后再补上刚才拿掉的那点用
另外一种颜色！即五色！！！！
(b),如果五色定理可以用！那么至多是六色!!!证明如上！
呜呜-----到底该选择哪个定理呢？？？？
郁闷！无奈！！
请牛人来指点小弟啊！！！急切期待！！！
：P
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/25 20:26:00

Logician

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

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

	第6楼

以下是引用borlong在2006-9-25 20:26:00的发言：
那么在本题目中，最小值是指加上最少的边！  即，可以有很多种方法加上最少的边！！而在这些方法中又一个是边数最多的！！即最大值！！
我的理解正确不？？？？    ：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变成欧拉图的各种不同方案所需添加的不同边数。
----------------------------------------------
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/25 22:57:00

Logician

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

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

	第7楼

以下是引用borlong在2006-9-25 20:26:00的发言：
给极小非平面图顶点着色，
（1）至少需要几种颜色，为什么？
（2）至多需要几种颜色，为什么？

参见 http://www.ieee.org.cn/dispbbs.asp?BoardID=67&replyID=52401&id=35822&star=1&skin=0
----------------------------------------------
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/25 23:05:00

Logician

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

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

	第8楼

以下是引用borlong在2006-9-25 20:26:00的发言：
给极小非平面图顶点着色，
（1）至少需要几种颜色，为什么？
（2）至多需要几种颜色，为什么？
我的解法：
极小非平面图最大指平面图上加上1条边，使之成为极小非平面！
由于极小非平面的定点数目〉=5，（因为<=4均是平面图，而k5是非平面图）
立刻联想到k3,3是极小非平面图，可以用2-色。
那么还有1-色的极小非平面图吗？
没有了！否则，该图不是连通的！
于是得出结论，最小的色数是2！！！！
即，至少用2种颜色！！！
呜呜----可是这个证明我总觉得有点问题！也许是来自于文字的叙述吧！毕竟
不是数学表达式的严格证明！！！
然而更可怕是下面的：至多需要几种颜色？
因为有平面图的四色定理的存在和五色定理的存在！
这些定理将直接影响到本题的证明！
（a）因为如果四色定理可以用！那么至多是五色！因为将极小非平面图中
暂且拿掉一个点，变成平面图，用四色，然后再补上刚才拿掉的那点用
另外一种颜色！即五色！！！！
(b),如果五色定理可以用！那么至多是六色!!!证明如上！
呜呜-----到底该选择哪个定理呢？？？？
郁闷！无奈！！

关于最少几色，你的论证没有问题。
你两个方面都考虑到了：
1、不可能是1色（因为1色图无边，肯定是平面图），从而下限至少是2。
2、确实有2色的极小非平面图K_{3,3,}。从而下限至多是2。
这就得到了“下限等于2”的结论。
关于最多几色，我前面给你的链接中已经给出了用五色定理证明上限不超过5的证法。
但你的论述中少了“上限最少是5”的论证（即，没有给出色数为5的极小非平面图的例子），从而即便说明了“上限不超过5”，也没有排除“上限是4”这样的可能性。所以论证不完整。
讨论上下限的题，如果可能，都要论证两方面，一方面是这个限制确实是有效的（没有例子能突破它），另一方面是这个限制确实是“最优的”（不可能有比它更“紧”的限制了）。
比如这道考题，如果我宣称：极小非平图图色数不可能小于0，也不可能大于100。那么我的宣称也是成立的，0和100也确实分别是极小非平图的色数下界和上界，但它们不是“紧”下/上界。用集合论的话说，它们是下界和上界，但不是下确界和上确界。所以这种结果是不够好的。
----------------------------------------------
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/25 23:15:00

borlong

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

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

	第9楼

非常感谢dear logician!!
相信在你的指点下，07年我的离散肯定可以取得不错的成绩！
每次看到你的贴，我收获不少！！
仔仔细细、反反复复阅读了你的贴后，我的理解是：
K个圈可以组成1类图，这类图中，每个图都可以加上“最少”的边
使之成为欧拉图！！！假设每个图加上“最少”的边数是X1,X2,X3...
然而，在这些X1,X2,X3...“最少”边数中，必有一个是“最大”的值！
而我们求得就是这个最大值！！！
我的理解正确吗？？
我是否很可爱啊？不好意思，我的图论部分的确很薄弱！！！
让Dear Logician ,见笑啦啊！
==================================================
“由k条个圈组成的图”不是一个图，而是一类图。
---------------------------------------------我懂了！！！
每个图都可以表成某k个不相交的圈的并！
---------------------------------------------不怎么懂！！！
假设有3=k个圈，那么你的G_1,G_2等等所指的是什么图呢？能否具体点。
因为这里实在是太抽象了，我无法“画”一些图来模拟啊！
我想着在考试中应该是个不小的困境吧！！！

============================
dear logician 国庆和中秋快来了，望你一切顺心哦！！
非常感谢！！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/26 21:30:00

Logician

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

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

	第10楼

以下是引用borlong在2006-9-26 21:30:00的发言：
仔仔细细、反反复复阅读了你的贴后，我的理解是：
K个圈可以组成1类图，这类图中，每个图都可以加上“最少”的边
使之成为欧拉图！！！假设每个图加上“最少”的边数是X1,X2,X3...
然而，在这些X1,X2,X3...“最少”边数中，必有一个是“最大”的值！
而我们求得就是这个最大值！！！
我的理解正确吗？？

正确。
==================================================
“每个图都可以表成某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顶点的图。但这个图只有两个连通支。
还需要我接着举吗？
建议多看看书上的例子，做一些习题，培养一下对图论的感觉。
----------------------------------------------
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/26 23:38:00

GoogleAdSense

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

	广告

2024/5/19 15:17:10

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

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


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