使用Python的图同态

Question

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

例子:如果G=K_1(单顶点图)那么hm (G,H)等于H的顶点数。若G=K_2(或等价的P_2)，则hm (G,H) = 2倍H的边数

谁能帮我一下吗?谢谢。

Answer 1

一般来说这是NP-hard。如果图G有n个顶点，图H有m个顶点，一种简单的方法是检查这两个图之间所有n^m个可能的赋值函数。

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

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

1)你可以生成m个列表[1…n]，并使用itertools.product得到这些列表之间的笛卡尔积。

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

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

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

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节的一些例子测试了它，它似乎运行良好。

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