更改

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

The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics.  This problem is also fixed-parameter tractable, and can be solved in time, where k is the number of edges to delete and m is the number of edges in the input graph.

The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics.  This problem is also fixed-parameter tractable, and can be solved in time, where k is the number of edges to delete and m is the number of edges in the input graph.

'''<font color="#ff8000"> 边二分化问题Edge bipartization problem</font>'''是删除尽可能少的边以使其成为二分图的问题，也是图修改算法中的重要问题。此问题同样是固定参数可解的，可以在时间O（2k m2）内解决，其中k是要删除的边数，m是输入图中的边数。

'''<font color="#ff8000"> 边二分化问题Edge bipartization problem</font>'''是删除尽可能少的边以使其成为二分图的问题，也是图修改算法中的重要问题。此问题同样是固定参数可解的，可以在时间O(2k m2),内解决，其中''k''是要删除的边数，''m''是输入图中的边数。

 

 

=== Matching 匹配 ===

=== Matching 匹配 ===