连线问题

nnd · 发表于 2012-7-14 00:12:28

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

平面上有n个点，以这些点为起点和终点做曲线，请问起点或终点不同，且不交叉的曲线最多有多少条？

wayne · 发表于 2012-7-14 18:56:23

$\sum_{k=2}^{n}C_k^2*C_n^k = n*(n-1)*2^{n-3}$

nnd · 发表于 2012-7-15 00:08:39

有这么大么？起点或终点不同的曲线最多只有n*（n-1）/2条啊。这题没有这么难的，wayne 是不是想复杂了？还是我的表达让人产生误解?

wayne · 发表于 2012-7-15 01:06:44

比如:,有3个点,标号为1,2,3.则曲线有: 连接2个点: 1-2 2-3 3-1 连接3个点: 1-2-3 2-3-1 3-1-2

nnd · 发表于 2012-7-15 09:54:29

1-2和2-3-1起点和终点都是相同的（不考虑方向的话）。但是表达确实有问题。我的意思是：平面上有n个点，分别以这些点为端点做曲线，请问两个端点不完全相同，且不交叉无重叠的曲线最多有多少条？加上”不重叠“是因为可以重叠时，依次连接这n个点就可以得到 n*（n-1）/2条曲线，没太多意思。

nnd · 发表于 2012-7-18 21:33:06

今天回家路上堵车，忽然想到第二个解法。更简单的解法。

nnd · 发表于 2012-7-19 09:29:00

将一个地图“最复杂化”后，用一个点表示一个国家，点之间的连线表示国家之间的接壤情况，四色定理就演变成这个题目了。能不能用这种思路得到四色定理的一个简单的证明呢？

nnd · 发表于 2012-7-19 10:01:13

我觉得我已经找到了四色定理的一个极其简单的证明，有空我把他写出来再仔细检查一下。呵呵

nnd · 发表于 2012-7-20 00:16:51

我发现把一个简单的思路写清楚真是一件很头痛的事情。 http://blog.sina.com.cn/s/blog_64c9803201014go8.html 我估计图论或者拓扑论里有相应的概念或者定理可以使用来简化论述。从头开始真是麻烦。不过也有好处，就是不懂图论或者拓扑论的人也能看懂。但是我不确定我是否写清楚了。

账号		自动登录	找回密码
密码			欢迎注册

[原创] 连线问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。