关于团数为k的图能否划分为至多k个独立集的技术问询
关于团数为k的图能否划分为至多k个独立集的技术问询
嘿,各位大佬,我最近在研究一个子问题时碰到了这么个论断,想跟大家求证一下:对于团数为k的图,是不是总能将其划分为至多k个独立集?
我的思路是这样的:首先,用来划分的独立集数量肯定不能少于k——不然的话,同一个团里的两个顶点就会被分到同一个独立集里,这显然说不通啊,毕竟团里的顶点两两都是相邻的,根本没法共存于同一个独立集。
不过我越想越觉得,这个结论是不是有点“过于完美”了?到底是真的总能做到,还是我哪里考虑不周,漏掉了某些特殊情况?
备注:内容来源于stack exchange,提问作者kakashi-pupushi
相关产品推荐
相关产品推荐

