更改

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets {\displaystyle U}U and {\displaystyle V}V such that every edge connects a vertex in {\displaystyle U}U to one in {\displaystyle V}V. Vertex sets {\displaystyle U}U and {\displaystyle V}V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets {\displaystyle U}U and {\displaystyle V}V such that every edge connects a vertex in {\displaystyle U}U to one in {\displaystyle V}V. Vertex sets {\displaystyle U}U and {\displaystyle V}V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]

One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;<ref>{{citation | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application.  If <math>|U|=|V|</math>, that is, if the two subsets have equal cardinality, then <math>G</math> is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then <math>G</math> is called biregular.

One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;<ref>{{citation | year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application.  If <math>|U|=|V|</math>, that is, if the two subsets have equal cardinality, then <math>G</math> is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then <math>G</math> is called biregular.

对于二分图常用的表达方式是G=(U,V,E)，其中U和V分别代表顶点子集，E代表二分图中的连边。如果有一个二分图内部不连通，则它可能具有多个二分图；在这种情况下，(U,V,E)标注将有助于指定一个特殊的二分图。在实际的应用当中，这无比重要。如果|U|=|V|，即这两个子集具有相同的基数，此时G被称为均衡二分图。如果在二分图中同一侧（同一个子集）所有的顶点都具有相同的度数，则G被称为双正则二分图。

对于二分图常用的表达方式是G=(U,V,E)，其中U和V分别代表顶点子集，E代表二分图中的连边。如果有一个二分图内部不连通，则它可能具有多个二分图；在这种情况下，(U,V,E)标注将有助于指定一个特殊的二分图。在实际的应用当中，这无比重要。如果|U|=|V|，即这两个子集具有相同的基数，此时G被称为'''<font color="#ff8000"> 均衡二分图Balanced bipartite graph</font>'''。如果在二分图中同一侧（同一个子集）所有的顶点都具有相同的度数，则G被称为'''<font color="#ff8000"> 双正则二分图Biregular</font>'''。

* The [[complete bipartite graph]] on ''m'' and ''n'' vertices, denoted by ''K_n,m'' is the bipartite graph <math>G = (U, V, E)</math>, where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''.  It follows that ''K_m,n'' has ''mn'' edges.

* The [[complete bipartite graph]] on ''m'' and ''n'' vertices, denoted by ''K_n,m'' is the bipartite graph <math>G = (U, V, E)</math>, where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''.  It follows that ''K_m,n'' has ''mn'' edges.

* 在一个完全二分图中，分别有由m和n的顶点（用Km,n表示）组成的两个不相交的集合U和V，连边E由分别在集合U和V的两个顶点连接。该二分图表示为G =（U，V，E），并且具有mn条边。另外完全二分图还包含一个特例，那就是冠图Crown graphs。冠图是通过将一个完全二分图中所有的完美匹配连边去掉形成的。

* 在一个完全二分图中，分别有由m和n的顶点（用Km,n表示）组成的两个不相交的集合U和V，连边E由分别在集合U和V的两个顶点连接。该二分图表示为G =（U，V，E），并且具有mn条边。另外完全二分图还包含一个特例，那就是'''<font color="#ff8000"> 冠图Crown graphs</font>'''。冠图是通过将一个完全二分图中所有的完美匹配连边去掉形成的。

* [[Hypercube graph]]s, [[partial cube]]s, and [[median graph]]s are bipartite. In these graphs, the vertices may be labeled by [[bitvector]]s, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.

* [[Hypercube graph]]s, [[partial cube]]s, and [[median graph]]s are bipartite. In these graphs, the vertices may be labeled by [[bitvector]]s, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.

* 超立方体图Hypercube graph，局部立方体partial cube和中位数图median graph均为二分图。判别方法是将这些图中的顶点用位向量bitvector（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树图和方图都是中位数图，而所有中位数图都是局部立方体。

* '''<font color="#ff8000"> 超立方体图Hypercube graph</font>'''，'''<font color="#ff8000"> 局部立方体partial cube</font>'''和'''<font color="#ff8000"> 中位数图median graph</font>'''均为二分图。判别方法是将这些图中的顶点用'''<font color="#ff8000"> 位向量bitvector</font>'''（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树图和方图都是中位数图，而所有中位数图都是局部立方体。

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[16][17] An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.[18] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.

In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[16][17] An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.[18] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.

在二分图中，最小顶点覆盖Minimum vertex cover（顶点数）等于最大匹配数Maximum matching(边数)；这就是柯尼希定理Kőnig's theorem。该定理的另一种等效形式是，最大独立集Maximum independent set（顶点数）加上最大匹配数等于顶点的数量。在任何没有孤立顶点的图中，最小边覆盖Minimum edge cover（边数）加上最大匹配数等于顶点数。于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。

在二分图中，'''<font color="#ff8000"> 最小顶点覆盖Minimum vertex cover</font>'''（顶点数）等于'''<font color="#ff8000"> 最大匹配数Maximum matching</font>'''(边数)；这就是'''<font color="#ff8000"> 柯尼希定理Kőnig's theorem</font>'''。该定理的另一种等效形式是，'''<font color="#ff8000"> 最大独立集Maximum independent set</font>'''（顶点数）加上最大匹配数等于顶点的数量。在任何没有孤立顶点的图中，'''<font color="#ff8000"> 最小边覆盖Minimum edge cover</font>'''（边数）加上最大匹配数等于顶点数。于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。

Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.

Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.

According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.

According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.

根据强完美图定理Strong perfect graph theorem，完美图具有类似于二分图的禁止图特征Forbidden graph characterization：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为导出子图Induced subgraph时，图才是完美的。二分图，其线图以及补图构成了完美图五种基本类别中的四个，被用于证明了强完美图定理。

根据'''<font color="#ff8000"> 强完美图定理Strong perfect graph theorem</font>'''，完美图具有类似于二分图的'''<font color="#ff8000"> 禁止图特征Forbidden graph characterization</font>'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为'''<font color="#ff8000"> 导出子图Induced subgraph</font>'''时，图才是完美的。二分图，其线图以及补图构成了完美图五种基本类别中的四个，被用于证明了强完美图定理。

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph K_3,5 has degree sequence <math>(5,5,5),(3,3,3,3,3)</math>. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph K_3,5 has degree sequence <math>(5,5,5),(3,3,3,3,3)</math>. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.

一个二分图的度数序列是一对列表，每个列表包含两个部分U和V的度数。例如，完全二分图K3,5具有度数序列（5,5,5），（3,3,3,3,3）。其同构二分图Isomorphic bipartite graphs具有相同的度数序列。但是，度数序列通常不是定义二分图的唯一方法；在某些情况下，非同构二分图可能具有相同的度数序列。

一个二分图的度数序列是一对列表，每个列表包含两个部分U和V的度数。例如，完全二分图K3,5具有度数序列（5,5,5），（3,3,3,3,3）。其'''<font color="#ff8000"> 同构二分图Isomorphic bipartite graphs</font>'''具有相同的度数序列。但是，度数序列通常不是定义二分图的唯一方法；在某些情况下，非同构二分图可能具有相同的度数序列。

The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)

The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)

二分实现问题bipartite realization problem是通过已知的两组自然数序列作为度数序列，来查找简单的二分图的判定问题（数理逻辑）。（尾随零可以忽略，因为通过向图添加适当数量的孤立顶点可以轻松实现尾随零。）

'''<font color="#ff8000"> 二分实现问题bipartite realization problem</font>'''是通过已知的两组自然数序列作为度数序列，来查找简单的二分图的判定问题（数理逻辑）。（尾随零可以忽略，因为通过向图添加适当数量的孤立顶点可以轻松实现尾随零。）

A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which  is the set of vertices of the hypergraph,  is the set of hyperedges, and  contains an edge from a hypergraph vertex  to a hypergraph edge  exactly when  is one of the endpoints of . Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.

A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which  is the set of vertices of the hypergraph,  is the set of hyperedges, and  contains an edge from a hypergraph vertex  to a hypergraph edge  exactly when  is one of the endpoints of . Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.