图同构测试：原理、算法与实现

# 图同构测试：原理、算法与实现 ## 1. 图同构的基本概念 在图论中，若能对一个图的节点进行重新标记，使得两个图完全相同，那么这两个图就被称为同构的。图同构测试在许多领域都有重要应用，如网络分析、化学结构识别等。下面将介绍一种用于测试两个无向简单图是否同构的方法。 ### 1.1 矩阵索引比较规则 对于矩阵的两个索引 `(u1, v1)` 和 `(u2, v2)`，比较规则如下： - 若 `max(u1, v1) < max(u2, v2)`，则 `(u1, v1) < (u2, v2)`。 - 若 `max(u1, v1) = max(u2, v2)` 且 `u1 < u2`，则 `(u1, v1) < (u2, v2)`。 在这种特定的矩阵索引顺序下，矩阵 `P` 小于或等于矩阵 `Q` 的条件是：要么 `P` 和 `Q` 的每个元素都相等，要么在第一个不同的矩阵元素 `(i, j)` 处，有 `Pi,j < Qi,j`。 ### 1.2 图代码的定义 图代码被定义为图的所有邻接矩阵中的最大矩阵。通过计算两个图的代码，可以进行图同构测试。这里使用回溯法来检查图节点的所有可能排列。从节点的恒等排列开始，考虑第一个节点与第二个节点交换的所有排列。在某些情况下，如果邻接矩阵的一部分足以确定该矩阵小于当前的最优解，则可以跳过当前搜索，直接进入枚举中的下一个候选解。 ## 2. 图同构测试的参数和返回值 ### 2.1 函数参数 | 参数 | 类型 | 说明 | | ---- | ---- | ---- | | `n` | `int` | 每个图中的节点数，节点编号从 1 到 `n`。 | | `adj1` | `int[n+1][n+1]` | 第一个图的邻接矩阵，元素为 0 或 1。只需要 `adj1[i][j]`（`i = 1, 2, …, n`，`j = 1, 2, …, n`）的值。 | | `adj2` | `int[n+1][n+1]` | 第二个图的邻接矩阵，元素为 0 或 1。只需要 `adj2[i][j]`（`i = 1, 2, …, n`，`j = 1, 2, …, n`）的值。 | | `map1`, `map2` | `int[n+1]` | 如果两个图同构（函数返回 0），这两个数组将返回实现同构的两个图的节点重新标记。即，通过将第一个图的节点 `map1[i]` 重新标记为第二个图的节点 `map2[i]`，或者反之，可以使两个图相同。 | ### 2.2 函数返回值 | 返回值 | 说明 | | ---- | ---- | | 0 | 两个图同构 | | 1 | 非同构，边的数量不同 | | 2 | 非同构，节点度序列不同 | | 3 | 非同构，图代码不同 | | 4 | 非同构，图代码计算错误 | ## 3. 图同构测试的 Java 实现 ### 3.1 `graphIsomorphism` 函数 ```java public static int graphIsomorphism(int n, int adj1[][], int adj2[][], int map1[], int map2[]) { int i,j,k,edges1,edges2; int label1[][] = new int[n + 1][n + 1]; int label2[][] = new int[n + 1][n + 1]; int degree1[] = new int[n + 1]; int degree2[] = new int[n + 1]; // validate the number of edges edges1 = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) edges1 = (i == j) ? edges1 + 2 * adj1[i][j] : edges1 + adj1[i][j]; edges1 /= 2; edges2 = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) edges2 = (i == j) ? edges2 + 2 * adj2[i][j] : edges2 + adj2[i][j]; edges2 /= 2; if (edges1 != edges2 ) return 1; // validate the degree sequences // node degrees of the first graph are ordered in decreasing order for (i=1; i<=n; i++) degree1[i] = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) degree1[i] += adj1[i][j]; // sort "degree1" in descending order GraphAlgo.heapsort(n, degree1, false); // node degree of the second graph are ordered in decreasing order for (i=1; i<=n; i++) degree2[i] = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) degree2[i] += adj2[i][j]; // sort "degree2" in descending order GraphAlgo.heapsort(n, degree2, false); // compare the degree sequence of the two graphs k = 1; while (k <= n) { if (degree1[k] < degree2[k]) return 2; k++; } // compute the code of the first graph if (!isomorphicCode(adj1, n, label1, map1)) return 4; // compute the code of the second graph if (!isomorphicCode(adj2, n, label2, map2)) return 4; // compare the codes of the two graphs for (j=2; j<=n; j++) for (i=1; i<=j-1; i++) if (label1[i][j] != label2[i][j]) return 3; return 0; } ``` ### 3.2 函数流程说明 ```mermaid graph TD; A[开始] --> B[验证边的数量]; B - ```