检测一组非严格不等式中的不一致性
Detecting inconsistency in a set of non-strict inequalities
给定一组变量和一组严格的不等式，检测是否存在不一致就足够简单了：制作一个节点为变量的有向图；对于每个断言 a > b 添加一条从 a 到 b 的边，反之亦然 a < b；检查图表中是否有循环。
然而，这对于非严格不等式是不够的；上面的算法不处理你有一些断言的情况 a = b.
检测一组非严格不等式中的不一致性的最简单算法是什么？
这种方式可行：
- 将每个
x=y 替换为 x>=y 和 y>=x
- 在变量之间创建一个有向图，如果
x>=y，绿色边从x到y，红色边从x到y 如果 x>y
- 确定图中的强连通分量，例如使用Tarjan's algorithm
- 如果任何 SCC 中有红色边缘，则方程组不一致。
其工作方式很简单：在 >= 条边的任何循环中，所有变量都必须相等，但如果其中一条边要求它们不相等，则这是不可能的。
给定一组变量和一组严格的不等式，检测是否存在不一致就足够简单了：制作一个节点为变量的有向图；对于每个断言 a > b 添加一条从 a 到 b 的边，反之亦然 a < b；检查图表中是否有循环。
然而，这对于非严格不等式是不够的；上面的算法不处理你有一些断言的情况 a = b.
检测一组非严格不等式中的不一致性的最简单算法是什么？
这种方式可行：
- 将每个
x=y替换为x>=y和y>=x - 在变量之间创建一个有向图，如果
x>=y，绿色边从x到y，红色边从x到y如果x>y - 确定图中的强连通分量，例如使用Tarjan's algorithm
- 如果任何 SCC 中有红色边缘，则方程组不一致。
其工作方式很简单：在 >= 条边的任何循环中，所有变量都必须相等，但如果其中一条边要求它们不相等，则这是不可能的。