将图分组的算法

Question

我正在寻找一种算法，可以将图形分成顶点组（如果它们本身是图形，则它们相互连接），最大尺寸为n，同时使组数最小化。我需要这个算法将德劳内三角测量分区成每个区域具有相等数量的顶点。如果有更好的解决此问题的方法，请告诉我！

- zaloo

Answer 1

似乎您正在寻找一种解决均匀k-way图分区问题的方法，其中，给定一个图G(V,E)，目标是将顶点集V划分为一系列k个不相交的子集V1，V2，...，Vk，使得每个子集Vi的大小大约为|V|/k。此外，通常需要“好”的分区，其中任意两个子集Vi和Vj之间的边权重之和最小化。

首先，众所周知，这个问题是NP-完全的，排除了有效精确算法的存在。好消息是，已经开发出了许多有效的启发式算法，在许多实际问题上表现良好。

特别是，基于迭代多层方法的方案在实践中非常成功。在这种方法中，通过逐步合并相邻的顶点形成一个较小的“粗糙”图形来创建一个图形层次结构。当粗略图变得足够小时，形成一个初始分区，然后将此分区“映射”回到原始图形上。通常，在此映射过程中执行分区的迭代细化，通常会导致伪最优分区。

实现此类算法并不容易，但许多现有软件包支持这些例程。具体而言，METIS 软件包得到了广泛应用。

- Darren Engwirda