如何实现子图同构到图自同构的扩展可行性检测

核心思路 #

要解决这个问题，需要分四步处理：保留子图顶点的原图索引、约束子图同构的匹配规则、将子图映射转换为原图部分映射、验证部分映射能否扩展为原图自同构。

代码实现与说明 #

1. 基础代码修正与子图顶点索引保留 #

首先修正原图创建的语法错误，同时保存子图顶点在原图中的完整索引，避免子图索引重置导致的映射断裂：

import igraph as ig

def get_star(graph, init_vertex):
    """获取以指定顶点为中心的星型子图顶点列表"""
    return [init_vertex] + graph.neighbors(init_vertex)

# 创建5顶点环图（修正原代码的edges参数错误）
g = ig.Graph(n=5, edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]])

# 保存两个星型子图的原图顶点列表
sub1_vertices = get_star(g, 0)  # 结果：[0, 1, 4]
sub2_vertices = get_star(g, 3)  # 结果：[3, 2, 4]

# 创建子图
sub_g = g.subgraph(sub1_vertices)
sub_g2 = g.subgraph(sub2_vertices)

2. 约束子图同构的匹配规则 #

星型子图的同构应该满足中心顶点对应中心顶点，可以通过给顶点添加属性并在vf2算法中指定约束来过滤无效映射：

# 给子图顶点添加中心标记（区分中心和叶子）
sub_g.vs["is_center"] = [v == 0 for v in sub_g.vs.indices]
sub_g2.vs["is_center"] = [v == 0 for v in sub_g2.vs.indices]

# 获取符合中心匹配规则的子图同构
sub_isos = sub_g.get_subisomorphisms_vf2(
    sub_g2,
    vertex_color=sub_g.vs["is_center"],
    vertex_color2=sub_g2.vs["is_center"]
)

3. 转换子图映射为原图部分映射 #

利用保存的原图顶点列表，将子图内部的索引映射转换为原图顶点的键值对：

# 将子图同构转换为原图的部分映射
partial_maps = []
for iso in sub_isos:
    partial_map = {sub1_vertices[i]: sub2_vertices[iso[i]] for i in range(len(iso))}
    partial_maps.append(partial_map)

例如，此时得到的有效部分映射为{0:3, 1:2, 4:4}和{0:3, 1:4, 4:2}，明确了子图同构在原图中的对应关系。

4. 验证部分映射能否扩展为原图自同构 #

方法一：遍历所有自同构验证

适合小规模图，直接遍历原图所有自同构，检查是否存在包含当前部分映射的自同构：

# 获取原图所有自同构
automorphisms = g.get_automorphisms_vf2()

# 检查每个部分映射能否扩展
for idx, partial_map in enumerate(partial_maps):
    print(f"部分映射 {idx+1}: {partial_map}")
    can_extend = False
    for auto in automorphisms:
        valid = True
        for v, mapped_v in partial_map.items():
            if auto[v] != mapped_v:
                valid = False
                break
        if valid:
            can_extend = True
            print(f"  可扩展为自同构: {auto}")
            break
    if not can_extend:
        print(f"  无法扩展为原图自同构")

方法二：vf2初始映射约束验证

适合大规模图，无需生成所有自同构，直接通过vf2算法的初始映射约束高效判断：

def can_extend_to_automorphism(graph, partial_map):
    """检查部分映射能否扩展为图的自同构"""
    init_map = list(partial_map.items())
    # 在初始映射约束下查找自同构
    iso = graph.get_isomorphisms_vf2(graph, initial_map=init_map)
    return len(iso) > 0

# 验证每个部分映射
for idx, partial_map in enumerate(partial_maps):
    print(f"部分映射 {idx+1}: {partial_map}")
    if can_extend_to_automorphism(g, partial_map):
        print(f"  可扩展为原图自同构")
    else:
        print(f"  无法扩展为原图自同构")

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