魔方吧·中文魔方俱乐部

标题: n点连线问题 [打印本页]

作者: 骰迷 时间: 2011-7-20 21:26:28 标题: n点连线问题

若平面上有n点,最多能连多少条互不相交的线段?
什么连线方案最优?

比如一点是0条线,两点1条,三点3条,四点6条,五点就好像只能连9条之类的

作者: superacid 时间: 2011-7-20 21:58:41

题目应该是问这n个点成如何状态的时候连线能最多吧
只要这n个点的凸包是三角形且任意3点不共线就可以了，能连3n-6条线(n≥3)

突然想起来。。。这就是著名的e≤3n-6

想法是根据V+F-E=1，然后用三角形内角和来考虑F的最大值

作者: 42752277 时间: 2011-7-20 23:10:02

没有太听懂

.

作者: konami赚了钱 时间: 2011-7-23 12:42:04

n*(n－1)/2

作者: superacid 时间: 2011-7-23 20:29:22 标题: 回复 4# 的帖子

线段互不相交。。。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)