You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于团数为k的图能否划分为至多k个独立集的技术问询

关于团数为k的图能否划分为至多k个独立集的技术问询

嘿,各位大佬,我最近在研究一个子问题时碰到了这么个论断,想跟大家求证一下:对于团数为k的图,是不是总能将其划分为至多k个独立集?

我的思路是这样的:首先,用来划分的独立集数量肯定不能少于k——不然的话,同一个团里的两个顶点就会被分到同一个独立集里,这显然说不通啊,毕竟团里的顶点两两都是相邻的,根本没法共存于同一个独立集。

不过我越想越觉得,这个结论是不是有点“过于完美”了?到底是真的总能做到,还是我哪里考虑不周,漏掉了某些特殊情况?

备注:内容来源于stack exchange,提问作者kakashi-pupushi

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.15 11:28:19