Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
给定一个无向图。如何找到图中每个顶点的度数至少为 p 的最大顶点子集的大小,其中子集中的度数仅在子集中的顶点中找到。
度数小于 p 的顶点永远不能成为解的一部分。完全移除它们,包括它们的边缘。查看新图表并重复,等等。
当这个过程停止时,所有顶点的度数至少为 p。
然后,查看该图的连接组件并选择最大的一个!(正如 Evgeny Kluev 正确指出的那样,这当然是不必要的。在我的脑海中,剩余的子图应该已经连接,但当然原始问题没有这样的要求。)