Math 版 (精华区)

发信人: kaola (无心考拉熊), 信区: Math
标  题: [合集]◎ 一道题目
发信站: 哈工大紫丁香 (2003年04月13日21:14:29 星期天), 站内信件


────────────────────────────────────────
 lhqian (一心一意的革命者)            于 发信站: 紫 丁 香 (Thu Mar 16 11:53:28 2000) WWW-POST
平面任意N个点，能否用直线把它们连起来，满足：
1。两点之间只能用直线连接
2。最后得到一条闭合的折线
3。且此折线不和自己相交
例如：
   *.............*
  .              .
 .               .
*.......*        .
         .       .
          *......*     

────────────────────────────────────────
 micheal (平凡的世界)                 于 发信站: 紫 丁 香 (Thu Mar 16 16:32:47 2000), 转信
hehe,能，上满足上面的平面要求的连线方式是有限的，取出长度最小的
即为所求，呵呵
【 在 lhqian (一心一意的革命者) 的大作中提到: 】
: 平面任意N个点，能否用直线把它们连起来，满足：
: 1。两点之间只能用直线连接
: 2。最后得到一条闭合的折线
: 3。且此折线不和自己相交
: 例如：
:    *.............*
:   .              .
:  .               .
: *.......*        .
:          .       .
:           *......*     

────────────────────────────────────────
 micheal (平凡的世界)                 于 发信站: 紫 丁 香 (Fri Mar 17 09:04:02 2000), 转信
我不是说要改变连线次序，只是证明最短的不会相交，:))
因为如果出现相交的情形，不妨设如图中情况，这是不改变其他
的连线情况，则其他连线总长记为l，如果最短的有相交的情形
则改变次序，有 总长变为l+ac+bd<l+ab+cd,就找到了比最短
还短的连线方式，呵呵，矛盾，所以最短的不会相交，
（因为连线的方式是有限个，所以必存在最短的路线。)
另外，如果连ac,bd变成两条封闭的折线，就连ad,bc,不会两种情况都是两条封闭的折线。
【 在 Santa (北极星) 的大作中提到: 】
: 怎么保证不会出现两条封闭曲线？
: 此外改变这些点的排列顺序，会不会产生新的交线？
: 【 在 micheal (平凡的世界) 的大作中提到: 】
: : hehe,设相交的两条线是ab,cd
: :        a
: :        |
: :        |
: :  c  ---|------d
: :        |
: :        b
: : then ab+ca>ac +bd,可以找到一种更短的连接方式，矛盾。所以不能
: : 相交，呵呵 

────────────────────────────────────────