寻找计算图节点的算法

Question

假设我有一个无向多图，即一个(G，E)对，其中G是一个有限的结点集，E是一个有限的边集。我正在寻找一个算法，将分配一个单一的字符串值到每个节点在以下的约束。

1.

每个节点都被赋予一组约束（可能是空的），这些约束限制了允许的值。我希望至少支持以下类型的值约束：

null

有两种类型的边缘：

• 不同，
• 相同，

这意味着应该为相关节点分配不同/相同的值（意味着不相等/相等的字符串）。

null

这意味着应该为给定节点分配一个不同于或等于给定节点的值。

我希望算法要么报告不一致（如果不存在这样的评估），要么返回任何（理想情况下是一个小的评估，即赋值由少量字符组成的评估）符合标准（否则）。

请注意，我并不期望您为我提供一个算法的详细描述。我将非常感谢您提供的任何提示，以使我走上正确的轨道。

Answer 1

几点建议：

>

您可以通过将由“相同”边连接的所有节点组合为单个节点来简化问题。（请注意，此单个节点的约束将是所有单个约束的并集。）

简化后的问题似乎与图形着色非常相似，因为您需要为每个节点选择标签，以便连接节点的标签是不同的。

null