如何在NetworkX中从一个图生成其同构图？

NetworkX本身没有专门的函数直接生成同构图，但可以通过节点置换重命名的方式轻松实现——毕竟同构图的核心就是节点标签不同但拓扑结构完全一致。

具体实现思路和代码示例如下：

• 先获取原图的节点列表，对节点进行随机（或指定）置换，生成原节点到新节点的映射字典
• 用NetworkX的nx.relabel_nodes()函数基于这个映射生成新图，得到的就是原图的同构图

import networkx as nx
import random

# 构造示例原图（这里以5节点完全图为例）
original_graph = nx.complete_graph(5)

# 生成随机节点置换映射：将原节点打乱顺序作为新节点标签
nodes = list(original_graph.nodes())
shuffled_nodes = random.sample(nodes, len(nodes))
node_mapping = dict(zip(nodes, shuffled_nodes))

# 生成同构图
isomorphic_graph = nx.relabel_nodes(original_graph, node_mapping)

# 验证同构性，输出应为True
print(nx.is_isomorphic(original_graph, isomorphic_graph))

如果需要固定的节点置换，直接手动定义node_mapping即可，比如node_mapping = {0: 'a', 1: 'b', 2: 'c'}，生成的新图同样和原图同构。

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