骰迷 发表于 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# 的帖子

线段互不相交。。。
页: [1]
查看完整版本: n点连线问题