匹配两个相同标记图的顶点
Match the vertices of two identical labelled graphs
我有一个相当简单的问题要定义，但到目前为止我还没有找到简单的答案。
我有两个相同的图（即顶点和边的集合）。他们每个人都有独立标记的顶点。看下面的例子：
计算机如何在事先不知道的情况下检测到 1 等于 9、2 等于 10 等等？
请注意，在对称的情况下，可能有几种可能的一对一配对可以给出完全等价的结果，但仅找到其中一种对我来说就足够了。
这是在 Python 实现的上下文中。有人有指向 Internet 上公开可用的简单算法的指针吗？这个问题听起来很简单，但我只是缺乏数学知识来自己解决或找到合适的关键字来查找信息。
编辑：请注意，我还有每个图的原子类型（即标签），以及两个图对齐的完整距离矩阵。但是位置可能相似但不完全相等。
这被称为graph isomorphism problem，而且可能很难；虽然究竟有多难的细节仍有待研究。
（但是如果你的图表是平面的，事情 look better。）
所以，在稍微搜索之后，我认为我找到了一个在大多数情况下都适用的解决方案，而且计算成本适中。这是一种使用了一点随机性的遗传算法，但对于我的目的来说它似乎足够实用。到目前为止，我的样本没有任何异常配置，即使理论上可能会发生这种情况。
我是这样处理的：
- 确定2路、3路、4路的完整集合
- 同时使用原子类型和周围拓扑确定顶点类型，为每个顶点创建一张“身份证”
重复以下十次：
- 从符合允许的顶点类型的一组随机候选配对开始
- 通过为每个对应的顶点打分（也使用原子类型作为附加描述符）来评估两对之间有多少 2 路径、3 路径和 4 路径对应
- 通过以相同方式排列该候选与其其他位置的配对，评估给定顶点的所有其他入围候选
- 按分数降序排列
- 对于每个分数，检查该配置是否在排除配置中，如果不是，则将其作为新配置放入排除配置中。
- 如果分数是完美的（即所有的2-paths，3-paths和4-paths都对应），则停止循环并计算两个图的距离矩阵之间的绝对差之和以进行配对使用选定的配对，否则返回 4。
完成 10 次后停止此过程
- 检查距离矩阵之间的差异，并采用与距离矩阵之间的绝对差异的最小和相关联的配对。
我有一个相当简单的问题要定义，但到目前为止我还没有找到简单的答案。
我有两个相同的图（即顶点和边的集合）。他们每个人都有独立标记的顶点。看下面的例子：
计算机如何在事先不知道的情况下检测到 1 等于 9、2 等于 10 等等？
请注意，在对称的情况下，可能有几种可能的一对一配对可以给出完全等价的结果，但仅找到其中一种对我来说就足够了。
这是在 Python 实现的上下文中。有人有指向 Internet 上公开可用的简单算法的指针吗？这个问题听起来很简单，但我只是缺乏数学知识来自己解决或找到合适的关键字来查找信息。
编辑：请注意，我还有每个图的原子类型（即标签），以及两个图对齐的完整距离矩阵。但是位置可能相似但不完全相等。
这被称为graph isomorphism problem，而且可能很难；虽然究竟有多难的细节仍有待研究。
（但是如果你的图表是平面的，事情 look better。）
所以，在稍微搜索之后，我认为我找到了一个在大多数情况下都适用的解决方案，而且计算成本适中。这是一种使用了一点随机性的遗传算法，但对于我的目的来说它似乎足够实用。到目前为止，我的样本没有任何异常配置，即使理论上可能会发生这种情况。
我是这样处理的：
- 确定2路、3路、4路的完整集合
- 同时使用原子类型和周围拓扑确定顶点类型，为每个顶点创建一张“身份证”
重复以下十次：
- 从符合允许的顶点类型的一组随机候选配对开始
- 通过为每个对应的顶点打分（也使用原子类型作为附加描述符）来评估两对之间有多少 2 路径、3 路径和 4 路径对应
- 通过以相同方式排列该候选与其其他位置的配对，评估给定顶点的所有其他入围候选
- 按分数降序排列
- 对于每个分数，检查该配置是否在排除配置中，如果不是，则将其作为新配置放入排除配置中。
- 如果分数是完美的（即所有的2-paths，3-paths和4-paths都对应），则停止循环并计算两个图的距离矩阵之间的绝对差之和以进行配对使用选定的配对，否则返回 4。
完成 10 次后停止此过程
- 检查距离矩阵之间的差异，并采用与距离矩阵之间的绝对差异的最小和相关联的配对。