我已经连续在互联网上搜索了大约两三天，但到目前为止还没有运气。
我知道在野外有很多用于子图同构的库和实现，但它们都适用于未加权图。例如，两种最流行的算法是 VF2 和 Uleman 算法。在这里，我的问题是：是否有任何方法可以给出一个图（G）和一个查询图（g），是否可以找到 g 是否是 G 的子图（并且同构）？（请注意，以下是图的边缘列表表示。）
G
1 2 c
1 3 d
1 4 c
2 3 a
...
g
1 3 d
2 3 a
在这种情况下，g 是一个子图并且与 G 同构，但是如果我们有这样的东西：
g
1 3 t
2 3 a
现在 g 不再是 G 的子图并且不是同构的。
更新：两个图都是无向的。
g={(1 2 a)} 不与 G 同构，因为 G 中这条边的权重是“c”而不是“a”。
这很奇怪。简而言之，如果存在来自 {G<->G'} 的某个函数 f ，则图 G，G'（实际上是任何代数结构）是同构的，因此对于任何关系 R(g1, g2) (g1, g2 in G) , R'(f(g1), f(g2)) 也适用于 G'，反之亦然。因此，通过重命名（置换）顶点从 G 中获得的任何图 G' 都与 G 同构。
看起来，您感兴趣的是确定对于 g 的任何标记边缘是否存在连接相同顶点并在 G 中带有相同标记的边缘。最简单的方法是复制 G 的边缘并按组件对其进行排序。然后对于查询 g 的每条边，将花费 O(log(|G|)) 来检查 G 是否具有相同的边（并且它具有相同的标记）。因此，总时间是 O(|G|*log(|G|)) 来准备图 G 和 O(|g|*log(|G|)) 来处理每个后续查询。
更新： “按组件对 G 的边进行排序”我的意思是：构建一个边数组（或二叉树），按第一个顶点排序，然后按第二个顶点排序。要轻松搜索边缘，应该复制它。例如，边 (1, 2, c) 应该以 (1, 2, c) 和 (2, 1, c) 的形式出现。因此，以数组形式，上面示例中的 G 变为
(1, 2, c)
(1, 3, d)
(1, 4, c)
(2, 1, c)
(2, 3, a)
(3, 1, d)
(3, 2, a)
(4, 1, c)
事后考虑，最好先将 G 和 g 的两条边都写成具有较小数量的顶点 - 这样就不需要重复了。