h*****a
发帖数: 1992 | 1 算法没学好，都还给老师了。请大家帮忙 //bow
一个平面上有n个点，每两个点之间都有连线(hmm，总共就是n*(n-1)/2条线)，现在呢，
要把这n*(n-1)/2条线分k次取出，每次取出的线段不能共享任何端点。问：1. k的最小值
是不是n-1(n是偶数）或n（n是奇数); 2. 计算这个最优取法有没有polynomial算法.
例子： 平面上6个点,标为ABCDEF，它们之间有15条线。最少可以分5次取出：
第一次： AB, CD, EF
第二次: AC, BE, DF
第三次: AD, BF, CE
第四次: AE, BD, CF
第五次： AF, BC, DE
偶有个程序大概要计算n=200的最优取法，brutal force或者回朔太慢了，有polynomial
算法么? | y***s
发帖数: 294 | 2 see EE for my hints
【在 h*****a 的大作中提到】
: 算法没学好，都还给老师了。请大家帮忙 //bow
: 一个平面上有n个点，每两个点之间都有连线(hmm，总共就是n*(n-1)/2条线)，现在呢，
: 要把这n*(n-1)/2条线分k次取出，每次取出的线段不能共享任何端点。问：1. k的最小值
: 是不是n-1(n是偶数）或n（n是奇数); 2. 计算这个最优取法有没有polynomial算法.
: 例子： 平面上6个点,标为ABCDEF，它们之间有15条线。最少可以分5次取出：
: 第一次： AB, CD, EF
: 第二次: AC, BE, DF
: 第三次: AD, BF, CE
: 第四次: AE, BD, CF
: 第五次： AF, BC, DE
|
|
