图同构的判断

更加详细的内容可以看：http://120.27.213.171/2022/03/28/%E5%9B%BE%E8%AE%BA/

同构的概念：假设 G=(V,E) 和 G1=(V1，E1) 是两个图，如果存在一个双射 m：V→V1 ，使得对所有的x,y∈V 均有 x,y∈E 等价于 m(x) m(y)∈E1 ，则称 G和 G1是同构的。

G图 G1图

如图，这是两个同构图。其关系满足图G{A->C, B->A, B->D, D->E, E->C}，图G1满足关系{A1->C1, B1->A1, B1->D1, D1->E1, E1->C1}。不难看出，图G与图G1是同构关系。当 G 同构带 G1后，这些顶点可能标号变了，但是如果在“旧”的图中有的关系，在“新”图中依然保留，只不过是“空间位置”变了。

1.充分条件：两个图的点集与边集之间分别存在一一对应关系（相同的关系E）。

2.必要条件：图同构问题一般可以分为四个不同的研究种类：精确图完全同构、精确子图同构、不精确图完全同构、不精确子图同构。证明已后面三者是NP-Complete问题，第一类问题还没有定论，一般认为是NP问题。这里讨论的是精确图完全同构。

图必须满足以下条件：

（1）.结点数相等。

（2）.边数相等。

（3）.对应节点的度相等（包括进度和出度）

(4) .节点对应的关系相同（包括重边和环）

（5）.在权值图与有向图内，各边的权值和对应的关系相同

3.判断方法：

（1）.我们可以从满足的条件来看首先可以从最简单，肉眼可见的顶点数开始看。如果G与G2同构，他们的阶和度必须完全相等，如果阶和度不相等就可以直接否定。其次，观察G和G2的双射关系，E(u, v) 需要等价于E1(u1, v1)。如果满足即可推断出两图重构。

（2）.也可以通过图的邻接矩阵来判断.一个图的邻接矩阵通过搜索，经过有限次的互换行或列的变换获得的映射关系E1，E2，如果E1 与 E2相等,则这两图同构。

4.图同构的搜索剪枝

我们可以使用DFS直接对图的双射关系和边，度数进行搜索（将双射映射为u->v的关系)，从而判断是否同构。但是，这样显然会出现大量的重复。我们可以在搜索前进行预处理,将图的边数和度数进行排序 (图的重构与判断双射顺序无关)，先从大的进行遍历。在大度数的情况下，更容易出现不符合的情况，直接返回这种情况，可以有效避免大量无效搜索。