网络图中节点的双染色

Question

我正在寻找一种很好的算法来在给定的网络图上执行2染色（即，在两种颜色之一中绘制网络中的每个节点，使得没有直接的节点对由边缘连接具有相同的颜色）。如果发生冲突，该算法应该从网络中删除节点，但要尽量减少被删除的节点的数量。有谁知道这样的算法是否可用（在Python或R中的实现将是一个很大的奖励）。

谢谢！

Answer 1

在每次迭代中在活动颜色之间交替的任何节点处启动BFS。颜色节点尚未访问。对每个连接的组件重复。

如果您到达已访问的节点u，并且颜色显示为当前未激活的颜色，则该图不是可着色的。

无法有效实施最佳节点删除。考虑一个带有至少3个辐条的轮子作为子图。一个集线器节点连接到偶数长度> = 4的周期的每个节点。要允许2种着色的最小节点数量为1，并且实现此目的的解决方案只有1个：移除集线器。

所以车轮检测是优化稀疏化的先决条件。

然而，this paper证明车轮检测是np完整的。