我想将图划分为子图，每个子图由最多 3 个顶点组成，并且边的权重之和最小化，主图是完整的(具有所有可能的边)，并且边被加权。 我想解决的主要问题是在 map 上找到接近的三个三点。
最佳答案
我确信这个问题是 NP 完全问题。它被称为 minimum k-cut problem .
尝试看看这个 article 。它讨论了解决此类问题的近似算法。
关于c - 将图划分为三顶点图，使边的权重之和最小化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22397743/