更改

二分图可以用以下几种不同的方式来描述其特征：

二分图可以用以下几种不同的方式来描述其特征：

* A graph is bipartite [[if and only if]] it does not contain an [[Cycle (graph theory)|odd cycle]].<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by [[Dénes Kőnig]]. For infinite graphs, this result requires the [[axiom of choice]].

* A graph is bipartite [[if and only if]] it does not contain an [[Cycle (graph theory)|odd cycle]]. Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by [[Dénes Kőnig]]. For infinite graphs, this result requires the [[axiom of choice]].

* 当且仅当它不包含奇数环的时候，该图为二分图。

* 当且仅当它不包含奇数环的时候，该图为二分图。

===Relation to hypergraphs and directed graphs===

=== Relation to hypergraphs and directed graphs 与超图和有向图的关系 ===

The [[Adjacency matrix of a bipartite graph|biadjacency matrix]] of a bipartite graph <math>(U,V,E)</math> is a [[(0,1) matrix]] of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

The [[Adjacency matrix of a bipartite graph|biadjacency matrix]] of a bipartite graph <math>(U,V,E)</math> is a [[(0,1) matrix]] of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

The biadjacency matrix of a bipartite graph <math>(U,V,E)</math> is a (0,1) matrix of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

The biadjacency matrix of a bipartite graph <math>(U,V,E)</math> is a (0,1) matrix of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

二部图的二邻接矩阵 < math > (u，v，e) </math > 是一个大小为 < math > | u | times | v | </math > 的(0,1)矩阵，每对相邻顶点有一个1，对不相邻顶点有一个0。双邻接矩阵可以用来描述二部图、超图和有向图之间的等价关系。

一个二分图（U，V，E）的双邻矩阵是大小为|V| 的（0,1）矩阵，其分别代表了每对相邻顶点集合和非相邻顶点的集合（全零矩阵）。双邻接矩阵可用于描述二分图，超图和定向图之间的等价关系。

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.

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between [[directed graph]]s (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with {{mvar|n}} vertices can be any [[(0,1) matrix]] of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with {{mvar|n}} vertices on each side of its bipartition.<ref>{{citation

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between [[directed graph]]s (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with {{mvar|n}} vertices can be any [[(0,1) matrix]] of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with {{mvar|n}} vertices on each side of its bipartition.<ref>{{citation

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with  vertices can be any (0,1) matrix of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with  vertices on each side of its bipartition.<ref>{{citation

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with  vertices can be any (0,1) matrix of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with  vertices on each side of its bipartition.

一个类似的邻接矩阵翻唱可以用来显示有向图(在给定数量的标号顶点上，允许自循环)和平衡二部图之间的双射，二部图的两边顶点数相同。因为，顶点有向图的邻接矩阵可以是任意大小的(0,1)矩阵 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n。< ref > { citation

关于邻接矩阵的另一个相似解释可以被用于展示有向图和均衡二分图（二分子集顶点数相等）之间的一一对应关系（在给定数量的标记顶点上，允许自循环）。例如，具有n个顶点的有向图的邻接矩阵可以是大小为nxn的任何（0,1）矩阵，然后可以将其重新解释为：具有相同顶点数n的同边子集的二分图的邻接矩阵。通过这种构建方式，二分图可以被解释为是一个有向图的二分双重覆盖bipartite double cover。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

| year = 1958}}.</ref> In this construction, the bipartite graph is the bipartite double cover of the directed graph.

 

==Algorithms==

==Algorithms==