寻找一种算法来评价的曲线图的节点 [英] Looking for an algorithm to evaluate nodes of a graph

问题描述

让我们假设我有一个无向多图，即（G，E）对，其中G是一个有限的节点集合，E是有限边集合。我在寻找一种算法，将在以下限制指定一个字符串值到每个节点。

Let's suppose I have an undirected multi-graph, i.e. a (G, E) pair, where G is a finite set of nodes and E is a finite set of edges. I am looking for an algorithm that would assign a single string value to each node under the following constraints.

1。

每一个节点都被赋予一个（可能为空）设定限制允许值的限制。我想支持的值约束至少有以下几种类型：

Every node is given a (possibly empty) set of constraints that restrict permissible values. I'd like to support at least the following types of value constraints:

• 最小长度（X）（该值至少字符长的给定数量），
• 的最大长度（X）（该值在字符的给定数量），
• 在正则表达式（X）（该值符合给定的正前pression），
• 数值（该值由数字只）。

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

Ideally it should be possible to add support for new types of constraints in future.

2。

有两种类型的边

• 不同，
• 一样，

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

meaning that the concerned nodes should be assigned different/same values (meaning non-equal/equal strings).

3。

最后每个节点可以分配一个（可能是空的）组下述类型的约束：

Finally every node can be assigned a (possibly empty) set of constraints of the following types:

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

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

meaning that the given node should be assigned a value different from or equal to the given one.

我期望算法要么报告一个不一致（如果没有这样的评价存在）或返回任​​何（理想的是小的，即，一个其中分配的值由一个小数量的字符）满足条件的评价（否则）。

I expect the algorithm to either report an inconsistency (if no such evaluation exists) or to return any (ideally a small one, i.e. one where the assigned values consist of a small number of characters) of the evaluations that meet the criteria (otherwise).

请注意，我不希望你提供一个算法的详细说明，对我来说。我很感谢任何提示，你可以提供让我在正确的轨道。

Please note that I don't expect you to provide a detailed description of an algorithm for me. I'd be grateful for any hints you could provide to get me on the right track.

推荐答案

几点建议：

• 您可以通过组合相同的边缘连接到一个单一节点的所有节点简化问题。 （请注意，此单节点的约束将所有的个体约束的并集。）

• You can simplify the problem by combining all nodes connected by "same" edges into a single node. (Note that the constraints for this single node will be the union of all the individual constraints.)

减少的问题似乎很相似，图着色，你需要选择标签对于每个节点，以使标签用于连接的节点不同。

The reduced problem seems very similar to graph colouring as you need to choose labels for each node such that the labels are different for connected nodes.

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

Unfortunately, graph colouring is NP complete so you may well struggle to get an efficient algorithm unless your number of nodes is quite small

图着色在计算上是困难的。它是NP完全问题，如果决定   一个给定的图承认除例为k的K-着色对于给定ķ   = 1和k = 2。尤其是，它是NP难题来计算色数。三着色问题仍然NP完全问题，甚至在平面   等级4的曲线图

Graph coloring is computationally hard. It is NP-complete to decide if a given graph admits a k-coloring for a given k except for the cases k = 1 and k = 2. In particular, it is NP-hard to compute the chromatic number. The 3-coloring problem remains NP-complete even on planar graphs of degree 4

• 在这可以帮忙看一下贪婪着色算法的，如果你并不一定需要一个完美的解决方案

• It may help to look at greedy colouring algorithms if you don't necessarily need a perfect solution

这篇关于寻找一种算法来评价的曲线图的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！