如果你有一个算法将一般图形映射到字符串,并且当两个图形映射到相同的字符串时,并且只有它们在拓扑上是等价的,那么你有一个GRAPH AUTOMORPHISM算法.图自同构没有已知的多项式时间算法.所以你不能(很容易)一个多项式时间算法来计算你假设的字符串,因为否则你已经构建了一个以前未知且非常有效的图形自同构算法.
这并不意味着无法解决您的图类问题; 它只是意味着对于所有图形的类而言,它很难.
小智 4
您可能会发现以下问题相关......
基本上，可以使用自动机理论教科书中的众所周知的算法来最小化自动机。霍普克罗夫茨就是一个例子。恰好有一个最小自动机相当于任何给定的自动机。然而，该最小自动机可以用不同的方式表示。构造安全规范形式基本上是使用对定义自动机而言重要的信息（而不是特定于表示的信息）对节点进行重新编号和对邻接表进行排序的问题。
基本原理应该扩展到一般图表。是否可以最小化图取决于它们的语义，但对节点重新编号和对邻接列表进行排序的基本思想仍然适用。
这里的其他答案假设有关您的图的事情 - 例如，节点具有可以排序的唯一标签，并且这对于图的语义很重要，可用于识别邻接矩阵或列表中的节点。例如，如果您对未标记图的吗啡感兴趣，那么这根本行不通。对节点进行编号的不同方式（从而对邻接列表进行排序）将导致等效图的不同规范形式，而这些图恰好以不同的方式表示。
至于重新编号等，一种方法是借鉴和改编自动机最小化算法的原理。基本上...
创建块向量（节点集）。最初，为每一类节点（即每个不同的节点注释）填充一个块。这里的修改是我们通过注释详细信息（而不是特定于表示的节点 ID）对它们进行排序。
对于边缘的每个类别（注释），按顺序评估每个块。如果块中的每个节点都可以遵循当前的边类型到达下一个块的同一组，则保持不变。否则，根据需要对其进行分割以获得实现此目标的最大块。将这些分割块在向量中聚集在一起（保留现有的顺序，只是稍微细化一下），并根据下一个块集的适当顺序对分割块进行排序。例如，使用与当前块向量一样长的位向量，并通过遵循当前边缘类型为每个块设置一个可到达的位。要对位向量进行排序，请将它们视为大整数。
编辑-我忘了提及-在第二个项目符号中，一旦分割了一个块，您就可以使用矢量和第一个边缘注释中的第一个块重新启动。显然，简单的实现会很慢，因此采用该原理并用它来适应 Hopcrofts 最小化算法。
如果您最终得到的块中有多个节点，则这些节点是等效的。这是否意味着它们可以合并取决于您的语义，但每个此类块内节点的相对顺序显然并不重要。
如果处理可以最小化的图形（例如自动机有向图），我怀疑最好先最小化，尽管我自己还没有时间实现这一点。
当然，关键是确保您的重新编号仅对图形的重要细节（其结构和注释）敏感，而不是仅对那些可以构建表示（例如节点 ID/地址等）的内容敏感。 。
一旦您对块进行了排序，导出规范形式应该很容易。
| 归档时间： |
|
| 查看次数： |
2997 次 |
| 最近记录： |