961
个编辑
更改
→Testing bipartiteness 二分性测试
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.
可以使用'''<font color="#ff8000"> 深度优先搜索Depth-first search</font>'''来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数环（如果不是二分图）。其方法的主要思想是为每个顶点分配与'''<font color="#ff8000"> 深度优先搜索林Depth-first search forest</font>'''中其父级颜色不同的颜色，并在其中进行遍历。这必定会为'''<font color="#ff8000"> 生成森林spanning forest</font>'''提供两种颜色，包括将顶点连接到其父级的边。不过它可能无法为非森林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的祖先，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则森林中从祖先到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回双色以及该图形为二分图的结果。
可以使用'''<font color="#ff8000"> 深度优先搜索Depth-first search</font>'''来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数环（如果不是二分图）。其方法的主要思想是为每个顶点分配与'''<font color="#ff8000"> 深度优先搜索林Depth-first search forest</font>'''中其父级颜色不同的颜色，并在其中进行遍历。这必定会为'''<font color="#ff8000"> 生成森林Spanning forest</font>'''提供两种颜色，包括将顶点连接到其父级的边。不过它可能无法为非森林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的祖先，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则森林中从祖先到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回双色以及该图形为二分图的结果。
Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.
Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.
又或者，可以使用'''<font color="#ff8000"> 广度优先搜索Breadth-first search</font>'''来替代深度优先搜索进行检测。同样，在搜索林中，以广度优先的顺序为每个节点赋予与父级节点相反的颜色。如果在着色某个顶点时存在一条边，其连接了与先前着色的顶点相同的颜色。然后这条边沿着以广度优先搜索林中的路径，将其两个端点与其'''<font color="#ff8000"> 最低共有祖先lowest common ancestor</font>'''相连，形成一条奇数环。当然，如果该算法最终没找到奇数环且终止，那么它肯定已经找到了正确的着色，可以安全返回并得出该图是二分图的结论。
又或者，可以使用'''<font color="#ff8000"> 广度优先搜索Breadth-first search</font>'''来替代深度优先搜索进行检测。同样，在搜索林中，以广度优先的顺序为每个节点赋予与父级节点相反的颜色。如果在着色某个顶点时存在一条边，其连接了与先前着色的顶点相同的颜色。然后这条边沿着以广度优先搜索林中的路径，将其两个端点与其'''<font color="#ff8000"> 最低共有祖先Lowest common ancestor</font>'''相连，形成一条奇数环。当然，如果该算法最终没找到奇数环且终止，那么它肯定已经找到了正确的着色，可以安全返回并得出该图是二分图的结论。