精华内容
下载资源
问答
  • 关于图论中导出子图的概念 1、导出子图 A subgraph H is called an induced subgraph of X if for any a,b∈E(H)a,b \in E(H)a,b∈E(H) if and only if a,b∈E(X)a,b \in E(X)a,b∈E(X). 2、点导出子图 设S是V(G)的...

    关于图论中导出子图的概念

    1、导出子图

    A subgraph H is called an induced subgraph of X if for any a,bE(H)a,b \in E(H) if and only if a,bE(X)a,b \in E(X).

    2、点导出子图

    设S是V(G)的子集,以S为点集,以G的所有那些两端点都在S内的边组成边集,所得到的G的子图称为S在G中的导出子图,或更确切地,节点导出子图。(一个顶点子集以及两个端点都在这个子集中的所有边构成的子图)

    例子:

    在图1中,设G如图1(a)所示,取 V1={a,b,c}{V_1} = \left\{ {a,b,c} \right\} ,则 V1{V_1} 的导出子图 G(V1)G\left( {{V_1}} \right) 如图所示

    图1(a)

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

    图1(b)

    3、边导出子图

    一个边子集以及这些边的所有端点构成的子图.

    例子:

    在图1中,设G如图1(a)所示,取 E1={e1,e3}{E_1} = \left\{ {e_1,e_3} \right\} ,则 E1{E_1} 的导出子图 G(E1)G\left( {{E_1}} \right) 如图 所示

    图1(a)

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

    图1(c)

    展开全文
  • 图 和图 的导出子图有哪些同构的问题可以看成一个约束满足问题(CSP) ,CSP的详细定义见:约束规划,约束传播和CSP问题 导出子图同构问题的形式化简单地说,图 在 中的嵌入(embedding) 满足(1) ,(2) ,(3) ,是 和 的...

    和图
    的导出子图有哪些同构的问题可以看成一个约束满足问题(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) ,是 和 的...

    和图
    的导出子图有哪些同构的问题可以看成一个约束满足问题(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("不存在导出子图同构")
    展开全文
  • 关于图论中的导出子图作了一些比较容易懂得解释,我看网上有各种版本的甚至还有些错误的的,所以自己查询了一些资料对这些概念进行了图文解释。
  • 子图,生成子图和导出子图

    万次阅读 2016-10-08 23:46:43
    设V1是V的一个非空子集,以V1为顶点集,以两端点均在V1中的边的全体为边集的子图称为G的导出子图,记作G[V1]。导出子图G[V\V1]记为G-V1,它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v},则...

    所有的顶点和边都属于图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的主子图。


    展开全文
  • 首先给出一些定义。原图G用G = (V, E)表示,V是G中的所有顶点的集合;E是G中所有边的集合。 子图 定义:子图G’中所有的顶点和边均包含于原图G。即E’∈E,并且V’∈V。...定义:导出子图G’,V’∈V,但对...
  •  设V1是V的一个非空子集,以V1为顶点集,以两端点均在V1中的边的全体为边集的子图称为G的导出子图,记作G[V1]。导出子图G[V\V1]记为G-V1,它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v},...
  • Gyárfás曾猜想:对于每一个不含森林[F]作为导出子图的图[G],存在整数函数[f(F,ω(G))]使得[χ(G)f(F,ω(G))],其中[χ(G)]和[ω(G)]分别表示图的色数和团数。以强完美图定理为基础,通过对不含[3K1 K2]和[C4]...
  • 给定一个无向图 G=(V,E)G=(V,E)G=(V,E) 和一个整数 kkk,试找到 GGG 的最大规模的导出子图 H=(U,F)H=(U,F)H=(U,F),其中 HHH 中所有顶点的度大于或等于 kkk,或者说明不存在这样的子图。 归纳假设 假设在顶点数目...
  • Aizu 2306 Rabbit Party 爆搜顶点导出子图

    千次阅读 2014-12-04 16:26:23
    选择一个顶点导出子图,该子图的每个点点权为 该点连接的最小边权。 找一个这样的子图使得点权和最大,输出点权和。 思路: 因为是一个完全图,所以我们选择的点构成的图一定不包含权值为0的边。因为若包含了权值...
  • 求这张图上的所有导出子图中有多少棵树。 解题思路 条件可以转换为这些区间联通并且没有一个位置被333个区间同时覆盖。 那么如果一个包含关系出现在这个图里,那么被包含的那个一定是作为叶子的。所以可以按照左...
  • AtCoder Beginner Contest 173 F - ...f(L,R)f(L,R)f(L,R):顶点集 V′={L,L+1,L+2,⋯ ,R}V'=\{L, L+1, L+2,\cdots,R\}V′={L,L+1,L+2,⋯,R}的导出子图(由 顶点集 V′V'V′ 和 两端点都在顶点集 V′V'V′中的边
  • 题意简述:给定一张无向图和一个数,求一个最大的子图,使得删掉原图中其他点后,子图中每个点的点度都大等。要求输出子图大小和子图中的每个点,若无解输出,若存在多解输出任意一组解。 题目让我们求一个子图,最...
  • 模型转化,dp
  • 归纳法之导出子图

    2010-07-08 09:59:00
  • ....
  • 2.点导出子图与边导出子图导出子图导出子图 3.图的生成子图 二、图运算 1.图的删点、删边运算 删点运算 删边运算 2.图的并运算 3.图的交运算 4.图的差运算 5.图的对称差运算或环和运算 6.图的联运...
  • LOJ10092半连通子图

    2019-04-19 15:30:00
    Description  一个有向图G=(V,E)称为半连通的(Semi-Connected),如果...V,E'是E中所有跟V'有关的边,则称G'是G的一个导出子图。若G'是G的导出子图,且G'半连通,则称G'为G的半连通子图。若G'是G所有半连通子...
  • AcWing 1175 题目描述 一个有向图 G=(V,E) 称为半连通的 (Semi-Connected),如果满足:∀...若 G′=(V′,E′) 满足,E′ 是 E 中所有和 V′ 有关的边,则称 G′ 是 G 的一个导出子图。 若 G′ 是 G 的导出子图,且 G...
  • Description  一个有向图G=(V,E)称为半连通的(Semi-Connected),如果满足:?u,v∈V,满足u→v或v→u,即对于图中任意 两点u,v,存在一条u到v的有...若G'是G的导出子图,且G'半连通,则称G'为G的半连通子图。若G...
  • 若 G′=(V′,E′) 满足,E′ 是 E 中所有和 V′ 有关的边,则称 G′ 是 G 的一个导出子图。 若 G′ 是 G 的导出子图,且 G′ 半连通,则称 G′ 为 G 的半连通子图。 若 G′ 是 G 所有半连通子图中包含节点数最多的,...
  • 子图是什么

    千次阅读 2018-12-12 19:47:36
    子图和真子图  设 G = <V, E>, = <, >是两个图(同为无向,或同为有向图). ... 若 V 且 E, 则称 为 G 的子图, G 为 的母图, 记作 ...两个导出子图  设 V 且 (空集), ...
  • 最大半连通子图 【问题描述】 一个有向图G = (V,E)称为半连通的(Semi-Connected),...若满足,则称G’是G的一个导出子图。 若G’是G的导出子图,且G’半连通,则称G’为G的半连通子图。 若G’是G所有半连通子...
  • [GDOI2018]滑稽子图

    2019-03-09 12:52:00
    题目大意:对于一棵树$(V,E)$,对于$S\subset V$,$f(S)$为点集$S$的导出子图的边数。求$\sum_{S\subset V}f(S)^k$ 这里的导出子图说的是,点集为S,边集为$\{(u,v)\in E|u,v\in S\}$的一个子图。 看到这个$k$...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 216
精华内容 86
关键字:

导出子图