网络图中节点的二次着色
2-coloring of nodes in a network graph
我正在寻找一种很好的算法来对给定的网络图执行二次着色（即，用两种颜色中的一种绘制网络中的每个节点，使得由边直接连接的节点对没有相同的颜色颜色）。在发生冲突的情况下，该算法应从网络中删除节点，但尽量减少删除节点的数量。有谁知道这样的算法是否可用（Python 或 R 中的实现将是一个很大的好处）。
谢谢！
在每次迭代中交替激活颜色的任意节点启动 BFS。尚未访问的颜色节点。对每个连接的组件重复。
如果您到达一个节点 u，该节点已被访问并且用当前未激活的颜色着色，则该图不是 2-colorable。
无法有效实施最佳节点删除。考虑一个至少有 3 个辐条的轮子作为子图，即。连接到偶数长度 >= 4 的循环的每个节点的集线器节点。为了允许 2 着色要删除的最小节点数是 1，并且只有 1 个解决方案可以实现此目的：删除集线器。
因此车轮检测是最佳稀疏化的先决条件。
然而，this paper证明车轮检测是np完全的。
我正在寻找一种很好的算法来对给定的网络图执行二次着色（即，用两种颜色中的一种绘制网络中的每个节点，使得由边直接连接的节点对没有相同的颜色颜色）。在发生冲突的情况下，该算法应从网络中删除节点，但尽量减少删除节点的数量。有谁知道这样的算法是否可用（Python 或 R 中的实现将是一个很大的好处）。
谢谢！
在每次迭代中交替激活颜色的任意节点启动 BFS。尚未访问的颜色节点。对每个连接的组件重复。
如果您到达一个节点 u，该节点已被访问并且用当前未激活的颜色着色，则该图不是 2-colorable。
无法有效实施最佳节点删除。考虑一个至少有 3 个辐条的轮子作为子图，即。连接到偶数长度 >= 4 的循环的每个节点的集线器节点。为了允许 2 着色要删除的最小节点数是 1，并且只有 1 个解决方案可以实现此目的：删除集线器。
因此车轮检测是最佳稀疏化的先决条件。
然而，this paper证明车轮检测是np完全的。