我的想法是编写一个 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 的边数。
谁能帮帮我?谢谢。
我的想法是编写一个 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 的边数。
谁能帮帮我?谢谢。
一般来说,它是NP难的。如果图 G 有 n 个顶点,而图 H 有 m 个顶点,那么一种简单的方法可能是检查两个图之间的所有 n^m 个可能的分配函数。
这相当于在 上执行 m 个链式循环range(n)
。
我知道在python中有两种方法:
1)您可以生成 m 个列表 [1...n] 并用于itertools.product
获取这些列表之间的笛卡尔积。
exec
2)您可以使用这些链式循环代码生成一个字符串,并使用内置函数在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 节的一些示例对其进行了测试,它似乎运行良好。
正如我所说,并行化可以大大提高速度。这段代码几乎在任何地方都是可并行的。它需要一些测试来查看并行执行的价值。