以 n 个顶点为一组的图形划分
Graph partitioning in groups of n vertices each
有没有一种图划分方法可以将一个图划分成最多n个顶点的组。
示例：我有一个包含 1000 个顶点的图，我想将其划分为最多包含 100 个顶点的子图。如果算法发现这样更好，则可以有 2 个子图，每个子图有 50 个顶点。
我发现了一种使用 k-means 和 k-means 之后 "calibrate" 聚类的方法，每个聚类中有 100 个顶点，但我认为这种方法很耗时。
有什么想法吗？
编辑：好的，也许要求子图是错误的。想象一下 kmeans 是如何工作的，我想将我的图分成小组，分区后我解决每个组中的 TSP 问题，然后 link 每个组最近的组，并为组中心应用 3opt 移动。但是要做到这一点，我需要一种分区方法来找到具有最大 n 个顶点的组；算法可以找到具有 n 个顶点的 k 组，如果有一些顶点空闲，它将用剩下的顶点创建另一个组。顶点必须彼此靠近而不是随机选择。
你需要为此进行研究。我记得一种名为 Kernighan-Lin 的启发式算法可以满足您的目的。不幸的是你需要概括它，时间真的很糟糕。我相信它大约是 O(N^3).
另外一种更专业但更复杂的方法是使用Spectral Partitioning。您可以在 Direct Science 网站上使用有关此主题的非常详细的文章。这里是这个主题的link：谱划分工作：平面图和有限
元素网格.
希望这对您的探索有所帮助。但我警告你这不是一件简单的事情。祝你好运！
有没有一种图划分方法可以将一个图划分成最多n个顶点的组。
示例：我有一个包含 1000 个顶点的图，我想将其划分为最多包含 100 个顶点的子图。如果算法发现这样更好，则可以有 2 个子图，每个子图有 50 个顶点。
我发现了一种使用 k-means 和 k-means 之后 "calibrate" 聚类的方法，每个聚类中有 100 个顶点，但我认为这种方法很耗时。
有什么想法吗？
编辑：好的，也许要求子图是错误的。想象一下 kmeans 是如何工作的，我想将我的图分成小组，分区后我解决每个组中的 TSP 问题，然后 link 每个组最近的组，并为组中心应用 3opt 移动。但是要做到这一点，我需要一种分区方法来找到具有最大 n 个顶点的组；算法可以找到具有 n 个顶点的 k 组，如果有一些顶点空闲，它将用剩下的顶点创建另一个组。顶点必须彼此靠近而不是随机选择。
你需要为此进行研究。我记得一种名为 Kernighan-Lin 的启发式算法可以满足您的目的。不幸的是你需要概括它，时间真的很糟糕。我相信它大约是 O(N^3).
另外一种更专业但更复杂的方法是使用Spectral Partitioning。您可以在 Direct Science 网站上使用有关此主题的非常详细的文章。这里是这个主题的link：谱划分工作：平面图和有限 元素网格.
希望这对您的探索有所帮助。但我警告你这不是一件简单的事情。祝你好运！