Kernighan-Lin算法 [英] Kernighan-Lin Algorithm

问题描述

有人因为我正在考虑使用它而对这个算法有点了解，但是我不确定它是否真的满足我的所有要求。所以基本上，我想做的是将一个图分成几个子图。但是，每个子图的节点都应该连接，也就是说，如果要到达节点x，则不必经过另一个子图。这正是我的关注。当我使用Kernighan-Lin算法拆分图时，子图的节点最终会散落到各处吗？

Does anybody know this algorithm a little bit, because I'm considering using it, but I'm not sure whether it really meets all my requirements. So bascially, what I want to do is splitting up a graph in several subgraphs. However the nodes of each subgraph should be connected, that is it should not be the case that for example if I want to reach node x I have to go through another subgraph. And that is exactly my concern. Is it possible, that when I split up a graph with the Kernighan-Lin algorithm, that the nodes of the subgraphs will end up scattered all over?

推荐答案

是的，K–L可能会创建断开连接的子图。例如，它分裂了8个顶点的星星

Yes, K--L may create disconnected subgraphs. For example, it splits the 8-vertex star

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

分为两个4个顶点子图，其中一个，不包含中心，不一定是连接的。我不知道您希望在此示例中发生什么。

into two 4-vertex subgraphs, of which one, the one not containing the center, is necessarily not connected. I don't know what you would want to happen on this example.

这篇关于Kernighan-Lin算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！