961
个编辑
更改
跳到导航
跳到搜索
第185行：
第185行： − + − + − + − + − 我们可以用深度优先搜索来检验一个图是否是二部图，并且可以在线性时间内返回一个双染色(如果是二部图)或一个奇循环(如果不是)。其主要思想是在深度优先搜索森林中为每个顶点分配与其父顶点颜色不同的颜色，在深度优先搜索森林的前序遍历中分配颜色。这将必然提供一个双着色的跨森林组成的边连接顶点到他们的父母，但它可能不适当的颜色一些非森林边。在深度优先搜索森林中，每个非森林边缘的两个端点中的一个是另一个端点的祖先，当深度首次搜索发现这种类型的边缘时，应该检查这两个顶点是否有不同的颜色。如果不是这样，那么森林中从祖先到后代的路径与错误着色的边一起形成一个奇循环，这个奇循环由算法返回，并得到图不是二部图的结果。然而，如果算法在没有检测到奇圈的情况下终止，那么每条边都必须正确着色，并且算法返回着色结果和图是二部图的结果。< ref > { citation+ − − | last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist) − − | last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist) − − 罗伯特·塞奇威克: 计算机科学家 − − | edition = 3rd − − | edition = 3rd − − 3 rd − − | pages = 109–111 − − | pages = 109–111 − − | pages = 109-111 − − | publisher = Addison Wesley − − | publisher = Addison Wesley − − 艾迪生 · 韦斯利 − − | title = Algorithms in Java, Part 5: Graph Algorithms − − | title = Algorithms in Java, Part 5: Graph Algorithms − − Java 中的算法，第五部分: 图算法 − − | year = 2004}}.</ref> − − | year = 2004}}.</ref> − − | year = 2004} . </ref > 第235行：
第199行： − + − − 或者，类似的方法也可以用广度优先搜索替代深度优先搜索。同样，在搜索林中，每个节点以与其父节点相反的颜色按广度优先的顺序给出。如果，当一个顶点着色时，存在一条边将其与先前着色的顶点用同样的颜色连接起来，那么这条边与广度优先搜索森林中连接其两个端点与它们的最近公共祖先的路径一起形成一个奇怪的循环。如果算法以这种方式终止而不发现奇循环，那么它一定已经发现了一个适当的着色，并且可以安全地得出图是二部图的结论。< ref > { citation − − | last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg − − | last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg − − 1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg − − | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos − − | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos − | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos+ − − | pages = 94–97 − − | pages = 94–97 − − 94-97 − − | publisher = Addison Wesley − − | publisher = Addison Wesley − − 艾迪生 · 韦斯利 − − | title = Algorithm Design − − | title = Algorithm Design − − 算法设计 − − | year = 2006}}.</ref> − − | year = 2006}}.</ref> − − | year = 2006} . </ref > 第281行：
第209行： − 对于 < math > n </math > 线段的交叉图或欧几里德平面上其他简单形状，即使图本身可能有 < math > o (n ^ 2) </math > 边，也可以检验图是否为二部图，并在时间上返回一个双染色或奇循环。< ref > { citation+ − − | last = Eppstein | first = David | author-link = David Eppstein − − | last = Eppstein | first = David | author-link = David Eppstein − − 最后 = Eppstein | 第一 = David | author-link = David Eppstein − − | arxiv = cs.CG/0307023 − − | arxiv = cs.CG/0307023 − − | arxiv = cs.CG/0307023 − − | doi = 10.1145/1497290.1497291 − − | doi = 10.1145/1497290.1497291 − − 10.1145/1497290.1497291 − − | issue = 2 − − | issue = 2 − − 2 − − | journal = ACM Transactions on Algorithms − − | journal = ACM Transactions on Algorithms − − 关于算法的 ACM 汇刊 − − | mr = 2561751 − − | mr = 2561751 − − 2561751先生 − − | page = Art. 15 − − | page = Art. 15 − − | page = Art.15 − − | title = Testing bipartiteness of geometric intersection graphs − − | title = Testing bipartiteness of geometric intersection graphs − − | title = 几何交图的测试双分性 − − | volume = 5 − − | volume = 5 − − 5 − − | year = 2009}}.</ref> − − | year = 2009}}.</ref> − − 2009} . </ref > − − ===Odd cycle transversal=== − − {{main|Odd cycle transversal}} − − [[File:Odd Cycle Transversal of size 2.png|thumb|A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.]] − − A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph. − − 一个具有大小为2的奇圈横截的图: 去掉两个蓝色底顶点后得到一个二部图。 − − [[Odd cycle transversal]] is an [[NP-complete]] [[algorithm]]ic 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.<ref name=yannakakis1978node>{{citation − − 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.<ref name=yannakakis1978node>{{citation − − 奇圈横截是一个 np 完全计算问题，它要求给定一个图 g = (v，e)和一个数 k，是否存在一组 k 点，从 g 中去掉这些点会使得得到的图是二部图。1978 node > { citation − − | last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis − − | last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis − − 最后 = yannakis | first = Mihalis | author-link = Mihalis yannakis − − | contribution = Node-and edge-deletion NP-complete problems − − | contribution = Node-and edge-deletion NP-complete problems − − | 贡献 = 节点和边删除 np 完全问题 − − | doi = 10.1145/800133.804355 − − | doi = 10.1145/800133.804355 − − | doi = 10.1145/800133.804355 − − | pages = 253–264 − − | pages = 253–264 − − | 页 = 253-264 − − | title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78) − − | title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78) − − | title = 第十届 ACM 计算理论研讨会论文集(STOC’78) − − | year = 1978| title-link = Symposium on Theory of Computing }}</ref> The problem is [[Parameterized complexity|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''.<ref name=reed2004finding>{{citation − − | year = 1978| title-link = Symposium on Theory of Computing }}</ref> 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.<ref name=reed2004finding>{{citation − − 这个问题是固定参数可处理的，这意味着有一个算法，其运行时间可以由图的大小乘以一个更大的函数 k 的多项式函数来限定 − − | last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician) − − | last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician) − − 1 = Reed | first1 = Bruce | author1-link = Bruce Reed (数学家) − − | last2 = Smith | first2 = Kaleigh − − | last2 = Smith | first2 = Kaleigh − − 2 = Smith | first2 = Kaleigh − − | last3 = Vetta | first3 = Adrian − − | last3 = Vetta | first3 = Adrian − − 3 = Vetta | first3 = Adrian − − | doi = 10.1016/j.orl.2003.10.009 − − | doi = 10.1016/j.orl.2003.10.009 − − 10.1016/j.orl. 2003.10.009 − − | issue = 4 − − | issue = 4 − − 第四期 − − | journal = Operations Research Letters − − | journal = Operations Research Letters − − | 日志 = 运筹学快报 − − | mr = 2057781 − − | mr = 2057781 − − 2057781先生 − − | pages = 299–301 − − | pages = 299–301 − − | 页数 = 299-301 − − | title = Finding odd cycle transversals − − | title = Finding odd cycle transversals − − | title = 查找奇怪的循环横截 − − | volume = 32 − − | volume = 32 − − 32 − − | year = 2004| citeseerx = 10.1.1.112.6357}}.</ref> The name ''odd cycle transversal'' comes from the fact that a graph is bipartite if and only if it has no odd [[Cycle (graph theory)|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 (combinatorics)|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. − − | year = 2004| citeseerx = 10.1.1.112.6357}}.</ref> 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. − − 10.1.1.112.6357}.名称奇圈横截来自于这样一个事实: 一个图是二部图当且仅当它没有奇圈。因此，要从图中删除顶点以得到二部图，就需要“遍历所有奇圈” ，或者找到一个所谓的奇圈横截集。在图中，图中的每个奇数圈都包含蓝色(最底部的)顶点，因此去掉这些顶点会杀死所有奇数圈并留下一个二部图。 − − − − 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 ''O''(2<sup>''k''</sup> ''m''<sup>2</sup>),<ref name=guo2006compression>{{citation − − 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 O(2<sup>k</sup> m<sup>2</sup>),<ref name=guo2006compression>{{citation − − 边双分问题是为了构造一个二部图而删除尽可能少的边的计算问题问题，也是图修正算法中的一个重要问题。这个问题也是固定参数易于处理的，可以在 o (2 < sup > k </sup > m < sup > 2 </sup >) ，< ref name = guo2006compression > { citation > 中解决 − − | last1 = Guo | first1 = Jiong − − | last1 = Guo | first1 = Jiong − − 1 = Guo | first1 = Jiong − − | last2 = Gramm | first2 = Jens − | last2 = Gramm | first2 = Jens − 2 = Gramm | first2 = Jens − | last3 = Hüffner | first3 = Falk+ − | last3 = Hüffner | first3 = Falk+ − | last3 = Hüffner | first3 = Falk+ − | last4 = Niedermeier | first4 = Rolf+ − | last4 = Niedermeier | first4 = Rolf − 4 = Rolf − | last5 = Wernicke | first5 = Sebastian + − | last5 = Wernicke | first5 = Sebastian + − 5 = Wernicke | first5 = Sebastian+ − | doi = 10.1016/j.jcss.2006.02.001 − | doi = 10.1016/j.jcss.2006.02.001 − | doi = 10.1016/jcss. 2006.02.001+ − − | journal = Journal of Computer and System Sciences − − | journal = Journal of Computer and System Sciences − − 计算机与系统科学杂志 − − | volume = 72 − − | volume = 72 − − 72 − − | issue = 8 − − | issue = 8 − − 第8期 − − | pages = 1386–1396 − − | pages = 1386–1396 − − | 页数 = 1386-1396 − − | title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization − − | title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization − − | title = 基于压缩的反馈顶点集和边双分离的固定参数算法 − − | year = 2006}}</ref> where ''k'' is the number of edges to delete and ''m'' is the number of edges in the input graph. − − | year = 2006}}</ref> where k is the number of edges to delete and m is the number of edges in the input graph. − − | year = 2006} </ref > 其中 k 是要删除的边数，m 是输入图中的边数。 − − − − − + − − A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.<ref>{{citation − − 图中的匹配是其边的一个子集，没有两条边共享一个端点。多项式时间算法已知的许多算法问题的匹配，包括最大匹配(寻找匹配，使用尽可能多的边) ，最大权重匹配，和稳定的婚姻。< ref > { citation − − | last1 = Ahuja | first1 = Ravindra K. − − | last1 = Ahuja | first1 = Ravindra K. − − 1 = Ahuja | first1 = Ravindra k. − − | last2 = Magnanti | first2 = Thomas L. − − | last2 = Magnanti | first2 = Thomas L. − − 2 = Magnanti | first2 = Thomas l. − − | last3 = Orlin | first3 = James B. − − | last3 = Orlin | first3 = James B. − − 3 = Orlin | first3 = James b. − − | contribution = 12. Assignments and Matchings − − | contribution = 12. Assignments and Matchings − − 12.作业和匹配 − − | pages = 461–509 − − | pages = 461–509 − − | 页数 = 461-509 − − | publisher = Prentice Hall − − | publisher = Prentice Hall − − 普伦蒂斯 · 霍尔 − − | title = Network Flows: Theory, Algorithms, and Applications − − | title = Network Flows: Theory, Algorithms, and Applications − − | title = 网络流: 理论、算法和应用 − − | year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> and many matching algorithms such as the [[Hopcroft–Karp algorithm]] for maximum cardinality matching<ref>{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.</ref> work correctly only on bipartite inputs. − − | year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs, and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching work correctly only on bipartite inputs. − − 1993}}.在许多情况下，二部图上的匹配问题比非二部图上的匹配问题更容易解决，而且许多匹配算法，如最大基数匹配的霍普克罗夫特-卡普算法，只能在二部图输入上正确工作。 − − − − As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> A [[perfect matching]] describes a way of simultaneously satisfying all job-seekers and filling all jobs; [[Hall's marriage theorem]] provides a characterization of the bipartite graphs which allow perfect matchings. The [[National Resident Matching Program]] applies graph matching methods to solve this problem for [[Medical education in the United States|U.S. medical student]] job-seekers and [[Residency (medicine)|hospital residency]] jobs.<ref>{{citation − − As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.<ref>{{citation − − 举个简单的例子，假设一组人都在一组工作中找工作，并不是所有的人都适合所有的工作。这种情况可以模拟为一个二部图 < math > (p，j，e) </math > 其中一条边连接每个求职者和每个合适的工作。完美匹配描述了一种同时满足所有求职者和填补所有工作岗位的方法; 霍尔的婚姻定理提供了二部图的角色塑造，这些图允许完美匹配。国家住院医生匹配计划(National Resident Matching Program)应用图形匹配方法来解决美国医学生求职者和医院住院医生工作的这一问题。< ref > { citation − − |last = Robinson − − |last = Robinson − − | last = Robinson − |first = Sara+ − |first = Sara+ − 第一名: 莎拉 − |date = April 2003 − |date = April 2003+ − | date = April 2003+ − |issue = 3+ − − |issue = 3 − − 第三期 − − |journal = SIAM News − − |journal = SIAM News − − 日志 = SIAM 新闻 − − |page = 36 − − |page = 36 − − 36 − − |title = Are Medical Students Meeting Their (Best Possible) Match? − − |title = Are Medical Students Meeting Their (Best Possible) Match? − − | title = 医学生是否达到了他们的(最佳可能的)匹配？ − − |url = http://www.siam.org/pdf/news/305.pdf − − |url = http://www.siam.org/pdf/news/305.pdf − − Http://www.siam.org/pdf/news/305.pdf − − |access-date = 2012-08-27 − − |access-date = 2012-08-27 − − | access-date = 2012-08-27 − − |archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf − − |archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf − − | archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf − − |archive-date = 2016-11-18 − − |archive-date = 2016-11-18 − − | archive-date = 2016-11-18 − − |url-status = dead − − |url-status = dead − − 地位 = 死亡 − − }}.</ref> − − }}.</ref> − − } . </ref > 第693行：
第255行： − Dulmage-Mendelsohn 分解是二部图的一种结构分解，它有助于找到最大匹配。+ − −
→Algorithms
==Algorithms==
== Algorithms 算法 ==
===Testing bipartiteness===
=== 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.<ref>{{citation
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.<ref>{{citation
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.
可以使用深度优先搜索Depth-first search来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数周期（如果不是二分图）。其方法的主要思想是为每个顶点分配与深度优先搜索林Depth-first search forest中其父级颜色不同的颜色，并在其中进行遍历。这必定会为生成森林spanning forest提供两种颜色，包括将顶点连接到其父级的边。不过它可能无法为非森林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的祖先，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则森林中从祖先到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回着色性质以及该图形为二分图的结果。
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.<ref>{{citation
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.<ref>{{citation
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.<ref>{{citation
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.
又或者，可以使用广度优先搜索来替代深度优先搜索进行检测。同样，在搜索林中，以广度优先的顺序为每个节点赋予与父级节点相反的颜色。如果在着色某个顶点时存在一条边，其连接了与先前着色的顶点相同的颜色。然后这条边沿着以广度优先搜索林中的路径，将其两个端点与其最低共有祖先相连，形成一条奇数环。当然，如果该算法最终没找到奇数环且终止，那么它肯定已经找到了正确的着色，并且可以安全返回并得出该图是二分图的结论。
For the intersection graphs of <math>n</math> line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation
For the intersection graphs of <math>n</math> line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation
对于n个线段的相交图或欧几里得平面Euclidean plane中的其他简单形状图，即使图本身可能具有多达O(N2)个边缘，也可以测试其是否而二分图，并在时间O(n lon n)中返回双色（判定为二分图）或奇数环（判定为非二分图）。
=== 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.
奇数循环遍历是一个NP完全算法问题NP-complete algorithmic problem（因不能用多项式算法而使问题无法解决的），在给定图形G =（V，E）和数字k的情况下，询问是否存在一组k个顶点，将其从G移除会导致生成的二分图。这个问题是固定参数可解的fixed-parameter tractable，这意味着存在一种算法，其运行时间可以由图形大小的多项式函数乘以增大系数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.
边二分化问题Edge bipartization problem是删除尽可能少的边以使其成为二分图的问题，也是图修改算法中的重要问题。此问题同样是固定参数可解的，可以在时间O（2k m2）内解决，其中k是要删除的边数，m是输入图中的边数。
=== Matching 匹配 ===
===Matching===
{{main|Matching (graph theory)}}
{{main|Matching (graph theory)}}
A [[Matching (graph theory)|matching]] in a graph is a subset of its edges, no two of which share an endpoint. [[Polynomial time]] algorithms are known for many algorithmic problems on matchings, including [[maximum matching]] (finding a matching that uses as many edges as possible), [[maximum weight matching]], and [[stable marriage]].<ref>{{citation
A [[Matching (graph theory)|matching]] in a graph is a subset of its edges, no two of which share an endpoint. [[Polynomial time]] algorithms are known for many algorithmic problems on matchings, including [[maximum matching]] (finding a matching that uses as many edges as possible), [[maximum weight matching]], and [[stable marriage]].In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[31] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[32] work correctly only on bipartite inputs.
A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,[31] and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching[32] work correctly only on bipartite inputs.
一个图中的匹配是其边集的一个子集，其中任意两个边均不共享一个端点。多项式时间算法素以解决很多关于匹配的算法问题而得名，包括最大匹配（查找使用尽可能多的边的匹配），最大权重匹配和稳定婚姻问题stable marriage。在许多情况下，与非二分图相比，二分图上的匹配问题更容易解决，并且许多匹配算法（例如用于最大基数匹配的Hopcroft-Karp算法）仅在二分图输入的时候才能正确运行。
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> A [[perfect matching]] describes a way of simultaneously satisfying all job-seekers and filling all jobs; [[Hall's marriage theorem]] provides a characterization of the bipartite graphs which allow perfect matchings. The [[National Resident Matching Program]] applies graph matching methods to solve this problem for [[Medical education in the United States|U.S. medical student]] job-seekers and [[Residency (medicine)|hospital residency]] jobs.
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.
举一个简单的例子，假设一组P的所有人都在一组J的职位中寻找工作，但并不是所有人都适合所有职位。可以将这种情况建模为一个二分图（P，J，E），其中当每个求职者找到其合适的工作时产生的关系就作为连边。一个完美的匹配描述的是所有求职者同时找到所有工作的情况；霍尔的婚姻定理Hall's marriage theorem阐述的就是二分图允许完美匹配的特征。国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。
The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.
The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.
Dulmage–Mendelsohn 分解是二分图的结构分解，可用于寻找最大匹配。
==Additional applications==
==Additional applications==