以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  06年图论的两个题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=35822)

--  作者：Supremgoooo
--  发布时间：7/19/2006 7:04:00 PM

--  06年图论的两个题
似乎很难说清道理，大家讨论一下：

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

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

--  作者：carroty
--  发布时间：7/19/2006 8:36:00 PM

--  
4.我觉得是就是k个吧,取到k得值时,k个圈不想连通.
可以证明其他情况下添加边得数目可以较少.例如两个圈相交时.
另外需要证明,对某种情况,添加得为一个圈,因为欧拉图是圈得并.

5.最少情况为2,因为k3,3需要至少两种颜色.
最多得情况最少应该是5,因为k5是极小,所有>=5
同时因为极小非平面图去掉一条边为地图,可以4着色,设图G-{e}可以4着色,则给e得两个端点添加一种其他颜色,则可实现着色.

又全部得题吗?共享一下吧,谢谢:)

--  作者：Logician
--  发布时间：7/20/2006 4:12:00 PM

--  
4. 首先，我不确定“由k个圈组成”，是否就是指“k个边不重的圈的并”。我认为是的，而且如果不是，这个题我就不知道该怎么做了。下面先在假定它是的情况下做：
    显然，如果图中有s个连通分支，则至少要s-1条边才能使之重新连通。但这时，必然存在奇数度顶点（这是因为，在加入这s-1条边前，G中所有顶点都是偶数度。新加入的这s-1条边会使总度数增加2s-2，而总共有s个连通分支，由鸽巢原理知，存在某个连通分支p_i，使得p_i的顶点度数和至多只增加1，另一方面，因为这s-1条边连接了所有连通分支，所以p_i的顶点度数至少增加1.这就是说，p_i中有一个顶点成为了奇数度），从而不会是欧拉图。
    另一方面，按如下方式向图中添加s个边：从s个连通分支中各取一个顶点，分别记为v_1,v_2,...,v_s，则加入边(v_1,v_2),(v_2,v_3),...,(v_{s-1},v_s),(v_s,v_1)。易见，加入的边构成一个圈，从而新图G'是若干个边不重的圈的并，且是连通的。
    这就是说，所需添加的边数t即为连通分支数，而有k个圈时，连通分支数至多为k，所以t的最大值是k。

5.
(1) 最少2种。因为：首先，1色图显然都是平面图，所以不可能有点色数为1的极小非平面图。另一方面，存在极小非平面的2部图（如K_{3,3}），而2部图是2-可着色的。从而存在2色的极小非平面图。这就是说，任意极小非平面图最少需要用2种颜色进行着色。
(2) 最多5种。因为：首先，设G为任意极小非平面图，e=(u,v)为G的任意边，令H=G-e。由4色定理，可以对H进行4着色。此时，若u和v同色，则给u着第5种颜色。这样的着色方案显然是对G的一种可行的着色。从而任意极小非平面图都是5-可着色的。另一方面，K_5就是一个点色数为5的极小非平面图。从而“5”就是所求的最大值。


[此贴子已经被作者于2006-7-20 20:30:09编辑过]
--  作者：Logician
--  发布时间：7/20/2006 4:58:00 PM

--  
感谢Supremgoooo的提醒，第5题可以不用4CC，而用教材上给出了证明的5色定理来做：
    设G为任意极小非平面图，e=(u,v)为G的任意边，令H=G-e。由教材定理11.10可知，|E(G)|=|E(H)|+1<=3n-5<3n。从而G中必然存在度数小于等于5的顶点v。
    令G_1=G-v，显然，G_1是平面图。由5色定理可知，它是5-可着色的。对G_1进行5着色，下面证明，把G_1还原成G时，v是可着色的。（下面照抄教材中5色定理证明中三种情况的讨论即可）。

--  作者：carroty
--  发布时间：7/20/2006 6:32:00 PM

--  
恩,有道理
--  作者：teng_t1986
--  发布时间：7/27/2006 6:39:00 PM

--  
多谢指教！
--  作者：yourwk
--  发布时间：8/22/2006 10:41:00 PM

--  
4CC仅是猜想缺乏证明,不能做定理用,只能用5色定理
--  作者：Logician
--  发布时间：8/22/2006 11:09:00 PM

--  
其实已经证明了……
不过因为北大的教材上没有，所以参加北大的考试时最好不用就是了。
--  作者：borlong
--  发布时间：9/2/2006 5:33:00 PM

--  
最少边的最大值？？？？这么绕口的命题怎么解释呀？？？通俗点，怎么说呢？
--  作者：lilylily
--  发布时间：9/4/2006 5:48:00 PM

--  
那楼主肯定有2006年数学基础的真题了？！
能不能给我发一份
油箱：lily830307@sina.com

急需，谢谢

--  作者：Logician
--  发布时间：9/4/2006 5:59:00 PM

--  
这个版上就有现成的可供下载，为什么不先自己找找呢？
--  作者：aison
--  发布时间：9/26/2006 5:52:00 PM

--  
还原v点的时候它关联着六条边啊。。。怎么能照书上的证明呢？？

偶想6可着色肯定没问题。

--  作者：Logician
--  发布时间：9/26/2006 8:14:00 PM

--  
v只关联5条啊，怎么会是6条？
首先我证明的是v在G中的度数也不超过5。
我作H只是为了使用那个3n-6的结论。
我的论证思路是：|E(H)|<=3n-6，所以|E(G)|<=3n-5。
因为|E(G)|<=3n-5，所以G中（不是H中）必有度数小于等于5的顶点。
这个顶点在G中关联的边数不超过5。
--  作者：aison
--  发布时间：9/26/2006 10:17:00 PM

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