关于图论中导出子图的概念
1、导出子图
A subgraph H is called an induced subgraph of X if for any $a,b \in E(H)$ if and only if $a,b \in E(X)$.
2、点导出子图
设S是V(G)的子集，以S为点集，以G的所有那些两端点都在S内的边组成边集，所得到的G的子图称为S在G中的导出子图，或更确切地，节点导出子图。（一个顶点子集以及两个端点都在这个子集中的所有边构成的子图）
例子：
在图1中，设G如图1(a)所示，取 ${V_1} = \left\{ {a,b,c} \right\}$ ,则 ${V_1}$ 的导出子图 $G\left( {{V_1}} \right)$ 如图所示

导出子图 $G\left( {{V_1}} \right)$ ：

3、边导出子图
一个边子集以及这些边的所有端点构成的子图.
例子：
在图1中，设G如图1(a)所示，取 ${E_1} = \left\{ {e_1,e_3} \right\}$ ,则 ${E_1}$ 的导出子图 $G\left( {{E_1}} \right)$ 如图 所示

导出子图$G\left( {{E_1}} \right)$

图 
 和图 
 的导出子图有哪些同构的问题可以看成一个约束满足问题(CSP) 
 ，CSP的详细定义见：约束规划，约束传播和CSP问题 
导出子图同构问题的形式化
简单地说，图 
 在 
 中的嵌入（embedding） 
 满足
(1)  
   ,
(2) 
  ,
(3) 
  ,
是 
 和 
 的某个导出子图的同构（把条件3去掉就是子图同构）
标准形式的导出子图同构问题
 的每个结点 
 都对应一个变量 
 ，因此可以定义双射 
 ，
变量集 
每个结点 
 的嵌入一定是 
 中的结点 
 ，因此变量
 对应的域为 
 ，
域集 
由条件（1）知，有约束条件 
由条件（2）知，对 
 ，有约束条件 
由条件（3）知，对 
 ，有约束条件 
综合以上3种约束，有约束集 
使用求解器求解同构问题
我们已经把导出子图同构对应的CSP问题
表示成了标准形式，因此可以使用求解器进行求解
OR-tools是谷歌开源的运筹学求解器库，详细介绍见：使用谷歌的OR-Tools求解鸡兔同笼 
networkx是python的一个图算法库，详细介绍见：python常用代码的第12和13节
以下代码使用OR-tools和networkx求解导出子图同构问题：
import networkx as nx
from ortools.sat.python import cp_model
from itertools import combinations
def var_from_domain(model, name, domain):
    "initialize a variable with integer domain defined by domain"
    domain = cp_model.Domain.FromIntervals([[i] for i in domain])
    val = model.NewIntVarFromDomain(domain, name)
    return val

# 五角星
G=nx.Graph([(1,3),(1,4),(2,4),(2,5),(3,5)])
# 五边形
S=nx.Graph([(1,2),(2,3),(3,4),(4,5),(5,1)])

model = cp_model.CpModel()

D = list(G.nodes)
X = {i:var_from_domain(model, "X("+str(i)+")", D) for i in S.nodes}

# 约束：嵌入 S -> subgraph of G
model.AddAllDifferent([X[i] for i in S.nodes])
E_G = list(G.edges) + [e[::-1] for e in G.edges]
for v1, v2 in combinations(S.nodes,2):
    if (v1,v2) in S.edges:
        model.AddAllowedAssignments((X[v1],X[v2]), E_G)
    else:
        model.AddForbiddenAssignments((X[v1],X[v2]), E_G)

solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.FEASIBLE:
    print("有嵌入:")
    for v, x in X.items():
        print('f(%s)=%i' % (v, solver.Value(x)))
else:
    print("不存在导出子图同构")

图 
 和图 
 的导出子图有哪些同构的问题可以看成一个约束满足问题(CSP) 
 ，CSP的详细定义见：约束规划，约束传播和CSP问题 
导出子图同构问题的形式化
简单地说，图 
 在 
 中的嵌入（embedding） 
 满足
(1)  
   ,
(2) 
  ,
(3) 
  ,
是 
 和 
 的某个导出子图的同构（把条件3去掉就是子图同构）
标准形式的导出子图同构问题
 的每个结点 
 都对应一个变量 
 ，因此可以定义双射 
 ，
变量集 
每个结点 
 的嵌入一定是 
 中的结点 
 ，因此变量
 对应的域为 
 ，
域集 
由条件（1）知，有约束条件 
由条件（2）知，对 
 ，有约束条件 
由条件（3）知，对 
 ，有约束条件 
综合以上3种约束，有约束集 
使用求解器求解同构问题
我们已经把导出子图同构对应的CSP问题
表示成了标准形式，因此可以使用求解器进行求解
OR-tools是谷歌开源的运筹学求解器库，详细介绍见：使用谷歌的OR-Tools求解鸡兔同笼 
networkx是python的一个图算法库，详细介绍见：python常用代码的第12和13节
以下代码使用OR-tools和networkx求解导出子图同构问题：
import networkx as nx
from ortools.sat.python import cp_model
from itertools import combinations
def var_from_domain(model, name, domain):
    "initialize a variable with integer domain defined by domain"
    domain = cp_model.Domain.FromIntervals([[i] for i in domain])
    val = model.NewIntVarFromDomain(domain, name)
    return val

# 五角星
G=nx.Graph([(1,3),(1,4),(2,4),(2,5),(3,5)])
# 五边形
S=nx.Graph([(1,2),(2,3),(3,4),(4,5),(5,1)])

model = cp_model.CpModel()

D = list(G.nodes)
X = {i:var_from_domain(model, "X("+str(i)+")", D) for i in S.nodes}

# 约束：嵌入 S -> subgraph of G
model.AddAllDifferent([X[i] for i in S.nodes])
E_G = list(G.edges) + [e[::-1] for e in G.edges]
for v1, v2 in combinations(S.nodes,2):
    if (v1,v2) in S.edges:
        model.AddAllowedAssignments((X[v1],X[v2]), E_G)
    else:
        model.AddForbiddenAssignments((X[v1],X[v2]), E_G)

solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.FEASIBLE:
    print("有嵌入:")
    for v, x in X.items():
        print('f(%s)=%i' % (v, solver.Value(x)))
else:
    print("不存在导出子图同构")

所有的顶点和边都属于图G的图称为G的子图。含有G的所有顶点的子图称为G的生成子图。 设V1是V的一个非空子集，以V1为顶点集，以两端点均在V1中的边的全体为边集的子图称为G的导出子图，记作G[V1]。导出子图G[V\V1]记为G-V1，它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v}，则把G-{v}简记为G-v， 称为主子图。在图1-13中，G1是G的生成子图，G2是G的导出子图，G3是G的主子图。