用于求解逻辑方程组的广度优先搜索算法

Question

我试图为下面的例子中的问题设想一个解决方案:

A != B
B != C
D != B
C != B
E != D
E != A

有多少变量是真的,有多少是假的？据我所知,我应该尝试使用广度优先搜索,但我的问题是从哪里开始,图形将是一个定向的事实(我连接xi到!xj存在相等关系的地方).有人能指出我正确的方向吗？

Answer 1

这是一个图2着色问题.顶点:A, B, C, …边(u, v)在这个无向图当且仅当u != v.