Graph isomorphism

题目

Two graphs G1(N1,E1) and G2(N2,E2) are isomorphic if there is a bijection f: N1 -> N2 such that for any nodes X,Y of N1, X and Y are adjacent if and only if f(X) and f(Y) are adjacent.

Write a predicate that determines whether two graphs are isomorphic. Hint: Use an open-ended list to represent the function f.

图同构

图同构(Graph Isomorphism)描述的是图论中，两个图之间的完全等价关系。在图论的观点下，两个同构的图被当作同一个图来研究。

定义

只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图$G$和$H$称为是同构的，若且唯若存在一个将 $G$的节点${\displaystyle 1,\ldots ,n}$映射到$H$的节点${\displaystyle 1,\ldots ,n}$的一一对应 $\sigma$，使得$G$中任意两个节点$i$和 $j$相连接，若且唯若 $H$中对应的两个节点${\displaystyle \sigma (i)}$和${\displaystyle \sigma (j)}$相连接。如果$G$和$H$是有向图，那么同构的定义中还进一步要求对于$G$中任意两个相连的节点$i$和 $j$，边 $(i,j)$与它在$H$中对应的边${\displaystyle (\sigma (i),\sigma (j))}$方向相同。类似地可以定义两个多重图的同构关系。

一个具体的例子如下，为方便起见，两图中对应节点被染成了相同的颜色：

图G	图H	从图$G$到图$H$的同构映射$\sigma$
		$\sigma(a)=1 \\ \sigma(b)=6 \\ \sigma(c)=8 \\ \sigma(d)=3 \\ \sigma(g)=5 \\ \sigma(h)=2 \\ \sigma(i)=4 \\ \sigma(j)=7$

要注意的一点是，在图论中，一幅图经常可以有多种不同的方式在纸上或屏幕上画出来，所以两个看起来很不同的图也可能是同构的。尤其当图的节点数比较大时，很难一眼从画出的图上判断它们是否同构。

图同构问题

在计算机科学、数学和统计学中，图同构问题是复杂度理论研究中经常讨论的热点话题之一。图同构问题容易和图匹配问题混淆：

• 判定图同构(Graph Isomorphism)问题：只需判断两个图之间是否是同构的，但如果同构的话，并不要求具体找出任何做成同构的对应关系
• 图匹配(Graph Matching)问题：判断两个图是否同构，如果同构，找出至少一个使得两者做成同构的节点间的一一对应关系

解题思路

先用回溯法罗列所有两个图点集之间的映射，再逐一检测每个映射是否支持两图为同构图。

代码实现

首先使用回溯法罗列出所有点集到点集的映射。

然后，逐一检测每一个映射，是否有映射满足图同构映射要求。即图A中每一个点的相邻点在图B中的映射，分别等于图A点在图B中映射点的相邻点。

完整代码：

functools.reduce

reduce是Python标准库提供的一个函数式的工具，其声明为：

reduce(function, iterable, initializer)

其功能是将function累积地、从左往右作用于iterable中的每一个元素。

reduce相当于如下代码：

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

参考

• 图同构