将图分成图组的算法

Question

我正在寻找一种算法来将图分成最大大小为n的顶点组（每个顶点都是连接的，如果它是自己的图），同时保持组数最小化。我需要这个算法来将delaunay三角剖分分割成每个区域中顶点数相等的区域。如果有人有解决这个问题的更好的想法，让我知道！

Answer 1

看来你正在寻找一个解决方案来统一k-way graph partitioning problem，其中，给定图G(V,E)，我们的目标是分区顶点集V成一系列的k分离子集V1, V2, ..., Vk使得各个子集的大小Vi大约是|V|/k。另外，通常需要“好”分区，其中任何两个子集Vi和Vj之间的边权重的总和被最小化。首先，众所周知的是，这个问题是完全的，排除了高效精确算法的存在。另一方面，已经开发了许多有效的启发式方法，在许多实际问题上表现得相当出色。

具体来说，基于迭代多级方法的方案在实践中已经非常成功。在这样的方法中，通过递增地合并相邻的顶点来创建图的层次结构，以在层次结构的每个层上形成较小的“粗略”图。初始分区在粗略图变得足够小时形成，然后该分区“映射”回层次结构到原始图上。分区的迭代改进通常作为该映射过程的一部分来执行，通常导致伪最优分区。

这种算法的实现是非平凡的，但一些现有的软件包支持这样的例程。具体来说，METIS包被广泛使用。