标签：顶点覆盖

2020-03-04半瓶木阅读(1336)评论(0)赞(0)

图G的顶点覆盖是一组顶点, 使得G中的每个边均入射到这些顶点中的至少一个顶点上。 决策顶点覆盖问题已被证明是NPC。现在, 我们要解决顶点覆盖问题的最佳版本, 即, 我们要找到给定图的最小尺寸的顶点覆盖。我们称这种顶点覆盖为最佳顶点覆盖C ...