algorithm - Kernighan-Lin 算法

Question

有没有人知道这个算法一点点，因为我正在考虑使用它，但我不确定它是否真的满足我的所有要求。所以基本上，我想做的是把一个图分成几个子图。但是，每个子图的节点应该是连接的，也就是说，例如，如果我想到达节点 x，我必须通过另一个子图。这正是我所关心的。是否有可能，当我使用 Kernighan-Lin 算法拆分图时，子图的节点最终会分散在各处？

Answer 1

是的，K--L 可能会创建不连贯的子图。例如，它将 8 顶点星

* * *
 \|/
*-*-*
 /|
* *

分成两个 4 顶点子图，其中一个不包含中心的子图不一定是不连通的。我不知道你想在这个例子中发生什么。