以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  2006年北大数学试题的一道图论题目  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=41301)

--  作者：ychj
--  发布时间：12/17/2006 7:49:00 AM

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

对于以下两种情况:
1) k个圈两两无公共点;
2) k个圈至少有两个圈有公共点, 但两两均无公共边;
可以得出t最大值为k, 并用数学归纳法容易严格证之.

似乎出题人并没有考虑到重边的情况, 若出现重边, t的最大值就与重边的情况相关了;
但题目条件的确没有给清楚, 大家讨论讨论吧.

--  作者：Logician
--  发布时间：12/17/2006 8:00:00 PM

--  
这个问题当时在未名BBS上讨论过。
如果认为有不同的子图中有公共边，且公共边在合并后合成一个，这样的题就太奇怪了（而且貌似很难）。
我当时想了一下，没想清楚……
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 31.250ms