更改

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]

The two sets <math>U</math> and <math>V</math> may be thought of as a coloring of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="s12">{{citation  | year = 2012}}.</ref>  In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

The two sets <math>U</math> and <math>V</math> may be thought of as a coloring of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="s12">{{citation  | year = 2012}}.</ref>  In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

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被称为均衡二分图。如果在二分图中同一侧（同一个子集）所有的顶点都具有相同的度数，则G被称为双正则二分图。

* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite. Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.

* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite. Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.

* 平面图（图论）中，所有面都具有偶数条边的平面图是二分的。特殊情况是网格图和方图，其中每个内面都由4个边组成，每个内顶点都有4个或更多的相邻点。

* 平面图（图论）中，所有面都具有偶数条边，该图为二分图。特殊情况是网格图和方图，其中每个内面都有4个边，每个内顶点都有4个或更多的相邻点。

* 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.

* [[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（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树图和方图都是中位数图，而所有中位数图都是局部立方体。

* The [[Spectral graph theory|spectrum]] of a graph is symmetric if and only if it's a bipartite graph.

* The [[Spectral graph theory|spectrum]] of a graph is symmetric if and only if it's a bipartite graph.

* 当且仅当它是二分图时，图的频谱spectrum是对称的。

* 当且仅当它是二分图时，图的频谱是对称的。

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.

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

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

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）。其同构二分图具有相同的度数序列。但是，度数序列通常不是定义二分图的唯一方法；在某些情况下，非同构二分图可能具有相同的度数序列。

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

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.

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.

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

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

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.

可以使用深度优先搜索Depth-first search来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数周期（如果不是二分图）。其方法的主要思想是为每个顶点分配与深度优先搜索林Depth-first search forest中其父级颜色不同的颜色，并在其中进行遍历。这必定会为生成森林spanning forest提供两种颜色，包括将顶点连接到其父级的边。不过它可能无法为非森林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的祖先，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则森林中从祖先到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回着色性质以及该图形为二分图的结果。

可以使用深度优先搜索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.

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.

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

奇数循环遍历是一个NP完全算法问题NP-complete algorithmic problem（因不能用多项式算法而使问题无法解决的），在给定图形G =（V，E）和数字k的情况下，询问是否存在一组k个顶点，将其从G移除会导致生成为二分图。这个问题是固定参数可解的fixed-parameter tractable，这意味着存在一种算法，其运行时间可以由图形大小的多项式函数乘以增大系数k来确定。奇数循环遍历的名称源于：当且仅当图没有奇数环时，该图是二分图。因此，为了从图中删除顶点来获得二分图，就需要“命中所有奇数环”或找到所谓的技术循环遍历集合。例如在图示中，图中的每个奇数环都包含蓝色（最底部）顶点，因此删除这些顶点就相当于删除了所有奇数环并留下一个二分图。

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.

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算法）仅在二分图输入的时候才能正确运行。

一个图中的匹配是其边集的一个子集，其中任意两个边均不共享一个端点。多项式时间算法Polynomial time algorithms素以解决很多关于匹配的算法问题而得名，包括最大匹配maximum matching（查找使用尽可能多的边的匹配），最大权重匹配maximum weight matching和稳定婚姻问题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. 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.

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阐述的就是二分图允许完美匹配的特征。国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。

举一个简单的例子，假设一组P的所有人都在一组J的职位中寻找工作，但并不是所有人都适合所有职位。可以将这种情况建模为一个二分图（P，J，E），其中当每个求职者找到其合适的工作时产生的关系就作为连边。一个完美的匹配描述的是所有求职者同时找到所有工作的情况；霍尔的婚姻定理Hall's marriage theorem阐述的就是二分图允许完美匹配的特征。美国国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。

Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.

Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.

二分图在现代编码理论中被广泛使用，尤其是对从通道接收到的密码进行解码。例如因子图Factor graphs和坦纳图Tanner graphs。Tanner图是二分图，其中二分的一侧顶点表示一个密码数字，另一侧顶点表示一个数字的组合，这些数字的总和期望为零而没有错误。因子图与置信网络密切相关，用于LDPC和Turbo码的概率解码。

二分图在现代编码理论中被广泛使用，尤其是对从通道接收到的密码进行解码。例如因子图Factor graphs和坦纳图Tanner graphs。Tanner图是二分图，其中二分的一侧顶点表示一个密码数字，另一侧顶点表示一个数字的组合，这些数字的总和期望为零且不存在误差。因子图与置信网络密切相关，用于LDPC和Turbo码的概率解码。

In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes:  A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources.  There are additional constraints on the nodes and edges that constrain the behavior of the system.  Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.

In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes:  A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources.  There are additional constraints on the nodes and edges that constrain the behavior of the system.  Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.