关于图论中导出子图的概念
 
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
        
       
       
        =
       
       
        
         {
        
        
         
          a
         
         
          ,
         
         
          b
         
         
          ,
         
         
          c
         
        
        
         }
        
       
      
      
       {V_1} = \left\{ {a,b,c} \right\}
      
     
    V1​={a,b,c} ,则 $V_1$ 的导出子图 $G\left(V_1\right)$ 如图所示
 
 
导出子图 $G\left(V_1\right)$ ：
 
 
3、边导出子图
 
一个边子集以及这些边的所有端点构成的子图.
 
例子：
 
在图1中，设G如图1(a)所示，取 
    
     
      
       
        
         E
        
        
         1
        
       
       
        =
       
       
        
         {
        
        
         
          
           e
          
          
           1
          
         
         
          ,
         
         
          
           e
          
          
           3
          
         
        
        
         }
        
       
      
      
       {E_1} = \left\{ {e_1,e_3} \right\}
      
     
    E1​={e1​,e3​} ,则 $E_1$ 的导出子图 $G\left(E_1\right)$ 如图 所示
 
 
导出子图$G\left(E_1\right)$
 

问题描述
 
给定一个无向图 $G=(V,E)$ 和一个整数 $k$，试找到 $G$ 的最大规模的导出子图 $H=(U,F)$，其中 $H$ 中所有顶点的度大于或等于 $k$，或者说明不存在这样的子图。
 
归纳假设
 
假设在顶点数目小于 $n$ 时，我们已知如何找到所有顶点的度大于或等于 $k$ 的最大导出子图。
 
归纳证明
 
当 $n\le k$ 时，则所有度均小于 $k$，不存在这样的图。当 $n=k+1$ 时，则可以注意到所有度大于等于 $k$ 的唯一方式是一个完全图。
假定现在 $n$ 是平凡的情况，即 $n>k+1$。如果所有顶点的度大于或等于 $k$，则整个图满足要求。否则，存在一个顶点 $v$，其度小于 $k$。显然在任何 $G$ 的子图中，$v$ 的度都小于 $k$，因此 $v$ 不在任何满足原命题的子图中。所以把 $v$ 及其相连的边删除，不影响原命题。当 $v$ 被删除后，图中只有 $n-1$ 个顶点。由归纳假设，可知如何对该问题求解。
 
由1，2得：对与任意无向图 $G=(V,E)$ 和一个整数 $k$，均能完成求解任务。
 
算法实现
 
def Max_Subgraph(G, k):
    """ U (G的子图, None表示无这样的子图)
    
    Args:
        G (dict): 图的邻接表 e.g. {1:[2], 2:[1]}表示节点为2的完全图
        k (int): 度
    """
    Du_More_Than = lambda G, n: all([len(G[v]) >= n for v in G])
    Find_V = lambda G, n: [v for v in G if len(G[v]) < n]
    while True:
        if len(G) <= k: 
            return None
        if len(G) == k + 1:
        	return G if Du_More_Than(G, k) else None
        for v in Find_V(G, k):
            for u in G[v]:
                G[u].remove(v)
            del G[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。
 
 
生成子图（Spanning Subgraph）
 定义：生成子图G’中顶点个数V’必须和原图G中V的数量相同，而E’∈E即可。
 
 
导出子图(Induced Subgraph)
 定义：导出子图G’，V’∈V，但对于V’中任一顶点，只要在原图G中有对应边，那么就要出现在E’中。
 
 
举个栗子：