请给我一个基于Python的用于图的同构识别的代码,其中输入两个图的邻接矩阵,输出是否同构,涉及到的测试有顶点的度是否相同,度相同的顶点数是否相同,顶点的数量是否相同
时间: 2024-02-24 15:00:43 浏览: 71
以下是一个基于Python的用于图的同构识别的代码,其中输入两个图的邻接矩阵,输出是否同构:
```python
import numpy as np
def is_isomorphic(A, B):
if A.shape != B.shape:
return False
n = A.shape[0]
deg_A = np.sum(A, axis=0)
deg_B = np.sum(B, axis=0)
if not np.array_equal(deg_A, deg_B):
return False
A_sorted = np.sort(A, axis=0)
B_sorted = np.sort(B, axis=0)
if not np.array_equal(A_sorted, B_sorted):
return False
for i in range(n):
if np.sum(A[i,:] != B[i,:]) == 0:
return False
return True
A = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
B = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
print(is_isomorphic(A, B)) # True
C = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
D = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
print(is_isomorphic(C, D)) # False
```
这段代码中,首先判断了两个输入矩阵的维度是否相同,如果不同则直接返回 False。然后计算了两个矩阵中每个顶点的度数,并进行比较。如果度数不同,则返回 False。接着对两个矩阵进行排序,并判断它们是否相同。如果不同,则返回 False。最后,对每一个顶点进行比较,如果有顶点的邻居不同,则返回 False。如果经过所有的比较都没有返回 False,则说明两个矩阵是同构的,返回 True。
阅读全文