为何R包igraph判定这两个图非同构？

咱们先把完整可运行的代码补全，方便复现问题：

library(igraph)

# 初始版本的边集合
e1 = c(1,2,1,5,2,1,2,5,2,6,3,5,5,1,5,2,5,3,5,6,6,2,6,5)
e2 = c(1,2,1,3,1,4,1,5,2,1,2,5,3,1,3,5,4,1,5,1,5,2,5,3)

G1 = make_graph(e1)
G2 = make_graph(e2)

# 首次同构检查
isomorphic(G1,G2)  # 返回 FALSE

# 修改后的e1（把6替换为4）
e1_modified = c(1,2,1,5,2,1,2,5,2,4,3,5,5,1,5,2,5,3,5,4,4,2,4,5)
G1_modified = make_graph(e1_modified)

# 再次检查同构
isomorphic(G1_modified, G2)  # 返回 TRUE

为什么首次检查显示非同构？ #

核心原因很直白：两个图的节点数量不一样。

• 初始的e1里包含节点6，所以G1是一个拥有6个节点（1-6）的图；
• 而e2里最大的节点是5，所以G2只有5个节点（1-5）。

根据图论的基本规则，同构的图必须满足节点数、边数完全一致，并且节点的邻接关系能通过重新标号一一对应。节点数量不同的图，根本不可能同构，这就是第一次检查返回FALSE的本质原因。

为什么修改后显示同构？ #

把e1里的6全部替换为4之后：

• G1_modified的节点范围变成了1-5，和G2的节点数一致；
• 此时两个图的边数、各节点的度数分布完全匹配，而且邻接结构可以通过节点重排一一对应——比如G1_modified里的节点4，和G2里的节点3/4的邻接关系完全重合，自然会被判定为同构，所以isomorphic()函数返回TRUE。

说白了，初始版本就是不小心多引入了一个节点6，导致两个图规模不匹配，修改后规模一致且结构对应，就符合同构的判定条件了。

内容的提问来源于stack exchange，提问作者user3635700