图同态使用 Python

Question

我的想法是编写一个 python 程序，它将两个有限简单无向图作为参数，例如 G,H 和 returns 来自 G 的图同态数 hom(G,H)到 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 可能的赋值函数。

这相当于在 range(n).

上执行 m 链式循环

我在 python 中知道两种方法：

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

2)您可以使用这些链式循环代码生成一个字符串，并使用 exec 内置函数在 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).

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

正如我所说，并行化可以大大提高速度。此代码几乎在任何地方都可以并行化。它需要一些测试来了解什么值得并行执行。

图同态使用 Python

Graph Homomorphism using Python

python

graph-theory

undirected-graph

homomorphism