给定一个无向图。如何找到图的最大顶点子集的大小,其中每个顶点的度至少为 p,其中子集中的度仅在子集中的顶点之间找到。
最佳答案
度数小于 p 的顶点永远不会成为解决方案的一部分。完全移除它们,包括它们的边缘。查看新图并重复等。
当这个过程停止时,所有顶点的度数至少为 p。
然后,查看该图的连通分量并选择最大的一个! (正如 Evgeny Kluev 正确指出的那样,这当然是不必要的。在我看来,剩余的子图应该是连接的,但当然原始问题没有这样的要求。)
关于algorithm - 找到图的最大子集的大小,其中每个顶点的度数至少为 p,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15309592/