python - 使用 Python 的图同态

Question

我的想法是编写一个 python 程序，它将两个有限简单无向图 G,H 作为参数，并返回从 G 到 H 的图同态的数字 hom(G,H)。

示例：如果 G=K_1（单顶点图），则 hom(G,H) 等于 H 的顶点数。如果 G=K_2（或等效为 P_2），则 hom(G,H) = 2 倍数H 的边数。

谁能帮帮我？谢谢。

Answer 1

一般来说，它是NP难的。如果图 G 有 n 个顶点，而图 H 有 m 个顶点，那么一种简单的方法可能是检查两个图之间的所有 n^m 个可能的分配函数。

这相当于在 上执行 m 个链式循环range(n)。

我知道在python中有两种方法：

1）您可以生成 m 个列表 [1...n] 并用于itertools.product获取这些列表之间的笛卡尔积。

exec2）您可以使用这些链式循环代码生成一个字符串，并使用内置函数在python中执行它。

如果您使用第一个解决方案，它是高度可并行化的。所以你可以加快很多。

没有并行化的第一个想法的实现将是这样的：

from itertools import product

def verify(G, H, f):
   homomorphism = True

   for edge in G:
       if not ((f[edge[0]], f[edge[1]]) in H):
           homomorphism = False
           break

   return homomorphism

def solve(G, H, n, m):
   rangeG = [i for i in range(n)]
   assignments = list(product(rangeG, repeat=m))
   cnt = 0

   for f in assignments:
       if verify(G, H, f):
           cnt += 1

   return cnt

这里的图G和H存储为一组元组。元组代表边。这种表示对于测试同态条件和快速应用赋值函数非常方便。参数n和m是每个图中的顶点数。

例如，如果你想要 G = S4 和 H = P4，它会是这样的：G = {(0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0)}和H = {(0, 1), (1, 0), (1, 2), (2, 1), (2, 3), (3, 2)}. 然后你调用函数solve(G, H, 4, 4)。

我用本文第 2.3 节的一些示例对其进行了测试，它似乎运行良好。

正如我所说，并行化可以大大提高速度。这段代码几乎在任何地方都是可并行的。它需要一些测试来查看并行执行的价值。