961
个编辑
更改
→Odd cycle transversal 奇数循环遍历
对于''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.
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来确定。奇环横贯的名称源于：当且仅当图没有奇数环时，该图是二分图。因此，为了从图中删除顶点来获得二分图，就需要“命中所有奇数环”或找到所谓的奇环横贯集合。例如在图示中，图中的每个奇数环都包含蓝色（最底部）顶点，因此删除这些顶点就相当于删除了所有奇数环并留下一个二分图。