造价通
反馈
取消

热门搜词

造价通
取消 发送 反馈意见

建设工程知识

最大独立集独立集

2022/07/16237 作者：佚名
导读：独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立集的性质。一般而言，寻找图的最大团是 NP 困难的，从而寻找图的最大独立集也是 N-P 困难的。但是，对于二部图的情形，有多项式时间算法找出图的最大独立集。

独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立集的性质。一般而言，寻找图的最大团是 NP 困难的，从而寻找图的最大独立集也是 N-P 困难的。但是，对于二部图的情形，有多项式时间算法找出图的最大独立集。

*文章为作者独立观点，不代表造价通立场，除来源是“造价通”外。
关注微信公众号造价通（zjtcn_Largedata），获取建设行业第一手资讯

热门推荐

相关阅读