更改

跳到导航 跳到搜索
删除12字节 、 2020年8月23日 (日) 10:12
第206行: 第206行:  
对于''n''个线段的相交图或'''<font color="#ff8000"> 欧几里得平面Euclidean plane</font>'''中的其他简单形状图,即使图本身可能具有多达''O''(''n²'')个边缘,也可以测试其是否而二分图,并在时间''O''(''n''log''n'')中返回双色(判定为二分图)或奇数环(判定为非二分图)。
 
对于''n''个线段的相交图或'''<font color="#ff8000"> 欧几里得平面Euclidean plane</font>'''中的其他简单形状图,即使图本身可能具有多达''O''(''n²'')个边缘,也可以测试其是否而二分图,并在时间''O''(''n''log''n'')中返回双色(判定为二分图)或奇数环(判定为非二分图)。
   −
=== Odd cycle transversal 奇环横贯图 ===
+
=== Odd cycle transversal 奇环横贯 ===
    
Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.[27] The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.[28] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
 
Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.[27] The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.[28] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
第212行: 第212行:  
Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.[27] The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.[28] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
 
Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.[27] The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.[28] The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
   −
奇环横贯图是一个'''<font color="#ff8000"> NP完全算法问题NP-complete algorithmic problem</font>'''(因不能用多项式算法而使问题无法解决的),在给定图形''G =(V,E)''和数字''k''的情况下,询问是否存在一组''k''个顶点,将其从''G''移除会导致生成为二分图。这个问题是'''<font color="#ff8000"> 固定参数可解Fixed-parameter tractable</font>'''的,这意味着存在一种算法,其运行时间可以由图形大小的多项式函数乘以增大系数k来确定。奇数循环遍历的名称源于:当且仅当图没有奇数环时,该图是二分图。因此,为了从图中删除顶点来获得二分图,就需要“命中所有奇数环”或找到所谓的奇环横贯集合。例如在图示中,图中的每个奇数环都包含蓝色(最底部)顶点,因此删除这些顶点就相当于删除了所有奇数环并留下一个二分图。
+
奇环横贯是一个'''<font color="#ff8000"> NP完全算法问题NP-complete algorithmic problem</font>'''(因不能用多项式算法而使问题无法解决的),在给定图形''G =(V,E)''和数字''k''的情况下,询问是否存在一组''k''个顶点,将其从''G''移除会导致生成为二分图。这个问题是'''<font color="#ff8000"> 固定参数可解Fixed-parameter tractable</font>'''的,这意味着存在一种算法,其运行时间可以由图形大小的多项式函数乘以增大系数k来确定。奇环横贯的名称源于:当且仅当图没有奇数环时,该图是二分图。因此,为了从图中删除顶点来获得二分图,就需要“命中所有奇数环”或找到所谓的奇环横贯集合。例如在图示中,图中的每个奇数环都包含蓝色(最底部)顶点,因此删除这些顶点就相当于删除了所有奇数环并留下一个二分图。
     
961

个编辑

导航菜单