| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
最大团就是=着色数吧 而且最大团本身也是NP 问题In Reply To:赞,顶色数!=最大团问题 Posted by:xuhanqiu at 2009-06-05 21:43:37 由最大团性质可知,最大团中每个顶点都相邻, 假设最大团中顶点个数为m 则需要m种中继器,而非最大团中的点,起码在最大团中找到一个不相邻的点,而不需要新的中继器 所以m即为所求。 且m必然是最小的。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator