寻找算法来评估图的节点

Question

假设我有一个无向多图，即一个（G，E）对，其中G是一个有限的节点集，E是一组有限的边。我正在寻找一种算法，可以在下列约束条件下为每个节点分配一个字符串值。

1.

每个节点被给予了限制允许值的限制（可能为空）集。我想至少支持以下类型的值约束：

• 最小长度（X）（该值是至少长给定字符数），
• 最大长度（x）的（该值至多是给定的字符长度）
• regexp（x）（该值符合给定的正则表达式），
• numeric（该值仅由数字组成）。

理想的情况下，应该可以增加对新类型的未来约束的支持。

2.

有两种类型的边：

• 不同，
• 相同，

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

3.

最后的每个节点可以被分配以下类型的约束的（可能为空）：

• 不同-从（X），
• 等于（X ），

这意味着给定节点应该被赋予一个不同于或等于给定节点的值。

---

我期望算法要么报告不一致（如果没有这样的评价存在）或返回任何（理想的是小一，即，一个在指定的值由一个小数目的字符的）的评价符合标准（否则）。

---

请注意，我不希望你为我提供算法的详细描述。我会很感激你提供的任何提示让我走上正轨。

Answer 1

几点建议：

• 您可以通过组合“相同的”边缘连接成一个单一节点的所有节点简化问题。 （请注意，这个单个节点的约束将是所有单个约束的联合。）

• 减少的问题看起来非常类似于graph colouring，因为您需要为每个节点选择标签，以便连接节点的标签不同。

• 不幸的是，图着色是NP完全问题，所以你可能很难得到一个高效的算法，除非你的节点的数量是相当小的

图着色是计算上。确定给定的图是否承认给定k的k染色是NP完全的，除了k = 1和k = 2的情况。特别是，计算色数是NP难的。三着色问题仍然是NP完全问题，甚至在平面度 图4

• 它可以帮助一下greedy colouring algorithms如果你并不一定需要一个完美的解决方案